网站如何做才能被百度等收录,网站建设理论基础,如何利用模板做网站视频,动漫制作专业简历传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
求aaa的所有子序列的和的乘积。
思路#xff1a;
看到suma≤1e5sum_a\le1e5suma≤1e5#xff0c;这应该会给我们提示#xff0c;但是我没看到。 我们可以记cntxcnt_xcntx表示和为xxx的子序列有cnt…传送门
文章目录题意思路题意
求aaa的所有子序列的和的乘积。
思路
看到suma≤1e5sum_a\le1e5suma≤1e5这应该会给我们提示但是我没看到。 我们可以记cntxcnt_xcntx表示和为xxx的子序列有cntxcnt_xcntx个那么答案就是∏xcntx\prod x^{cnt_x}∏xcntx。 考虑求cntxcnt_xcntx我们定义f[i][j]f[i][j]f[i][j]表示前iii个数和为jjj的数有多少显然可以n2n^2n2转移。 考虑这是一个经典问题将每一项aia_iai写成多项式1xai1x^{a_i}1xai那么nnn个多项式乘起来之后指数为xxx系数为cntxcnt_xcntx但是这个过程仍然是n2n^2n2的。 由于我们将其转换成多项式了而多项式相乘是无序的所以可以用分治来优化这个过程每层用FFTFFTFFT来计算即可。又因为要取模所以可以用三模NTTNTTNTT或者拆系数FFTFFTFFT这里采用FFTFFTFFT即可。注意这里多项式的取模应该是mod−1mod-1mod−1因为其实际是指数我们要用费马小定理降幂。 在就是实现的时候一些小技巧了比如我们需要返回一个多项式直接返回肯定炸掉了我们可以返回一个指针就可以完美的返回一个多项式了。 最后直接算一下答案即可。
// Problem: K - Yiwen with Formula
// Contest: Virtual Judge - 2021多校第7场补题
// URL: https://vjudge.net/contest/452480#problem/K
// Memory Limit: 524 MB
// Time Limit: 16000 ms
//
// Powered by CP Editor (https://cpeditor.org)#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod998244353,INF0x3f3f3f3f,P115;
const double eps1e-6;int n,m;
int a[N];struct MTT {long double PIacos(-1);int rev[N];int bit,limit;struct Complex {long double x,y;void init() { xy0; }Complex operator (const Complex t) const { return {xt.x,yt.y}; }Complex operator - (const Complex t) const { return {x-t.x,y-t.y}; }Complex operator * (const Complex t) const { return {x*t.x-y*t.y,x*t.yy*t.x}; } }p1[N],p2[N],g[N];void init(int n,int m) {int xnm; bit0;while((1bit)x) bit;limit1bit;for(int i0;ilimit;i) rev[i](rev[i1]1)|((i1)(bit-1));}void fft(Complex a[],int inv) {for(int i0;ilimit;i) if(irev[i]) swap(a[i],a[rev[i]]);for(int mid1;midlimit;mid1) {Complex w1Complex({cos(PI/mid),inv*sin(PI/mid)});for(int i0;ilimit;imid*2) {Complex wkComplex({1,0});for(int j0;jmid;j,wkwk*w1) {Complex xa[ij],ywk*a[ijmid];a[ij]xy; a[ijmid]x-y;}}}}int mul(int *as,int *a,int n,int *b,int m,int mod) {for(int i0;in;i) {int xa[i];int aax15,bbx0x7fff;p1[i]{(long double)aa,(long double)bb};p2[i]{(long double)aa,-(long double)bb};}for(int i0;im;i) {int xb[i];int aax15,bbx0x7fff;g[i]{(long double)aa,(long double)bb};}init(n,m);fft(p1,1); fft(p2,1); fft(g,1);for(int i0;ilimit;i) g[i].x/limit,g[i].y/limit;for(int i0;ilimit;i) p1[i]p1[i]*g[i],p2[i]p2[i]*g[i];fft(p1,-1); fft(p2,-1);for(int i0;imn;i) {LL ans0,a1b10,a2b20,a1b20,a2b10;a1b1(long long)floor((p1[i].xp2[i].x)/20.49)%mod;a1b2(long long)floor((p1[i].yp2[i].y)/20.49)%mod;a2b1((long long)floor(p1[i].y0.49)-a1b2)%mod;a2b2((long long)floor(p2[i].x0.49)-a1b1)%mod;ans(((((a1b115)%mod(a1b2a2b1))%mod)15)%moda2b2)%mod;ansmod; ans%mod;as[i]ans;}for(int i0;ilimit;i) p1[i].init(),p2[i].init(),g[i].init();return nm;}
}MT;int all,al[N*4];struct Com {int *a,len;void init(int l) {aalall; lenl; alll;for(int i0;ilen;i) a[i]0;a[0]; a[len-1];}void mul(Com x) {lenMT.mul(a,a,len,x.a,x.len,mod-1);}
};Com solve(int l,int r) {Com ans;if(lr) {return ans.init(a[l]1),ans;} else {int mid(lr)1;anssolve(l,mid);ans.mul(solve(mid1,r));return ans;}
}LL qmi(LL a,LL b) {LL ans1;while(b) {if(b1) ansans*a%mod;aa*a%mod;b1;}return ans%mod;
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);int _; scanf(%d,_);while(_--) {scanf(%d,n); all0; int miINF;for(int i1;in;i) scanf(%d,a[i]),mimin(mi,a[i]);if(mi0) {puts(0);continue;}Com nowsolve(1,n);LL ans1;for(int i2;inow.len;i) (ans*qmi(i,now.a[i]))%mod;printf(%lld\n,ans);}return 0;
}
/**/
