Luogu4233 射命丸文的笔记 DP、多项式求逆

ゝ一纸荒年。 2021-11-26 09:40 213阅读 0赞

[传送门][Link 1]

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

注意到总共有\\(\\frac\{n!\}\{n\}\\)条本质不同的哈密顿回路，每一条哈密顿回路恰好会出现在\\(2^\{\\binom\{n\}\{2\} - n\}\\)个图中，所以我们实际上要算的是强连通有向竞赛图的数量。

设\\(f\_i\\)表示点数为\\(i\\)的强连通竞赛图数，转移考虑用总数\\(2^\\binom\{i\}\{2\}\\)减去不强连通的图数量。如果竞赛图不强连通，我们可以枚举拓扑序最靠后的一个强连通子图，如果它的大小为\\(j\\)，那么剩下\\(i-j\\)个点之间的边可以任意连，但是这\\(i-j\\)个和这\\(j\\)个点之间的边的方向是确定的，可以得到转移\\(f\_i = 2^\\binom\{i\}\{2\} - \\sum\\limits\_\{j=1\}^\{i-1\} \\binom\{i\}\{j\} 2^\\binom\{i-j\}\{2\} f\_j\\)，直接做复杂度\\(O(n^2)\\)

然后考虑优化。把\\(\\binom\{i\}\{j\}\\)拆开然后左右两边各除以\\(i!\\)得到\\(\\frac\{f\_i\}\{i!\} = \\frac\{2^\\binom\{i\}\{2\}\}\{i!\} - \\sum\\limits\_\{j=1\}^\{i-1\} \\frac\{f\_j\}\{j!\} \\frac\{2^\\binom\{i-j\}\{2\}\}\{i-j!\}\\)。设多项式\\(F = \\sum\\limits\_\{i=1\}^n \\frac\{f\_i\}\{i!\}x^i\\)，\\(G = \\sum\\limits\_\{i=1\}^n \\frac\{2^\\binom\{i\}\{2\}\}\{i!\} x^i\\)，可以得到\\(F = G - F \* G\\)，即\\(F = \\frac\{G\}\{G + 1\}\\)，多项式求逆即可。

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<vector>
    #include<queue>
    #include<cstring>
    #include<iomanip>
    #include<cmath>
    #include<cassert>
    //This code is written by Itst
    using namespace std;
    
    #define int long long
    const int MOD = 998244353 , _ = (1 << 18) + 3;
    int jc[_] , inv[_] , G[_] , H[_] , N;
    
    #define ch2(x) ((x) * ((x) - 1) / 2)
    
    int poww(int a , int b){
        int tms = 1;
        while(b){
            if(b & 1) tms = tms * a % MOD;
            a = a * a % MOD;
            b >>= 1;
        }
        return tms;
    }
    
    namespace poly{
        const int G = 3 , INV = 332748118;
        int dir[_] , need , invnd;
    
        void init(int len){
            need = 1;
            while(need < len) need <<= 1;
            invnd = poww(need , MOD - 2);
            for(int i = 1 ; i < need ; ++i)
                dir[i] = (dir[i >> 1] >> 1) | (i & 1 ? need >> 1 : 0);
        }
    
        void NTT(int *arr , int tp){
            for(int i = 1 ; i < need ; ++i)
                if(i < dir[i])
                    arr[i] ^= arr[dir[i]] ^= arr[i] ^= arr[dir[i]];
            for(int i = 1 ; i < need ; i <<= 1){
                int wn = poww(tp == 1 ? G : INV , MOD / i / 2);
                for(int j = 0 ; j < need ; j += i << 1){
                    int w = 1;
                    for(int k = 0 ; k < i ; ++k , w = w * wn % MOD){
                        int x = arr[j + k] , y = arr[i + j + k] * w % MOD;
                        arr[j + k] = x + y >= MOD ? x + y - MOD : x + y;
                        arr[i + j + k] = x < y ? x + MOD - y : x - y;
                    }
                }
            }
            if(tp != 1)
                for(int i = 0 ; i < need ; ++i)
                    arr[i] = arr[i] * invnd % MOD;
        }
    
    #define clr(x) memset(x , 0 , sizeof(int) * need)
        int A[_] , B[_];
        void getInv(int *a , int *b , int len){
            if(len == 1) return (void)(b[0] = poww(a[0] , MOD - 2));
            getInv(a , b , (len + 1) >> 1);
            memcpy(A , a , sizeof(int) * len);
            memcpy(B , b , sizeof(int) * len);
            init(len * 2 + 3); NTT(A , 1); NTT(B , 1);
            for(int i = 0 ; i < need ; ++i)
                A[i] = A[i] * B[i] % MOD * B[i] % MOD;
            NTT(A , -1);
            for(int i = 0 ; i < len ; ++i)
                b[i] = (2 * b[i] - A[i] + MOD) % MOD;
            clr(A); clr(B);
        }
    }
    
    signed main(){
        cin >> N;
        jc[0] = 1;
        for(int i = 1 ; i <= N ; ++i) jc[i] = jc[i - 1] * i % MOD;
        inv[N] = poww(jc[N] , MOD - 2);
        for(int i = N - 1 ; i >= 0 ; --i) inv[i] = inv[i + 1] * (i + 1) % MOD;
        for(int i = 1 ; i <= N ; ++i) G[i] = 1ll * poww(2 , ch2(i)) * inv[i] % MOD;
        G[0] = 1; poly::getInv(G , H , N + 1); G[0] = 0;
        poly::init(2 * N + 2); poly::NTT(G , 1); poly::NTT(H , 1);
        for(int i = 0 ; i < poly::need ; ++i)
            G[i] = 1ll * G[i] * H[i] % MOD;
        poly::NTT(G , -1);
        for(int i = 1 ; i <= N ; ++i)
            printf("%d\n" , i == 1 ? 1 : (i == 2 ? -1 : poww(G[i] , MOD - 2) * inv[i] % MOD * jc[i - 1] % MOD * poww(2 , ch2(i) - i) % MOD));
        return 0;
    }

转载于:https://www.cnblogs.com/Itst/p/10989483.html

[Link 1]: https://www.luogu.org/problemnew/show/P4233