5651 [51nod1348]乘积之和

题意：

给长度为\(n\)的数列\(a_i\),\(q\)个询问每次给\(k\)，问不同方案\(k\)个数乘起来乘积的和。（mod=1e5+4）

思路：

从乘起来的和切入容易想到ntt吧。问题是怎么卷。
ntt，ftt只能解决两个多项式相卷的问题。
因此用分治（二分），可解决问题。
分治是递归的，会存在状态怎么存的问题，这个一定要想清楚？不能一个变量赋值后递归下去又被改了。
这里可以存\(f[i][dep]\)在正常状态上加一维\(O(logn)\)的层数，这样就不会冲突。
然后毒瘤出题人给的是\(100005\)这种坏模数。
我按照题解学写了一下双模数，正常\(10^5\)保证正确应该用三模数才稳妥，这个做法正确的原理是最终的值不超过三个模数的积（相当于准确值没有取模）。
还是有一个坑点是学CRT的漏洞：就是处理出来的余数一定要是最小非负数。之前因为是负数G了好几波。然后先合并出模\(p_0*p_1\)的余数，再去模\(100005\)
模数很大时记得用龟速乘。

code:

#include
using namespace std;
typedef long long ll;
const int N=3e5+5;
const int M=21;
const ll mod=100003;
ll val[N],f[N][M],P[]={998244353,1004535809},inv[]={669690699,332747959};
const ll MOD=P[0]*P[1]; 
ll x[N],y[N],z[N],w[N];
int up,l,rev[N];

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<0)b=(b+MOD)%MOD;ll sum=0;for(;b;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[i],a[rev[i]]);
	for(int mid=1;mid>1]>>1)|((i&1)<<(l-1));}
}

void Mul(ll *a,ll *b) {
	NTT(a,-1);
	NTT(b,-1);
	
	for(int i=0;i>1,len=r-l+1;
	int lL=_CDQ(l,mid,dep+1);
	for(int i=0;i=lL) {f[i][dep]=0;}
		if(i>=lR) {y[i]=0;}
		z[i]=x[i]=f[i][dep];w[i]=y[i];
	}
	p=P[0];Mul(x,y);
	p=P[1];Mul(z,w);
	//CRT
	for(int i=0;i