P5363 [SDOI2019]移动金币
转化一下题意，移动一个金币相当于把这个金币前面的格子移到了后面，这是经典的阶梯\(\text{Nim}\)，因为题目是把格子向后移，所以我们只要保证一共\(m + 1\)个数，\(\lfloor \frac{m + 1}{2}\rfloor\)个数的异或和不为\(0\)，所有的数和为\(n - m\)，这样我们可以\(O(mn^3)\)\(DP\)，但我们发现有太多的无用的状态了，考虑求出异或和为零的方案数，再用全部方案数减去其。
那么我们可以考虑按位来\(DP\)，每一位上\(1\)的个数为偶数即可，设\(f_{i,j}\)表示考虑到了第\(i\)位，当前所有的数和为\(j\)，那么转移为
答案再乘上其他数随便选的方案即可。
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("%lld\n", ans);
}