传送门
结论:当 (na1,a2,…,ak)是奇数并且 n是偶数的时候 Alice 必败
首先我们来证明这个结论
首先当你有 n个字母的时候(假设上一轮还有 n+1个字母),那么你有两种方案,如果删掉一个字母可以让对手进入必败态,就直接删;否则如果 (na1,a2,…,ak)是偶数,你可以通过 (na1,a2,…,ak)−1步交换先手顺序让自己必胜。
那如何定夺 (na1,a2,…,ak)是奇数的情况呢,很多题解直接用归纳法证明了,我在这里写个比较直觉性的证明
首先根据勒让德定理
νp(n!)=∞∑i=1⌊npi⌋
νp(n)表示 n的标准分解里 p的指数,或者如果 pk||n,νp(n)=k
改写一下形式得到
νp(n!)=n−sp(n)p−1
其中 sp(n)表示 n 在 p 进制下各位之和(用等比数列求和就能得到)
所以
ν2(na1,a2,…,ak)=0
ν2(n!)=ν2(a1!)+⋯+ν2(ak!)
s2(n)=s2(a1)+⋯+s2(ak)
也就是说,a1+⋯+ak在二进制下不能进位,也就是 a1|a2|⋯|ak=∑ai,这也是库默尔定理的一个推论。值得一提的是,库默尔定理本身可以用相似的方法证明,这里不再赘述。
我们记 S=(na1,a2,…,ak),现在每个人都要尽量地使得每次 n−1后 S是奇数,也就是要让 ∑ai在二进制下不能进位,我们只需要每次把含有 lowbit(n)的对应的 ai给减 1 即可。
这样,对于任意 S且 S是奇数的情况下,当前先手都可以让 n减 1来达到翻转情况的目的。因为每个人都是这样做的,且 n=0是必败态,所以 n为偶数且 S是奇数的时候必败。
Q.E.D.
接着我们来 dp,记 fi,S表示取完第 i个字母且状态为 S的方案数,我们有:
fi,S=∑x⊆S1x!fi−1,S–x
这里因为 (na1,a2,…,ak)=n!a1!a2!⋯ak!,我们只需要在 f里记录分母,最后对于每个 fk,S乘上 S!即可。
注意到这是一个子集卷积的形式,直接用 FWT就可以 O(nlog2n)计算。
因为子集卷积有结合律,可以加一个快速幂,直接快速幂 FWT变换后的部分即可,可以减小常数。
总复杂度 O(nlog2nlogk)
#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(3lognk)肯定是过不了的,但他给每个字母定了序,并且规定前 i个字母必须都要至少出现一次,且它们的首位一定是从左到右依次的。因为本身位置只有 logn个,是小于 k的,所以能用等比数列求和优化掉。
详细写在了草稿纸上:

0 条评论