结论：当 $\binom{n}{a_1,a_2,…,a_k}$是奇数并且 $n$是偶数的时候 Alice 必败
首先我们来证明这个结论
首先当你有 $n$个字母的时候（假设上一轮还有 $n+1$个字母），那么你有两种方案，如果删掉一个字母可以让对手进入必败态，就直接删；否则如果 $\binom{n}{a_1,a_2,…,a_k}$是偶数，你可以通过 $\binom{n}{a_1,a_2,…,a_k}-1$步交换先手顺序让自己必胜。
那如何定夺 $\binom{n}{a_1,a_2,…,a_k}$是奇数的情况呢，很多题解直接用归纳法证明了，我在这里写个比较直觉性的证明
首先根据勒让德定理
$$\nu _{p}(n!)=\sum _{{i=1}}^{{\infty }}\left\lfloor {\frac {n}{p^{i}}}\right\rfloor$$
$\nu_p(n)$表示 $n$的标准分解里 $p$的指数，或者如果 $p^k||n$,$\nu_p(n)=k$
改写一下形式得到
$$\nu_{p}(n!)={\frac {n-s_{p}(n)}{p-1}}$$
其中 $s_p(n)$表示 n 在 p 进制下各位之和（用等比数列求和就能得到）
所以
$$\nu_2\binom{n}{a_1,a_2,…,a_k} = 0$$
$$\nu_2(n!)=\nu_2(a_1!)+ \cdots + \nu_2(a_k!)$$
$$s_2(n)=s_2(a_1)+ \cdots + s_2(a_k)$$
也就是说，$a_1+\cdots + a_k$在二进制下不能进位，也就是 $a_1|a_2|\cdots|a_k = \sum a_i$，这也是库默尔定理的一个推论。值得一提的是，库默尔定理本身可以用相似的方法证明，这里不再赘述。
我们记 $S =\binom{n}{a_1,a_2,…,a_k} $，现在每个人都要尽量地使得每次 $n-1$后 $S$是奇数，也就是要让 $\sum a_i$在二进制下不能进位，我们只需要每次把含有 $lowbit(n)$的对应的 $a_i$给减 1 即可。
这样，对于任意 $S$且 $S$是奇数的情况下，当前先手都可以让 $n$减 $1$来达到翻转情况的目的。因为每个人都是这样做的，且 $n=0$是必败态，所以 $n$为偶数且 $S$是奇数的时候必败。
$Q.E.D.$
接着我们来 dp，记 $f_{i,S}$表示取完第 $i$个字母且状态为 $S$的方案数，我们有：
$$f_{i,S} = \sum_{x \subseteq S} \frac {1}{x!}f_{i-1,S – x}$$
这里因为 $\binom{n}{a_1,a_2,…,a_k}=\frac{n!}{a_1!a_2!\cdots a_k!}$，我们只需要在 $f$里记录分母，最后对于每个 $f_{k,S}$乘上 $S!$即可。
注意到这是一个子集卷积的形式，直接用 $FWT$就可以 $O(nlog^2n)$计算。
因为子集卷积有结合律，可以加一个快速幂，直接快速幂 $FWT$变换后的部分即可，可以减小常数。
总复杂度 $O(nlog^2nlogk)$
//HomuraCat codes it!
#include<time.h>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<bitset>
#include<queue>
#include<vector>
#include<set>
#include<cstdlib>
#include<iostream>
#include<utility>
#include<map>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define eps 1e-4
#define lowbit(x) (x & -x)
#define N 263005
#define clr(arr) memset(arr, 0, sizeof arr)
#define bset std::bitset<N>
#define pi std::pair<int, int>
inline ll read ()
{
ll x = 0; bool flag = 0; char ch = getchar();
while (!isdigit(ch) && ch != '-') ch = getchar();
if (ch == '-') flag = 1, ch = getchar();
while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
if (flag) x = -x; return x;
}
inline ll qabs (ll x) { return x < 0 ? -x : x; }
int P;
inline ll qpow (ll x, int y)
{
ll ret = 1;
while (y)
{
if (y & 1) ret = ret * x % P;
x = x * x % P;
y >>= 1;
}
return ret;
}
int n, m, f[19][N], g[19][N], h[19][N];
void add (int &x, int y)
{
x = x + y;
if (x >= P) x -= y;
}
void fwt(int *a,int limit,int op){
for(int mid=1;mid<limit;mid<<=1){
for(int R=(mid<<1),i=0;i<limit;i+=R){
for(int j=0;j<mid;++j){
if(op==1) a[i+j+mid]=(a[i+j]+a[i+j+mid])%P;
else a[i+j+mid]=(a[i+j+mid]-a[i+j]+P)%P;
}
}
}
}
int fac[N], ifac[N];
int limit = 1, up = 0;
void mul (int a[][N], int b[][N])
{
fo (i, 0, up)
fo (j, 0, i)
fo (k, 0, limit - 1)
h[i][k] = (h[i][k] + 1ll * a[j][k] * b[i - j][k]) % P;
fo (i, 0, up) fo (k, 0, limit - 1) a[i][k] = h[i][k], h[i][k] = 0;
}
void pow_m(int m)
{
fo (i, 0, up) fwt(f[i], limit, 1);
fo (i, 0, up) fwt(g[i], limit, 1);
while (m)
{
if (m & 1) mul(f, g);
m >>= 1;
mul(g, g);
}
fo (i, 0, up) fwt(f[i], limit, -1);
}
int main ()
{
n = read(); m = read(); P = read();
ll ans = qpow(m, n);
if (n & 1)
{
printf("%lld\n", ans);
return 0;
}
while (limit <= n) limit <<= 1, up++;
fac[0] = ifac[0] = 1;
fo (i, 1, limit) fac[i] = 1ll * fac[i - 1] * i % P;
ifac[limit] = qpow(fac[limit], P - 2);
fd (i, limit - 1, 1) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;
f[0][0] = 1;
fo (i, 0, limit - 1) g[__builtin_popcount(i)][i] = ifac[i];
pow_m(m);
ans = (ans - 1ll * f[__builtin_popcount(n)][n] * fac[n] % P + P) % P;
printf("%lld\n", ans % P);
return 0;
}
后记：
我这份代码跑了 2994ms 莽过去的，人傻常数大（虽然本机只有 1.5s 左右
后来发现 AC 代码里有 100+ms 的，就去学习了一下。
发现他用的是子集枚举，不过暴力子集枚举 $O(3^{\log n}k)$肯定是过不了的，但他给每个字母定了序，并且规定前 $i$个字母必须都要至少出现一次，且它们的首位一定是从左到右依次的。因为本身位置只有 $\log n$个，是小于 $k$的，所以能用等比数列求和优化掉。
详细写在了草稿纸上：
0 条评论