题解 SP8372 【TSUM - Triple Sums】

太艹了... NTT 打惯了后被现实狠狠的扇了一巴掌 这题没有模数...但数据范围比较友好，全程不炸 double 【雾 （就算炸了咱也可以用 long double ，咳咳...） 所以咱也不能用 NTT 啊... （假的，您愿意双模数做完 NTT 之后 CRT 求解当然是阔以的，或者直接上一个大于答案理论值的模数硬杠，祝好运） 所以咱只能用法法塔，不过也蛮好打的（板子 copy 一下谁不会，笑） 光顾着说 这题是如何毒瘤迫害 NTT 的，正经说说这道题的解法好了： 因为有负数，我们直接把所有数加 20000 ，最后减掉 20000* 3 就好了，接下来讨论内容就不包含负数情况了 那么不难看出我们只要根据读入的数构造一个多项式然后乘起来加加减减就好了 【对于多项式搞背包有深入了解的同学可以跳过此段】 具体而言，读入一个数为 t 时，我们令多项式 A(x) 中的 $x^t$ 加一，表示体积为 t 的物品多了一个，那么我们最后把多项式乘一乘（或者是平方、立方）就发现某个体积 V 的构造方案为：$x^V$ 假设根据读入数据构造的多项式为 $A(x)$，那么咱首先对于这个0/1三元背包直接搞一个立方，发现里面是完全三元背包，于是构造俩多项式 B、C 来搞容斥 令 B(x) 为读入数据中每个数 t 乘二 为指数的多项式，C 为 t 乘三做指数的多项式 那么易知【雾： $$ans[t]= [x^t] {A(x)^3-3A(x)·B(x) +2C(x)\over 6}$$ 具体而言， $A(x)$ 中包含了不该考虑进去的 3 个$A(x)B(x)$ 以及 1 个 $C(x)$ ，然后每个 $A(x)B(x)$ 中又包含了一个 $C(x)$ ，实质就是简单容斥 然后 $O(m)$ （m 为 t 最大值* 3）扫一遍输出 ans 不为 0 的值就好了 # Code ``` //by Judge (zlw ak ioi) #include<bits/stdc++.h> #define eps 0.1 #define Rg register #define fp(i,a,b) for(Rg int i=(a),I=(b)+1;i<I;++i) #define fd(i,a,b) for(Rg int i=(a),I=(b)-1;i>I;--i) #define ll long long #define db double using namespace std; const double PI=acos(-1.0); const int M=3e5+3; typedef int arr[M]; #ifndef Judge #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) #endif char buf[1<<21],*p1=buf,*p2=buf; inline bool cmax(int& a,int b){return a<b?a=b,1:0;} inline int read(){ int x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } char sr[1<<21],z[20];int CCF=-1,Z; inline void Ot(){fwrite(sr,1,CCF+1,stdout),CCF=-1;} inline void print(ll x,char chr='\n'){ if(CCF>1<<20)Ot();if(x<0)sr[++CCF]=45,x=-x; while(z[++Z]=x%10+48,x/=10); while(sr[++CCF]=z[Z],--Z);sr[++CCF]=chr; } int n,m,limit; int r[M]; struct cp{ mutable db x,y; cp(db xx=0,db yy=0){x=xx,y=yy;} inline cp operator *(const int& b){return cp(x*b,y*b);} inline cp operator +(const cp& b){return cp(*this)+=b;} inline cp operator -(const cp& b){return cp(*this)-=b;} inline cp operator *(const cp& b){return cp(*this)*=b;} inline cp& operator +=(const cp& b){return *this=cp(x+b.x,y+b.y);} inline cp& operator -=(const cp& b){return *this=cp(x-b.x,y-b.y);} inline cp& operator *=(const cp& b){return *this=cp(x*b.x-y*b.y,x*b.y+y*b.x);} }a[M],b[M],c[M],Wn,w,x,y; inline void init(int n){ Rg int l=-1; limit=1; while(limit<=n) limit<<=1,++l; fp(i,1,limit-1) r[i]=(r[i>>1]>>1)|((i&1)<<l); } inline void FFT(cp* a,int type){ for(int i=0;i<limit;++i) if(i<r[i]) swap(a[i],a[r[i]]); for(int mid=1;mid<limit;mid<<=1){ Wn=cp(cos(PI/mid),type*sin(PI/mid)); for(int j=0,k;j<limit;j+=mid<<1) for(k=0,w=cp(1,0);k<mid;++k,w*=Wn) x=a[j+k],y=a[j+k+mid],y*=w,a[j+k]=a[j+k+mid]=x,a[j+k]+=y,a[j+k+mid]-=y; } if(type>0) return ; fp(i,0,limit-1) a[i].x=(ll)(a[i].x/limit/6+0.5); } int main(){ n=read(); Rg int x; fp(i,1,n) x=read()+20000,++a[x].x,++b[2*x].x,++c[3*x].x,cmax(m,x); init(m*3),FFT(a,1),FFT(b,1),FFT(c,1); fp(i,0,limit-1) a[i]=(a[i]*(a[i]*a[i]-b[i]*3)+c[i]*2); FFT(a,-1); fp(i,1,m*3) if(a[i].x>eps) print(i-60000,' '), sr[++CCF]=':',sr[++CCF]=' ',print((ll)a[i].x); return Ot(),0; } ``` 【水题，大雾】