首页
关于
笔记
文章
友链

Solution -「CCPC Winter Camp Day 6 A」Convolution

cirnovsky /

§ Description

Link.

给定一个数列 a1,a2,....an\sf a_1,a_2,....a_n，请求出下面这个结果在模 998244353\sf 998244353 下的答案。

∑i=1n∑j=1n2aiaj\sum_{i=1}^{n}\sum_{j=1}^{n}2^{a_i a_j}

§ Solution

这题涉及一个 trick：ij=(i+j2)−(i2)−(j2)\sf ij=\binom{i+j}{2}-\binom{i}{2}-\binom{j}{2}，是 UQ 里面 EI 给我讲的，说明一下。

首先我们令 cai=the number of the occurrences of ai,mx=max⁡{ai}\sf c_{a_{i}}=the~number~of~the~occurrences~of~a_{i},mx=\max\{a_{i}\}。

然后来推式子：

∑i=1n∑j=1n2aiaj=∑i=1mx∑j=1mxcicj2ij=∑i=1mx∑j=1mxcicj2(i+j2)−(i2)−(j2)=∑i=1mx∑j=1mxcicj2(i+j2)2−(i2)2−(j2)=∑i=1mx∑j=1mxcicj2(i+j2)2−(i2)2−(j2)\begin{aligned} \sf\sum_{i=1}^{n}\sum_{j=1}^{n}2^{a_{i}a_{j}}&=\sf\sum_{i=1}^{mx}\sum_{j=1}^{mx}c_{i}c_{j}2^{ij} \\ &=\sf\sum_{i=1}^{mx}\sum_{j=1}^{mx}c_{i}c_{j}2^{\binom{i+j}{2}-\binom{i}{2}-\binom{j}{2}} \\ &=\sf\sum_{i=1}^{mx}\sum_{j=1}^{mx}c_{i}c_{j}2^{\binom{i+j}{2}}2^{-\binom{i}{2}}2^{-\binom{j}{2}} \\ &=\sf\sum_{i=1}^{mx}\sum_{j=1}^{mx}c_{i}c_{j}2^{\binom{i+j}{2}}2^{-\binom{i}{2}}2^{-\binom{j}{2}} \\ \end{aligned}\\

现在我们令 ti=2(i2),iti=2−(i2)\sf t_{i}=2^{\binom{i}{2}},it_{i}=2^{-\binom{i}{2}}。

那么 i+j\sf i+j 那项你就直接拿出来最后单独算即可。

∑i=1n∑j=1n2aiaj=∑i=1mx∑j=1mxcicj2(i+j2)2−(i2)2−(j2)=∑i=1mx∑j=1mxcicjti+jitiitj\begin{aligned} \sf\sum_{i=1}^{n}\sum_{j=1}^{n}2^{a_{i}a_{j}} &=\sf\sum_{i=1}^{mx}\sum_{j=1}^{mx}c_{i}c_{j}2^{\binom{i+j}{2}}2^{-\binom{i}{2}}2^{-\binom{j}{2}} \\ &=\sf\sum_{i=1}^{mx}\sum_{j=1}^{mx}c_{i}c_{j}t_{i+j}it_{i}it_{j} \\ \end{aligned}\\

最后直接算：

∑i=1mx∑j=0mx−1ciitici−jiti−j\sf \sum_{i=1}^{mx}\sum_{j=0}^{mx-1}c_{i}it_{i}c_{i-j}it_{i-j}

卷积 完了。

