首先考虑一个状态什么时候是合法的。不难把游戏过程抽象为阶梯 Nim 博弈。
根据阶梯 Nim 博弈的结论,先手必胜当且仅当奇数位上的异或和不为 0。
考虑将本题中每个棋子后面的若干格子数视作石子数,那么先手必胜的条件就是偶数位上的石子数异或和不为 0(奇数位变为偶数位是因为第一颗棋子前面还有一堆没用的)。
新的题意:\(n-m\) 个石子,分成 \(m+1\) 堆,求偶数位上石子数异或和不为 0 的方案数。
限制很强,考虑容斥,算偶数位上异或和为 0 的方案数,再用 \(\binom{n}{m}\) 减去它即可。
考虑一个 naive 的 DP:设 \(f(i,j,k)\) 表示前 \(i\) 堆放了 \(j\) 个石子,偶数位异或和为 \(k\) 的方案数。3D / 1D 动态规划,时间复杂度 \(\mathcal O(n^3m)\)。
因为和位运算相关,各位之间独立,那么考虑按位拆分。此处我没有想到是因为以前没有见过这种类型的 DP。
设 \(f(i,j)\) 表示前 \(i\) 个二进制位上偶数位石子异或和均为 0 的方案数。
考虑 \(i+1\) 位,显然要往偶数位上放 \(k(2|k)\) 个石子,造成的影响为 \(k\times 2^i\),偶数位上选 \(k\) 个位置的方案数为 \(\dbinom{\lfloor\frac{m+1}{2} \rfloor}{k}\)。
综上,有:
\[f(i,j)=\sum_{2|k,k\le \lfloor\frac{m+1}{2} \rfloor,k\times 2^{i-1}\le j} f(i-1,j-k\times 2^{i-1})\times \binom{\lfloor \frac{m+1}{2}\rfloor }{k} \]然后最后再用组合数算一下即可。时间复杂度 \(\mathcal O(nm\log n)\),用一些内存连续访问之类的卡常技巧足以通过。
// Problem: P5363 [SDOI2019]移动金币
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5363
// Memory Limit: 500 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
const int maxn = 1.5e5 + 5;
const int maxm = 22;
const int mod = 1e9 + 9;
int n,m,fac[maxn],inv[maxn],f[maxm][maxn],S,p,q;
void add(int& x,int y) {
x += y;
if(x >= mod)
x -= mod;
return ;
}
void sub(int& x,int y) {
x -= y;
if(x < 0)
x += mod;
return ;
}
int power(int x,int y) {
int ans = 1;
for(;y;y >>= 1) {
if(y & 1)
ans = 1ll * ans * x % mod;
x = 1ll * x * x % mod;
}
return ans;
}
int C(int n,int m) {
if(n < m||n < 0||m < 0)
return 0;
return 1ll * fac[n] * inv[n - m] % mod * inv[m] % mod;
}
int main() {
scanf("%d %d",&n,&m);
if(n < m) {
puts("0");
return 0;
}
fac[0] = 1;
for(int i = 1;i <= n;++ i)
fac[i] = 1ll * i * fac[i - 1] % mod;
inv[n] = power(fac[n] , mod - 2);
for(int i = n - 1;~ i;-- i)
inv[i] = 1ll * (i + 1) * inv[i + 1] % mod;
n -= m;
p = (m + 1) >> 1;
q = m + 1 - p;
S = std::log(n) / std::log(2) + 2;
f[0][0] = 1;
for(int i = 1;i <= S;++ i)
for(int j = 0;j <= n;++ j)
for(int k = 0;k <= p&&k * (1 << (i - 1)) <= j;k += 2)
add(f[i][j] , 1ll * f[i - 1][j - k * (1 << (i - 1))] * C(p , k) % mod);
int ans = C(n + m , m);
for(int i = 0;i <= n;++ i)
sub(ans , 1ll * f[S][i] * C(n - i + q - 1 , q - 1) % mod);
printf("%d\n",ans);
return 0;
}
标签:偶数,return,int,题解,石子,金币,异或,SDOI2019,mod
From: https://www.cnblogs.com/663B/p/17183180.html