CF838C（博弈+FWT子集卷积+多项式ln、exp）

短命女 2021-12-11 04:07 203阅读 0赞

### 传送门： ###

--------------------

[http://codeforces.com/problemset/problem/838/C][http_codeforces.com_problemset_problem_838_C]

### 题解： ###

--------------------

如果一个字符串的排列数是偶数，则先手必胜，因为如果下一层有后手必赢态，直接转移过去，不然，就一直耗着，因为是偶数，所以会让后手进入下一层，则后手必输。

排列数是偶数，打表发现\\(|s|\\)是奇数时，先手必赢，否则后手必赢，接下来尝试归纳这个结论。

|s|<=2时显然成立。

对于\\(|S|\\)奇数,排列个数是奇数时，设a\[i\]表示第i个字符出现次数，排列个数=\\(\\binom\{|S|\}\{a\[1\],a\[2\],…,a\[k\]\}\\)，我们需要使一个a\[i\]减一，然后新的排列个数还是奇数，因为\\(|S|\\)是奇数，所以一定可以找到一个是奇数的\\(a\[i\]\\)，然后满足。

对于\\(|S|\\)偶数，排列个数是奇数时，不管新的的排列个数是奇数还是偶数，因为下一个长度是奇数，新状态都会先手比胜。

因此得证。

那么问题转换为选\\(a\[1\],a\[2\],…,a\[k\]，使\{\\forall i,j(i≠j)\}满足a\[i\]~and~a\[j\]=0\\)。

一个比较容易的思路，\\(>0\\)的\\(a\[i\]\\)肯定不超过\\(log ~ n\\)个，不难想到子集卷积，最后乘一个组合数。

子集卷积解决下面这个问题：  
\\(c\[i|j\]+=a\[i\]\*b\[j\](i~and~j=0)\\)

套路的解决方法是再记录一维表示1的个数，只要最后搞出的结果的1的个数相符就表示没有出现\\(i~and~j≠0\\)。

那么复杂度是\\(O(n~log^3~n)\\)，卡卡常就能过。

事实上有\\(O(n~log^2n)\\)的做法。

考虑不枚举\\(>0\\)的个数，直接暴力卷积：  
记\\(f\[i\]\[j\]\\)表示1的个数为i时状态为j的的系数和。

这个东西可以快速幂卷对吧，不过还是\\(log^3\\)的。

把状态反过来\\(f\[j\]\[i\]\\)表示状态为j的，1的个数为i的系数和，注意这个j已经FWT过了。

那么后面就相当于普通的多项式快速幂，求个ln\*k再exp即可。

注意到项数很少，可以暴力ln和exp。

暴力exp可以用组合意义搞：  
有\\(F\\)，设\\(f(x)\\)为它的EGF，即\\(f(x)\[x^n\]=F\[n\]/n!\\)

那么有\\(g(x)=e^\{f(x)\}\\)意义可以为有标号连通图->有标号一般图，\\(g(x)\\)是\\(G=e^\{f(x)\}\\)的EGF，所以有dp：

\\(G\[n\]\*n!=\\sum\_\{i=1\}^\{n\}\\binom\{n-1\}\{i-1\}\*F\[i\]\*i!\*G\[n-i\]\*(n-i)!\\)

\\(G\[n\]=\\sum\_\{i=1\}^\{n\}F\[i\]\*G\[n-i\]\*\{i\\over n\}\\)

ln的过程即由G->F，直接反过来可得：  
\\(F\[n\]=G\[n\]-\\sum\_\{i=1\}^\{n-1\}F\[i\]\*G\[n-i\]\*\{i \\over n\}\\)

### Code： ###

--------------------

#include<bits/stdc++.h>
    #define fo(i, x, y) for(int i = x, B = y; i <= B; i ++)
    #define ff(i, x, y) for(int i = x, B = y; i <  B; i ++)
    #define fd(i, x, y) for(int i = x, B = y; i >= B; i --)
    #define ll long long
    #define pp printf
    #define hh pp("\n")
    using namespace std;
    
    const int N = 3e5 + 5;
    
    int n, k, mo;
    ll fac[N], nf[N];
    
    ll ksm(ll x, ll y) {
        ll s = 1;
        for(; y; y /= 2, x = x * x % mo)
            if(y & 1) s = s * x % mo;
        return s;
    }
    
    ll C(int n, int m) {
        ll s = 1;
        fo(i, n - m + 1, n) s = s * i % mo;
        s = s * nf[m] % mo;
        return s;
    }
    
    ll ans;
    
    const int nm = (1 << 17) + 5;
    
    #define low(x) (x & -(x))
    int g[nm * 4];
    ll a[18][nm], f[2][18][nm]; int o;
    void fwt(ll *a, int n) {
        for(int i = 1; i < n; i *= 2) for(int j = 0; j < n; j += 2 * i)
            ff(k, 0, i) a[i + j + k] += a[j + k];
        ff(i, 0, n) a[i] %= mo;
    }
    int tp, aw[21];
    
    int main() {
        freopen("megalovania.in", "r", stdin);
        freopen("megalovania.out", "w", stdout);
        scanf("%d %d %d", &n, &k, &mo);
        if(n & 1) {
            pp("0\n"); return 0;
        }
        fac[0] = 1; fo(i, 1, n) fac[i] = fac[i - 1] * i % mo;
        nf[n] = ksm(fac[n], mo - 2); fd(i, n, 1) nf[i - 1] = nf[i] * i % mo;
        ff(i, 1, 1 << 19) g[i] = g[i - low(i)] + 1;
        tp = g[n]; int cw = 0;
        fo(j, 0, 18) if(n >> j & 1) {
            aw[j] = 1 << (cw ++);
        }
        fo(i, 1, n) if((i & n) == i) {
            int ni = 0;
            fo(j, 0, 18) if(i >> j & 1) ni += aw[j];
            a[g[i]][ni] = nf[i];
        }
        fo(i, 1, tp) fwt(a[i], 1 << tp);
        fo(i, 1, tp) ff(j, 0, 1 << tp) f[o][i][j] = a[i][j];
        int mx = (1 << tp) - 1;
        fo(i, 1, tp) {
            memset(f[!o], 0, sizeof f[!o]);
            if(i != tp) {
                fo(u, i, tp) fo(v, 1, tp - u) ff(j, 0, 1 << tp) if(f[o][u][j] && a[v][j])
                    f[!o][u + v][j] += f[o][u][j] * a[v][j],
                    f[!o][u + v][j] > 9e18 ? f[!o][u + v][j] %= mo : 0;
            }
            ll F = 0;
            ff(j, 0, 1 << tp) F += f[o][tp][j] * (g[j ^ mx] % 2 ? -1 : 1);
            F %= mo;
            ans += F * C(k, i) % mo * fac[n] % mo;
            o = !o;
            fo(u, 0, tp) ff(j, 0, 1 << tp) f[o][u][j] >= mo ? f[o][u][j] %= mo : 0;
        }
        ans = (ans % mo + mo) % mo;
        pp("%lld\n", ans);
    }

转载于:https://www.cnblogs.com/coldchair/p/11141466.html

[http_codeforces.com_problemset_problem_838_C]: http://codeforces.com/problemset/problem/838/C