• 欢迎光临~

# P5363 [SDOI2019]移动金币

## P5363 [SDOI2019]移动金币

[f_{i,j} = sum_{2|k}f_{i,j - 2^i*k} * dbinom{lfloor frac{m + 1}{2}rfloor}{k} ]

Code
``````#include<cstdio>
#define LL long long
using namespace std;
const int N = 150005, P = 1e9 + 9;
int n, m; LL f[30][N], fac[N], inv[N];

LL getc(int x, int y){return fac[x] * inv[y] % P * inv[x - y] % P;}
int main() {
scanf("%d%d",&n,&m), fac[0] = inv[0] = inv[1] = 1;
for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * (LL)i % P;
for (int i = 2; i <= n; i++) inv[i] = (P - P / i) * inv[P % i] % P;
for (int i = 2; i <= n; i++) inv[i] = inv[i] * inv[i - 1] % P;
int bit = 0, z = n - m; while (z) z >>= 1, bit++;
f[0][0] = 1;
for (int i = 1; i <= bit; i++)
for (int j = 0; j <= n - m; j++)
for (int k = 0; k <= (m + 1 >> 1) && (1 << i - 1) * k <= j; k += 2)
(f[i][j] += f[i - 1][j - (1 << i - 1) * k] * getc(m + 1 >> 1, k) % P) %= P;
LL ans = 0; int a = (m + 1 >> 1) - 1, b = m >> 1;
for (int j = 0; j <= n - m; j++)
(ans += (getc(j + a, a) - f[bit][j] + P) * getc(n - m - j + b, b) % P) %= P;
printf("%lldn", ans);
}

``````