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)，那么转移为

[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);
}

程序员灯塔
转载请注明原文链接：P5363 [SDOI2019]移动金币