传送门

结论:当 $\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$的,所以能用等比数列求和优化掉。

详细写在了草稿纸上:

分类: 文章

HomuraCat

明日は何になる? やがて君になる!

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注