Description
Link.
给你一个序列，你每次可以取 $1\sim3$ 个数然后计算和，问你对于每一种和，方案数是多少。
Solution
设一个 OGF $A(x)=\sum_{i=0}^{+\infty}a_{i}x^{i}$，指数为物品的价值，$a_{i}$ 为出现的次数。
也就是说，$\sum a_{i}$ 就是选个一个数的答案。
再来考虑选两个数。$A^{2}(x)$ 显然会有重复。
重复有两种情况，第一种是 $i\times j$ 和 $j\times i$，这个简单，除个 $2!$ 即可。
还有就是 $i\times i$ 的情况，那么再设一个表示一个斧头选两次的 OGF $B(x)=\sum_{i=0}^{+\infty}b_{i}x^{2i}$。
那么选两个数的答案为 $\frac{A^{2}(x)-B(x)}{2!}$。
再来考虑选三个数，基本同理地设 $C(x)=\sum_{i=0}^{+\infty}c_{i}x^{3i}$。
然后选三个数的答案为 $\frac{A^{3}(x)-3A(x)B(x)+2C(x)}{3!}$，这个容斥就是考虑 $\sf aab,baa$ 和 $\sf abc,acb$ 情况的重复。
做完了。
#include<bits/stdc++.h>
using namespace std;
namespace Poly
{
typedef complex<double> comp;
typedef vector<complex<double> > poly;
#define len(x) (int((x).size()))
const double bh_pi=acos(-1),eps=1e-3;
int lim,rev[500010];
void fft(poly &f,int op)
{
for(int i=0;i<lim;++i) if(i<rev[i]) swap(f[i],f[rev[i]]);
for(int len=2;len<=lim;len<<=1)
{
comp bas(cos(2*bh_pi/len),op*sin(2*bh_pi/len));
for(int fr=0;fr<lim;fr+=len)
{
comp now(1,0);
for(int ba=fr;ba<fr+(len>>1);++ba,now*=bas)
{
comp tmp=now*f[ba+(len>>1)];
f[ba+(len>>1)]=f[ba]-tmp;
f[ba]+=tmp;
}
}
}
if(op==-1) for(int i=0;i<lim;++i) f[i]/=lim;
}
poly mulPoly(poly f,poly g)
{
int n=len(f)+len(g)-1;
for(lim=1;lim<n;lim<<=1);
for(int i=0;i<lim;++i) rev[i]=(rev[i>>1]>>1)|((i&1)?(lim>>1):0);
f.resize(lim),g.resize(lim);
fft(f,1),fft(g,1);
for(int i=0;i<lim;++i) f[i]*=g[i];
fft(f,-1),f.resize(n);
return f;
}
poly addPoly(poly f,poly g)
{
int n=max(len(f),len(g));
f.resize(n),g.resize(n);
for(int i=0;i<n;++i) f[i]+=g[i];
return f;
}
poly decPoly(poly f,poly g)
{
int n=max(len(f),len(g));
f.resize(n),g.resize(n);
for(int i=0;i<n;++i) f[i]-=g[i];
return f;
}
poly mulPoly(poly f,double x)
{
for(int i=0;i<len(f);++i) f[i]*=x;
return f;
}
poly divPoly(poly f,double x)
{
for(int i=0;i<len(f);++i) f[i]/=x;
return f;
}
}using namespace Poly;
int main()
{
int waste,x;
scanf("%d",&waste);
poly one,two,thr;
while(waste--)
{
scanf("%d",&x);
if(x>=len(one)) one.resize(x+1);
if((x<<1)>=len(two)) two.resize(x<<1|1);
if((x<<1)+x>=len(thr)) thr.resize((x<<1)+x+1);
one[x]=comp(one[x].real()+1,0);
two[x<<1]=comp(two[x<<1].real()+1,0);
thr[(x<<1)+x]=comp(thr[(x<<1)+x].real()+1,0);
}
poly ans=addPoly(addPoly(one,divPoly(decPoly(mulPoly(one,one),two),2)),divPoly(addPoly(decPoly(mulPoly(mulPoly(one,one),one),mulPoly(mulPoly(one,two),3)),mulPoly(thr,2)),6));
for(int i=0;i<len(ans);++i) if(int(ans[i].real()+eps)) printf("%d %d\n",i,int(ans[i].real()+eps));
return 0;
}