BZOJ3771: Triple

n<=40000个<=40000的不同数字，问选一个或两个或三个，凑成每个值的方案数。

选东西，总数加起来为某值的方案数--生成函数，$f$表示选一个的，$g$表示两个一样的，$h$表示三个一样的（等会去重要用）。

选一个：$f$

选两个：$frac{f^2-g}{2}$

选三个：$frac{f^3-3*(g*f-h)-h}{6}$。

直接用点值算完再换成系数。

//#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
//#include<map>
#include<math.h>
//#include<time.h>
//#include<complex>
#include<algorithm>
using namespace std;
 
int n,m,wei;
#define maxn 300011
const int mod=998244353,G=3;
 
int powmod(int a,int b)
{
    int ans=1;
    while (b)
    {
        if (b&1) ans=1ll*ans*a%mod;
        a=1ll*a*a%mod; b>>=1;
    }
    return ans;
}
 
int rev[maxn];
void dft(int *a,int n,int type)
{
    if (!rev[1]) for (int i=0;i<n;i++)
    {
        rev[i]=0;
        for (int j=0;j<wei;j++) rev[i]|=((i>>j)&1)<<(wei-j-1);
    }
    for (int i=0;i<n;i++) if (i<rev[i]) {int t=a[i]; a[i]=a[rev[i]]; a[rev[i]]=t;}
    for (int i=1;i<n;i<<=1)
    {
        int w=powmod(G,(mod-1)/(i<<1));
        if (type==-1) w=powmod(w,mod-2);
        for (int j=0,p=i<<1;j<n;j+=p)
        {
            int t=1;
            for (int k=0;k<i;k++,t=1ll*t*w%mod)
            {
                int tmp=1ll*t*a[j+k+i]%mod;
                a[j+k+i]=(a[j+k]-tmp+mod)%mod;
                a[j+k]=(a[j+k]+tmp)%mod;
            }
        }
    }
    if (type==-1)
    {
        int inv=powmod(n,mod-2);
        for (int i=0;i<n;i++) a[i]=1ll*a[i]*inv%mod;
    }
}
 
void ntt(int *a,int *b,int *c)
{
    dft(a,n,1); dft(b,n,1);
    for (int i=0;i<n;i++) c[i]=1ll*a[i]*b[i]%mod;
    dft(c,n,-1); 
}
 
int f[maxn],g[maxn],s[maxn],h[maxn],ans[maxn];
int main()
{
    scanf("%d",&n); int Max=0;
    for (int i=1,x;i<=n;i++) scanf("%d",&x),Max=x,f[x]=1,g[x+x]=1,s[x+x+x]=1;
    m=Max*3; for (n=1,wei=0;n<=m;n<<=1,wei++);
     
    dft(f,n,1); dft(g,n,1); dft(s,n,1);
    for (int i=0,tmp6=((mod+1)/6),tmp2=((mod+1)>>1);i<n;i++)
    ans[i]=(((1ll*f[i]*f[i]%mod*f[i]%mod-3ll*g[i]*f[i]%mod+2*s[i])%mod*tmp6%mod
    +(1ll*f[i]*f[i]%mod-g[i])%mod*tmp2%mod+f[i])%mod+mod)%mod;
    dft(ans,n,-1);
    for (int i=0;i<=m;i++) if (ans[i]>0) printf("%d %d
",i,ans[i]);
    return 0;
}