2017 Multi-University Training Contest - 第一场 04 Division Game （NTT+数学）

野性酷女 2022-06-11 00:23 81阅读 0赞

题目链接：  
[HDU 6036][]

题解：  
(官方：[题解][Link 1])

显然每个石子堆最多做 ∑ m i=1 e i   （记为 w  ）次操作。此外，如果定义一个堆做 x  次操作恰好变为 1  的方案数为 f(x)  ，显然每个数字做少于 x  次操作不变为 1  的方案数也是 f(x)  。

为了统计结束于石子堆i 的情况数，我们可以枚举这是它第几次操作时结束的，不妨设为x ，则对应的方案数恰好是 f(x\+1) i−1 f(x) k−i\+1   ，因为编号小于等于 i  的石子堆做了 x  次操作不变为，其他石子堆做 x−1  次操作恰好变为 1  ，且只有石子堆 i  变成了一个石子。因此我们在 O(wk)  时间复杂度下将问题规约到 f(x)  的计算。

我们可以基于一个数的不同质因子几乎互不影响的观察得到第一个结论。每次操作保证任何一个 e i   (e i >0)  可以减少且至少一个 e i   会减少。自然而然我们可以发现一个容斥关系。

考虑f(x) 的组成，不妨设在某种方案中第 j  次操作使 e i   减少了d(i,j)  （非负值）。我们知道对于每个 e i   有 ∑ x j=1 d(i,j)=e i   ，且对于每个j  有∑ m i=1 d(i,j)>0  。进一步我们能发现f(x) 也就是分配d(i,j) (1≤i≤m,1≤j≤x)  使其满足上述两个条件的方案数。

假设只满足第一个条件的相应方案数为g(x) ，我们可以发现每个i 分别对应一个组合问题，从而是有：g(x)=∏ i=1 m (e i \+x−1x−1)  。

我们也可以观察到如果某些j 与第二个条件产生了矛盾，与之相关的d(i,j) 都会是零。利用容斥原理可以得到 f(x)=∑ y=0 x (−1) x−y (xy)g(y)  。这个式子可以化为一个卷积式子 f(x)x! =∑ y=0 x (−1) x−y (x−y)! ⋅g(y)y!   。因此你可以用一些方法来加速卷积，不过 985661441=235×2 22 \+1  是一个特殊的质数，所以我们推荐使用 NTT 。

总时间复杂度为O(wm\+wlogn\+wk) ，然而实现上谨慎一些也是很有必要的。

AC代码：

