BZOJ4555: [Tjoi2016&Heoi2016]求和

BZOJ4555: [Tjoi2016&Heoi2016]求和

https://lydsy.com/JudgeOnline/problem.php?id=4555

分析:

• \(g[n]=\sum\limits_{i=0}^{n}S(n,i)\times 2*i\times (i!)\)
• 考虑这个式子的组合意义，即\(n\)个数分成若干有序集合，且每个集合可选可不选。
• 枚举最后一个集合选几个数，有\(g(n)=\sum\limits_{i=1}^{n}2\times \binom{n}{i}\times g(n-i)\) 。
• \(g(n)=\sum\limits_{i=1}^{n}2\times \frac{n!}{i!\times (n-i)!}\times g(n-i)\)。
• \(\frac{g(n)}{n!}=\sum\limits_{i=1}^{n}\frac{g(n-i)}{(n-i)!}\times \frac{2}{i!}\)。
• 这是一个分治\(fft\)的形式，可以用多项式求逆优化。
• 具体地，我们设\(G=G\times H+1\)。
• \(G=\frac{1}{1-H}\)

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define N 400050
#define mod 998244353
typedef long long ll;
int fac[N],G[N],H[N],A[N],B[N];
int qp(int x,int y) {
    int re=1;
    for(;y;y>>=1,x=ll(x)*x%mod) if(y&1) re=ll(re)*x%mod; return re;
}
#define inv(x) (qp(x,mod-2))
void ntt(int *a,int len,int flg) {
    int i,j,k,t,w,wn,tmp;
    for(i=k=0;i<len;i++) {
        if(i>k) swap(a[i],a[k]);
        for(j=len>>1;(k^=j)<j;j>>=1) ;
    }
    for(k=2;k<=len;k<<=1) {
        t=k>>1;
        wn=qp(3,(mod-1)/k);
        if(flg==-1) wn=inv(wn);
        for(i=0;i<len;i+=k) {
            w=1;
            for(j=i;j<i+t;j++) {
                tmp=ll(a[j+t])*w%mod;
                a[j+t]=(a[j]-tmp)%mod;
                a[j]=(a[j]+tmp)%mod;
                w=ll(w)*wn%mod;
            }
        }
    }
    if(flg==-1) {
        t=inv(len);
        for(i=0;i<len;i++) a[i]=ll(a[i])*t%mod;
    }
}
void get_inv(int *a,int *b,int len) {
    if(len==1) {
        b[0]=inv(a[0]); return ;
    }
    get_inv(a,b,len>>1);
    int t=len<<1,i;
    for(i=0;i<len;i++) A[i]=a[i],B[i]=b[i];
    ntt(A,t,1), ntt(B,t,1);
    for(i=0;i<t;i++) {
        B[i]=(2-ll(A[i])*B[i])%mod*B[i]%mod;
    }
    ntt(B,t,-1);
    for(i=0;i<len;i++) b[i]=B[i];
}
int main() {
    int n;
    scanf("%d",&n);
    int i,ans=0;
    for(fac[0]=i=1;i<=n;i++) {
        fac[i]=ll(fac[i-1])*i%mod;
    }
    int len=1;
    while(len<=n) len<<=1;
    for(i=1;i<=n;i++) {
        H[i]=2*inv(fac[i])%mod;
    }
    H[0]=1;
    for(i=1;i<=n;i++) {
        H[i]=mod-H[i];
    }
    get_inv(H,G,len);
    for(i=0;i<=n;i++) {
        ans=(ans+ll(G[i])*fac[i])%mod;
    }
    printf("%d\n",(ans%mod+mod)%mod);
}

BZOJ4555: [Tjoi2016&Heoi2016]求和

原文：https://www.cnblogs.com/suika/p/10017232.html