记住模数非质的时候不一定有逆元啊啊啊啊！！！！

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD=998244353;
void exGCD(LL one,LL ano,LL &x,LL &y)
{
	if(ano==0)	x=1,y=0;
	else	exGCD(ano,one%ano,y,x),y-=(one/ano)*x;
}
LL getInv(LL val,LL _MOD){LL res,w; exGCD(val,_MOD,res,w); return (res%_MOD+_MOD)%_MOD;}
LL fspow(LL bas,LL fur)
{
	LL res=1;
	while(fur)
	{
		if(fur&1)	res=LL(res)*bas%MOD;
		bas=LL(bas)*bas%MOD;
		fur>>=1;
	}
	return (res+MOD)%MOD;
}
LL fac[200010],ifac[200010];
//LL binom(LL n,LL k){return n>=k?LL(fac[n])*ifac[k]%(MOD-1)*ifac[n-k]%(MOD-1):0;}
LL binom(LL n,LL k){return n>=k?LL(n)*(n-1)/2%(MOD-1):0;}
namespace Poly
{
	typedef vector<LL> poly;
	#define len(x) (LL((x).size()))
	LL lim,rev[800010];
	void ntt(poly &f,LL op)
	{
		for(LL i=0;i<lim;++i)	if(i<rev[i])	swap(f[i],f[rev[i]]);
		for(LL len=2;len<=lim;len<<=1)
		{
			LL bas=fspow(op==1?3:332748118,(MOD-1)/len);
			for(LL fr=0;fr<lim;fr+=len)
			{
				LL now=1;
				for(LL ba=fr;ba<fr+(len>>1);++ba,now=LL(now)*bas%MOD)
				{
					LL tmp=LL(now)*f[ba+(len>>1)]%MOD;
					f[ba+(len>>1)]=(f[ba]-tmp+MOD)%MOD;
					f[ba]=(f[ba]+tmp)%MOD;
				}
			}
		}
		if(op==-1)
		{
			LL tmp=getInv(lim,MOD);
			for(LL i=0;i<lim;++i)	f[i]=LL(f[i])*tmp%MOD;
		}
	}
	poly operator*(poly f,poly g)
	{
		LL n=len(f)+len(g)-1; lim=1;
		while(lim<n)	lim<<=1;
		f.resize(lim),g.resize(lim);
		for(LL i=0;i<lim;++i)	rev[i]=(rev[i>>1]>>1)|((i&1)?(lim>>1):0);
		ntt(f,1),ntt(g,1);
		for(LL i=0;i<lim;++i)	f[i]=LL(f[i])*g[i]%MOD;
		ntt(f,-1),f.resize(n);
		return f;
	}
}using namespace Poly;
LL n,mx,c[100010],t[100010],it[100010],ans,ex[200010];
int main()
{
	poly f;
	scanf("%lld",&n);
	for(LL i=1,x;i<=n;++i)	scanf("%lld",&x),mx=max(mx,x),++c[x];
	f.resize(mx+1);
	fac[0]=1;
	for(LL i=1;i<=(mx<<1);++i)	fac[i]=LL(fac[i-1])*i%(MOD-1);
//	for(LL i=0;i<=(mx<<1);++i)	ifac[i]=getInv(fac[i],MOD-1);
//	printf("%lld\n",getInv(fac[2],MOD));
//	printf("(%lld %lld %lld %lld)\n",fac[2],ifac[2],ifac[0],binom(2,2));
	for(LL i=0;i<=mx;++i)	t[i]=fspow(2,binom(i,2));
	for(LL i=0;i<=mx;++i)	it[i]=getInv(t[i],MOD);
//	for(LL i=1;i<=mx;++i)	printf("%lld ",fac[i]); puts("");
//	for(LL i=1;i<=mx;++i)	printf("%lld ",binom(i,2)); puts("");
//	for(LL i=1;i<=mx;++i)	printf("%lld ",LL(i)*(i-1)/2%MOD); puts("");
	for(LL i=0;i<=mx;++i)	f[i]=LL(c[i])*it[i]%MOD;
	for(LL i=1;i<=(mx<<1);++i)	ex[i]=fspow(2,binom(i,2));
	f=f*f;
	for(LL i=0;i<len(f);++i)	ans=(ans+LL(f[i])*ex[i]%MOD)%MOD;
	printf("%lld\n",ans);
	return 0;
}