5651 [51nod1348]乘积之和
题意：给长度为\(n\)的数列\(a_i\),\(q\)个询问每次给\(k\)，问不同方案\(k\)个数乘起来乘积的和。（mod=1e5+4）
思路：
从乘起来的和切入容易想到ntt吧。问题是怎么卷。
ntt，ftt只能解决两个多项式相卷的问题。
因此用分治（二分），可解决问题。
分治是递归的，会存在状态怎么存的问题，这个一定要想清楚？不能一个变量赋值后递归下去又被改了。
这里可以存\(f\)在正常状态上加一维\(O(logn)\)的层数，这样就不会冲突。
然后毒瘤出题人给的是\(100005\)这种坏模数。
我按照题解学写了一下双模数，正常\(10^5\)保证正确应该用三模数才稳妥，这个做法正确的原理是最终的值不超过三个模数的积（相当于准确值没有取模）。
还是有一个坑点是学CRT的漏洞：就是处理出来的余数一定要是最小非负数。之前因为是负数G了好几波。然后先合并出模\(p_0*p_1\)的余数，再去模\(100005\)
模数很大时记得用龟速乘。
code:
#includeusing namespace std;typedef long long ll;const int N=3e5+5;const int M=21;const ll mod=100003;ll val,f,P[]={998244353,1004535809},inv[]={669690699,332747959};const ll MOD=P*P; ll x,y,z,w;int up,l,rev;ll p;ll ksm(ll a,ll b) {ll mul=1;for(;b;b>>=1,a=a*a%p)if(b&1)mul=mul*a%p;return mul;}ll cheng(ll a,ll b) {if(b>=1,a=(a+a)%MOD)if(b&1)sum=(sum+a)%MOD;return sum;}void NTT(ll *a,int op) { for(int i=0;ii)swap(a,a]); for(int mid=1;mid
页:
[1]