CF838C Future Failure 题解

· · 题解

题意

两人轮流操作一个长度为 n 的由字母表中前 k 个字符组成的字符串。每次将字符串重新排列或删去一个字符，并不能和之前的字符串相同。不能操作者失败。

问有多少种字符串可以使得先手必胜，对质数 p 取模。

n \leqslant 250000,k \leqslant 26

题解

假设给定一个字符串，考虑判断情况，假设当前每个字符出现了 a_i 次，并且记重排方式有 b 种，可以得到：

b=\frac{n!}{\prod_{i=1}^ka_i!}

若 b 为偶数先手必胜，证明：

  1. 若有一种一开始就删除的方案，自然会这样干。
  2. 否则，先手重排一下，那么后手不可能去删除而取得获胜，这样与第一种情况矛盾。那么两人会一直重排，到最后后手不能就重排了。

那 b 不是偶数怎么办呢？显然这个时候先手只能一开始就删除，假如删除的字符是 i，则 b 会变成 \frac{ba_i}{n}，所以我们考虑找到最小的 \text{lowbit}(a_i)，假如是 a_j，由于 a_i 的和等于 n，所以 \text{lowbit}(a_j)\leq\text{lowbit}(n)。考虑把 b,a_j,n 分解质因数，发现若把 a_j 删掉，b 中二的因子只会减少，即还是奇数。那么局面没有变化两个人一直删数，所以当前 n 是奇数时先手必胜。

总结一下：

  2. 否则，b 是偶数时先手必胜。

那么重点在于判断 b 的奇偶性，所以不妨把计算 b 放在模二意义下进行。

b\equiv\frac{n!}{\prod_{i=1}^ka_i!} \pmod 2

这样的式子并不好观察，换一种计算方式，设 b_i 表示用 i 种字符当前的重排数量。

b_i\equiv {\sum_{i=1}^i a_i\choose a_i} b_{i-1} \pmod 2

那么

b_k\equiv {n\choose a_k} b_{k-1} \pmod 2

根据卢卡斯定理 {n\choose a_k} \bmod 2 = 1 当且仅当 a_k 是 n 的二进制子集，所以 n-a_k 同样也是 n 的二进制子集。于是可以归纳 a_{k-1} 也是 n 的二进制子集。最后得出 a_i 都要是 n 的二进制子集。

那么怎么计数呢？先把 a_i 都要是 n 的二进制子集，并且 \sum_{i=1}^k a_i=n 转化成：把 a_i 全部或起来等于 n，并且 \text{popcount}(a_i) 的和等于 \text{popcount}(n)，于是可以 FWT 做。

时间复杂度是 \mathcal{O}\left(n\log k \log^2 n\right) 感觉过不了是吧，但是官方题解就是这个复杂度。

#include<bits/stdc++.h>
// #define ONLINE_JUDGE
#define INPUT_DATA_TYPE int
#define OUTPUT_DATA_TYPE int
inline __attribute((always_inline)) INPUT_DATA_TYPE read(){register INPUT_DATA_TYPE x=0;register char f=0,c=getchar();while(c<'0'||'9'<c)f=(c=='-'),c=getchar();while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+(c&15),c=getchar();return f?-x:x;}void print(OUTPUT_DATA_TYPE x){if(x<0)x=-x,putchar('-');if(x>9)print(x/10);putchar(x%10^48);return;}

const int barK=64;
struct Barrett_Mod{
    unsigned long long d;__uint128_t m;
    void init(long long mod){
        m=(((__uint128_t)1)<<barK)/(d=mod);
        return;
    }

    inline __attribute((always_inline)) unsigned long long operator ()(register unsigned long long x){
        register unsigned long long w=(m*x)>>barK;
        w=x-w*d;
        return w>=d?w-d:w;
    }
}MOD;

long long mod;

void FWT_OR(long long *f,long long x,int n){
    register int i,j,k,o;
    for(o=2,k=1;o<=n;o<<=1,k<<=1)
        for(i=0;i<n;i+=o)
            for(j=0;j<k;++j)
                f[i+j+k]=MOD(f[i+j+k]+f[i+j]*x);
    return;
}

#define PC_DATA_TYPE long long

const PC_DATA_TYPE PC_DATA_SIZE=1000010;

PC_DATA_TYPE inv[PC_DATA_SIZE],fact[PC_DATA_SIZE],invfact[PC_DATA_SIZE];

void init_pc(int n){
    register int i;
    for(inv[0]=0,inv[1]=fact[0]=fact[1]=invfact[0]=invfact[1]=1,i=2;i<=n;++i)
        invfact[i]=invfact[i-1]*(inv[i]=mod-mod/i*inv[mod%i]%mod)%mod,fact[i]=fact[i-1]*i%mod;
    return;
}


#define QPOW_DATA_TYPE long long
QPOW_DATA_TYPE qpow(register QPOW_DATA_TYPE base,register QPOW_DATA_TYPE e){
    register QPOW_DATA_TYPE res=1;
    while(e){
        if(e&1) res=MOD(res*base);
        base=MOD(base*base);
        e>>=1;
    }
    return res;
}

long long f[19][300000],g[19][300000];

int main(){
    #ifndef ONLINE_JUDGE
    freopen("name.in", "r", stdin);
    freopen("name.out", "w", stdout);
    #endif

    register int i,j,k,len,e,cnt;
    register long long res;
    int n=read();
    int K=read();
    mod=read();

    MOD.init(mod);

    res=qpow(K,n);

    if(!(n&1)){
        cnt=__builtin_popcount(n);
        len=1<<std::__lg(n);
        if(len<=n) len<<=1;
        init_pc(len);

        for(i=0;i<len;++i) f[__builtin_popcount(i)][i]=invfact[i],g[0][i]=1;
        for(i=0;i<=cnt;++i) FWT_OR(f[i],1,len);

        e=K;
        while(e){
            if(e&1)
                for(j=cnt;~j;--j) for(k=0;k<j;++k) for(i=0;i<len;++i)
                    g[j][i]=MOD(g[j][i]+g[k][i]*f[j-k][i]);

            for(j=cnt;~j;--j) for(k=0;k<j;++k) for(i=0;i<len;++i)
                f[j][i]=MOD(f[j][i]+f[k][i]*f[j-k][i]);

            e>>=1;
        }

        FWT_OR(g[cnt],mod-1,len);
        (res+=mod-g[cnt][n]*fact[n]%mod)%=mod;
    }

    print(res);

    #ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    #endif
    return 0;
}