#include<bits/stdc++.h> 
    using namespace std;
    typedef long long ll;
    const int maxm = 11;
    const int maxn = 100010;
    const int maxLen = 18;
    const int maxs = 1<<18;
    const int mod = 985661441;
    const int gen = 3; // MOD的原根,当且仅当 g^(MOD-1) = 1 % MOD  
    ll q_mod(ll a,int b)     
    {  
        ll ans=1;  
        while(b>0)  
        {  
            if(b&1)     
                ans=(ans*a)%mod;               
            b>>=1;    
            a=(a*a)%mod;  
        }  
        return ans;  
    } 
    int inv2[maxLen + 1], w[maxs];
    int mod_add(int x, int y)
    {
        if(x+y>=mod)
        {
            return x+y-mod;
        }
        else return x+y;
    }
    int mod_sub(int x, int y)
    {
        if(x-y<0){
            return x-y+mod;
        }
        else return x-y;
    }
    void rader(int y[], int len)  
    {  
        for(int i = 1, j = len / 2; i < len - 1; i++){  
            if(i < j) swap(y[i], y[j]);  
            int k = len / 2;  
            while(j >= k) {  
                j -= k;  
                k /= 2;  
            }  
            if(j < k) j += k;  
        }  
    }  
    void NTT(int len, int x[], bool flag)//NTT
    {
        rader(x, len); 
        for(int i = 1, d = 1; d < len; i++, d <<= 1)
        {
            for(int j = 0; j < len; j += d << 1)
            {
                for(int k = 0; k < d; ++k)
                {
                    int t = 1LL * w[(maxs >> i) * k] * x[j + k + d] % mod;
                    x[j + d + k] = mod_sub(x[j + k], t);
                    x[j + k] = mod_add(x[j + k], t);
                }
            }
    
        }
    
        if(flag)
        {
            reverse(x + 1, x + len);
            int bitLen = 0;
            while(1<<bitLen < len)
            {
                bitLen++;
            }
            int val = inv2[bitLen];
            for(int i = 0; i < len; i++)
            {
                x[i] = 1LL*x[i] * val % mod;
            }
    
        }
    }
    int fact[maxn<<1];
    int iact[maxn];
    int n, m, k, e[maxm];
    int h[2][maxm];
    int cur, pre = 1;
    int ans[maxm];
    int f[maxs], g[maxs];
    
    void init()
    {
        w[0] = 1;
        w[1] = q_mod(gen, (mod - 1) >> maxLen);
        for(int i = 2; i < maxs; i++)
        {
            w[i] = 1LL*w[i - 1] * w[1] % mod;
        }
    
        inv2[0] = 1;
        inv2[1] = (mod + 1) >> 1;
        for(int i = 2; i <= maxLen; i++)
        {
            inv2[i] = 1LL*inv2[i - 1] * inv2[1] % mod;
        }
    
        fact[0] = 1;
        for(int i = 1; i < maxn << 1; i++)
        {
            fact[i] = 1LL*fact[i - 1] * i % mod;
        }
    
        iact[1] = 1;
        for(int i = 2; i < maxn; i++)
        {
            iact[i] = mod - (int)(mod / i * 1LL*iact[mod % i] % mod);
        }
    
        iact[0] = 1;
        for(int i = 1; i < maxn; i++)
        {
            iact[i] = 1LL*iact[i - 1] * iact[i] % mod;
        }    
    }
    int main()
    { 
        init();
        int Case = 0;  
        while(~scanf("%d%d",&m,&k))
        {
            Case++;
            n = 0;
            for(int i = 0; i < m; i++)
            {
                scanf("%*d%d", &e[i]);
                n += e[i];
            }
            int len=1;
            while(len < (n+1)<<1)
            {
                len <<= 1;
            }
    
            f[0] = 0;
            int delta = 1;
            for(int i = 0; i < m; i++)
            {
                delta = 1LL*delta * iact[e[i]] % mod;
            }
    
            for(int i = 1; i <= n; i++)
            {
                f[i] = 1LL*delta * iact[i] % mod * q_mod(iact[i - 1], m) % mod;
                for(int j = 0; j < m; j++)
                {
                    f[i] = 1LL*f[i] * fact[e[j] + i - 1] % mod;
                }
    
            }
            memset(f + n + 1, 0, (len - n - 1) * sizeof(int));
    
            NTT(len, f, 0);
            for(int i = 0; i <= n; i++)
            {
                g[i] = i & 1 ? mod - iact[i] : iact[i];
            }
    
            memset(g + n + 1, 0, (len - n - 1) * sizeof(int));
    
            NTT(len, g, 0);
            for(int i = 0; i < len; i++)
            {
                 f[i] = 1LL*f[i] * g[i] % mod;
            } 
            NTT(len, f, 1);
    
            memset(ans + 1, 0, k * sizeof(int));
            for(int i = 1; i <= n; i++)
            {
                cur ^= 1;
                pre ^= 1;
                f[i] = 1LL*f[i] * fact[i] % mod;
                h[cur][0] = 1;
                for(int j = 1; j <= k; j++)
                {
                    h[cur][j] = 1LL*h[cur][j - 1] * f[i] % mod;
                }       
                if(i > 1)
                {
                    for(int j = 1; j <= k; j++)
                    {
                        ans[j] = (ans[j] + (ll)h[cur][j - 1] * h[pre][k - j + 1]) % mod;
                    }
                }                    
            }
            if((ans[1] += h[cur][k]) >= mod)
            {
                 ans[1] -= mod;
            } 
            printf("Case #%d:", Case);
            for(int i = 1; i <= k; i++){
                printf(" %d", ans[i]);
            }    
            puts("");
        }
        return 0;
    }

[HDU 6036]: http://acm.hdu.edu.cn/showproblem.php?pid=6036
[Link 1]: http://bestcoder.hdu.edu.cn/blog/