3771. Triple
Description
我们讲一个悲伤的故事。从前有一个贫穷的樵夫在河边砍柴。这时候河里出现了一个水神，夺过了他的斧头，说：“这把斧头，是不是你的？”樵夫一看：“是啊是啊！”水神把斧头扔在一边，又拿起一个东西问：“这把斧头，是不是你的？”樵夫看不清楚，但又怕真的是自己的斧头，只好又答：“是啊是啊！”水神又把手上的东西扔在一边，拿起第三个东西问：“这把斧头，是不是你的？”樵夫还是看不清楚，但是他觉得再这样下去他就没法砍柴了。于是他又一次答：“是啊是啊！真的是！”水神看着他，哈哈大笑道：“你看看你现在的样子，真是丑陋！”之后就消失了。樵夫觉得很坑爹，他今天不仅没有砍到柴，还丢了一把斧头给那个水神。于是他准备回家换一把斧头。回家之后他才发现真正坑爹的事情才刚开始。水神拿着的的确是他的斧头。但是不一定是他拿出去的那把，还有可能是水神不知道怎么偷偷从他家里拿走的。换句话说，水神可能拿走了他的一把，两把或者三把斧头。樵夫觉得今天真是倒霉透了，但不管怎么样日子还得过。他想统计他的损失。樵夫的每一把斧头都有一个价值，不同斧头的价值不同。总损失就是丢掉的斧头价值和。他想对于每个可能的总损失，计算有几种可能的方案。注意：如果水神拿走了两把斧头a和b，(a,b)和(b,a)视为一种方案。拿走三把斧头时，(a,b,c),(b,c,a),(c,a,b),(c,b,a),(b,a,c),(a,c,b)视为一种方案。Input
第一行是整数N，表示有N把斧头。接下来n行升序输入N个数字Ai，表示每把斧头的价值。Output
若干行，按升序对于所有可能的总损失输出一行x y，x为损失值，y为方案数。Sample Input
4
4
5
6
7Sample Output
4 1
5 1
6 1
7 1
9 1
10 1
11 2
12 1
13 1
15 1
16 1
17 1
18 1
样例解释
11有两种方案是4+7和5+6，其他损失值都有唯一方案，例如4=4,5=5,10=4+6,18=5+6+7.Hint
所有数据满足：Ai<=40000
题解
假设我们没有不能重复选取而且无序计数的限制, 直接构造多项式 $A(x)=sumlimits_{kin S} x^k$ 然后计算 $A(x)+A(x)^2+A(x)^3$ 就好了
然而这题有点诡异...因为它要求的东西是无序对而且还不允许选两次...这就非常蠢...
好的那么我们想一想如果直接求 $A(x)+A(x)^2+A(x)^3$ 会发生什么:
对于形如 $(a,b)$ 的值, 我们会算两遍;
对于形如 $(a,b,c)$ 的值, 我们会算 $6$ 遍;
对于形如 $(a,a,b)$ 的值, 我们会算 $3$ 遍;
对于形如 $(a,a)$ 和 $(a,a,a)$ 的值, 我们会算 $1$ 遍(然而这些值不合法)
因为情况比较少, 我们手动容斥一发.
我们设 $A_1(x)$ 为原来的 $A(x)$, $A_2(x)$ 为将其中的所有项指数扩大两倍的多项式, $A_3(x)$ 同理. 这样我们就可以把两个同样的值绑定在一起计算方案.
然后我们对不同大小的组合分别计算:
大小为 $1$ 的组合, 显然就是 $A_1(x)$;
大小为 $2$ 的组合, $(a,b)$ 算了两遍, $(a,a)$ 算了一遍, 而 $(a,a)$ 不合法, 我们把它减掉. 而 $(a,a)$ 的方案数就是 $A_2(x)$, 于是这部分的答案就是 $frac 1 2 left(A_1(x)^2-A_2(x) ight)$
大小为 $3$ 的组合, $(a,b,c)$ 算了 $6$ 遍, $(a,a,b)$ 算了三遍, 我们想办法计算出 $(a,a,b)$ 的个数并减掉: 我们如果直接计算 $A_1(x)A_2(x)$ 的话又会把 $(a,a,a)$ 算上一遍, 所以 $(a,a,b)$ 的个数就是 $A_1(x)A_2(x)-A_3(x)$. $(a,a,a)$ 的个数就是 $A_3(x)$, 于是我们就可以得到总的方案数是 $frac 1 6 left(A_1(x)^3-3left(A_1(x)A_2(x)-A_3(x) ight)-A_3(x) ight)$
于是总答案就是长这样的:
$$ A_1(x)+frac 1 2 left(A_1(x)^2-A_2(x) ight)+frac 1 6 left(A_1(x)^3-3left(A_1(x)A_2(x)-A_3(x) ight)-A_3(x) ight) $$
代码实现
全家桶板子真好用
1 #include <bits/stdc++.h> 2 3 const int G=3; 4 const int DFT=1; 5 const int IDFT=-1; 6 const int MAXN=550000; 7 const int MOD=998244353; 8 const int INV2=(MOD+1)>>1; 9 const int PHI=MOD-1; 10 11 typedef std::vector<int> Poly; 12 13 Poly Sqrt(Poly); 14 void Read(Poly&); 15 Poly Inverse(Poly); 16 Poly Ln(const Poly&); 17 Poly Exp(const Poly&); 18 void Print(const Poly&); 19 void NTT(Poly&,int,int); 20 Poly Pow(const Poly&,int); 21 Poly Integral(const Poly&); 22 Poly Derivative(const Poly&); 23 Poly operator*(int,Poly); 24 Poly operator*(Poly,Poly); 25 Poly operator/(Poly,Poly); 26 Poly operator%(Poly,Poly); 27 Poly operator+(const Poly&,const Poly&); 28 Poly operator-(const Poly&,const Poly&); 29 30 int w[MAXN]; 31 int rev[MAXN]; 32 33 int NTTPre(int); 34 int Pow(int,int,int); 35 36 int main(){ 37 int n; 38 scanf("%d",&n); 39 int maxv=0; 40 for(int i=0;i<n;i++){ 41 scanf("%d",w+i); 42 maxv=std::max(maxv,w[i]); 43 } 44 Poly s1(maxv+1),s2(maxv*2+1),s3(maxv*3+1); 45 for(int i=0;i<n;i++){ 46 s1[w[i]]=1; 47 s2[2*w[i]]=1; 48 s3[3*w[i]]=1; 49 } 50 Poly ans=s1+INV2*(s1*s1-s2)+Pow(6,MOD-2,MOD)*(s1*s1*s1-3*(s1*s2-s3)-s3); 51 for(int i=1;i<=maxv*3;i++) 52 if(ans[i]) 53 printf("%d %d ",i,ans[i]); 54 return 0; 55 } 56 57 void Read(Poly& a){ 58 for(auto& i:a) 59 scanf("%d",&i); 60 } 61 62 void Print(const Poly& a){ 63 for(auto i:a) 64 printf("%d ",i); 65 puts(""); 66 } 67 68 Poly operator*(int k,Poly a){ 69 for(auto& i:a) 70 i=1ll*k*i%MOD; 71 return a; 72 } 73 74 Poly Pow(const Poly& a,int k){ 75 Poly log=Ln(a); 76 for(auto& i:log) 77 i=1ll*i*k%MOD; 78 return Exp(log); 79 } 80 81 Poly Sqrt(Poly a){ 82 int len=a.size(); 83 if(len==1) 84 return Poly(1,int(sqrt(a[0]))); 85 else{ 86 Poly b=a; 87 b.resize((len+1)>>1); 88 b=Sqrt(b); 89 b.resize(len); 90 Poly inv=Inverse(b); 91 int bln=NTTPre(inv.size()+a.size()); 92 NTT(a,bln,DFT); 93 NTT(inv,bln,DFT); 94 for(int i=0;i<bln;i++) 95 a[i]=1ll*a[i]*INV2%MOD*inv[i]%MOD; 96 NTT(a,bln,IDFT); 97 for(int i=0;i<len;i++) 98 b[i]=(1ll*b[i]*INV2%MOD+a[i])%MOD; 99 return b; 100 } 101 } 102 103 Poly Exp(const Poly& a){ 104 size_t len=1; 105 Poly ans(1,1),one(1,1); 106 while(len<(a.size()<<1)){ 107 len<<=1; 108 Poly b=a; 109 b.resize(len); 110 ans=ans*(one-Ln(ans)+b); 111 ans.resize(len); 112 } 113 ans.resize(a.size()); 114 return ans; 115 } 116 117 Poly Ln(const Poly& a){ 118 Poly ans=Integral(Derivative(a)*Inverse(a)); 119 ans.resize(a.size()); 120 return ans; 121 } 122 123 Poly Integral(const Poly& a){ 124 int len=a.size(); 125 Poly ans(len+1); 126 for(int i=1;i<len;i++) 127 ans[i]=1ll*a[i-1]*Pow(i,MOD-2,MOD)%MOD; 128 return ans; 129 } 130 131 Poly Derivative(const Poly& a){ 132 int len=a.size(); 133 Poly ans(len-1); 134 for(int i=1;i<len;i++) 135 ans[i-1]=1ll*a[i]*i%MOD; 136 return ans; 137 } 138 139 Poly operator/(Poly a,Poly b){ 140 int n=a.size()-1,m=b.size()-1; 141 Poly ans(1); 142 if(n>=m){ 143 std::reverse(a.begin(),a.end()); 144 std::reverse(b.begin(),b.end()); 145 b.resize(n-m+1); 146 ans=Inverse(b)*a; 147 ans.resize(n-m+1); 148 std::reverse(ans.begin(),ans.end()); 149 } 150 return ans; 151 } 152 153 Poly operator%(Poly a,Poly b){ 154 int n=a.size()-1,m=b.size()-1; 155 Poly ans; 156 if(n<m) 157 ans=a; 158 else 159 ans=a-(a/b)*b; 160 ans.resize(m); 161 return ans; 162 } 163 164 Poly operator*(Poly a,Poly b){ 165 int len=a.size()+b.size()-1; 166 int bln=NTTPre(len); 167 NTT(a,bln,DFT); 168 NTT(b,bln,DFT); 169 for(int i=0;i<bln;i++) 170 a[i]=1ll*a[i]*b[i]%MOD; 171 NTT(a,bln,IDFT); 172 a.resize(len); 173 return a; 174 } 175 176 Poly operator+(const Poly& a,const Poly& b){ 177 Poly ans(std::max(a.size(),b.size())); 178 std::copy(a.begin(),a.end(),ans.begin()); 179 for(size_t i=0;i<b.size();i++) 180 ans[i]=(ans[i]+b[i])%MOD; 181 return ans; 182 } 183 184 Poly operator-(const Poly& a,const Poly& b){ 185 Poly ans(std::max(a.size(),b.size())); 186 std::copy(a.begin(),a.end(),ans.begin()); 187 for(size_t i=0;i<b.size();i++) 188 ans[i]=(ans[i]+MOD-b[i])%MOD; 189 return ans; 190 } 191 192 Poly Inverse(Poly a){ 193 int len=a.size(); 194 if(len==1) 195 return Poly(1,Pow(a[0],MOD-2,MOD)); 196 else{ 197 Poly b(a); 198 b.resize((len+1)>>1); 199 b=Inverse(b); 200 int bln=NTTPre(b.size()*2+a.size()); 201 NTT(a,bln,DFT); 202 NTT(b,bln,DFT); 203 for(int i=0;i<bln;i++) 204 b[i]=(2ll*b[i]%MOD-1ll*b[i]*b[i]%MOD*a[i]%MOD+MOD)%MOD; 205 NTT(b,bln,IDFT); 206 b.resize(len); 207 return b; 208 } 209 } 210 211 void NTT(Poly& a,int len,int opt){ 212 a.resize(len); 213 for(int i=0;i<len;i++) 214 if(rev[i]>i) 215 std::swap(a[i],a[rev[i]]); 216 for(int i=1;i<len;i<<=1){ 217 int step=i<<1; 218 int wn=Pow(G,(PHI+opt*PHI/step)%PHI,MOD); 219 for(int j=0;j<len;j+=step){ 220 int w=1; 221 for(int k=0;k<i;k++,w=1ll*w*wn%MOD){ 222 int x=a[j+k]; 223 int y=1ll*a[j+k+i]*w%MOD; 224 a[j+k]=(x+y)%MOD; 225 a[j+k+i]=(x-y+MOD)%MOD; 226 } 227 } 228 } 229 if(opt==IDFT){ 230 int inv=Pow(len,MOD-2,MOD); 231 for(int i=0;i<len;i++) 232 a[i]=1ll*a[i]*inv%MOD; 233 } 234 } 235 236 int NTTPre(int n){ 237 int bln=1,bct=0; 238 while(bln<n){ 239 bln<<=1; 240 ++bct; 241 } 242 for(int i=0;i<bln;i++) 243 rev[i]=(rev[i>>1]>>1)|((i&1)<<(bct-1)); 244 return bln; 245 } 246 247 inline int Pow(int a,int n,int p){ 248 int ans=1; 249 while(n>0){ 250 if(n&1) 251 ans=1ll*a*ans%p; 252 a=1ll*a*a%p; 253 n>>=1; 254 } 255 return ans; 256 }
