题解 | E题解

感谢牛客神机：此题可暴力FWT通过：

以下为做法：

1.枚举$ll$，递增$rr$，跑的时候把$fwtfwt$数组乘起来：$O(\frac{n\cdot n}{2}\ast 1024)\approx 1e9O(\backslash frac\{n\; \backslash cdot\; n\}\{2\}*1024)\backslash approx1e9$

2.到有询问的$ll$，$rr$，$ifwtifwt$回来:$O(q\ast 10\ast 1024)\approx 1e9O(q*10*1024)\backslash approx1e9$

3.适当卡常，我要跑$2400ms2400ms$

4.$code:code:$

#include<bits/stdc++.h>

#define db double
#define lp long long
#define ulp unsigned lp

#define pa pair < lp , lp >
#define fi first
#define se second
#define mp make_pair

#define vc vector
#define pb push_back

#define is insert

#define rp(i,x,y) for(lp i=(x);i<=(y);i++)
#define pr(i,x,y) for(lp i=(x);i>=(y);i--)

using namespace std;

inline lp gi(){
    lp r=0,f=0;char c=getchar();
    while(!isdigit(c))f=c=='-',c=getchar();
    while(isdigit(c))r=r*10+c-48,c=getchar();
    return f?-r:r;
}

inline lp mi(lp a,lp b){return a<b?a:b;}
inline lp ma(lp a,lp b){return a>b?a:b;}

const lp ml=1029;
const lp mk=1e5+111;
const lp mo=1e9+7;
const lp inv2=500000004;

lp n,Q;

lp x[ml];
lp f[ml],g[ml];
lp a[ml],b[ml][ml],ans[mk];

vc<pa>seq[ml][ml];

inline void add(lp &a,lp b){a+=b;if(a>=mo)a-=mo;}

void Xor(lp *f,lp type=1){
    if(type==1){
    	for(lp o=2,k=1;o<=1024;o<<=1,k<<=1)
    		for(lp i=0;i<1024;i+=o)
    			for(lp j=0;j<k;j++)
    				add(f[i+j],f[i+j+k]),
    				f[i+j+k]=(f[i+j]+2*(mo-f[i+j+k]))%mo;
    }
    else{
        for(lp o=2,k=1;o<=1024;o<<=1,k<<=1)
    		for(lp i=0;i<1024;i+=o)
    			for(lp j=0;j<k;j++){
    				f[i+j]=(f[i+j]+f[i+j+k])*inv2%mo;
    				f[i+j+k]=(f[i+j]+mo-f[i+j+k])%mo;
    			}
    }
}

int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin>>n>>Q;
	//rp(i,1,n)x[i]=1000;
	rp(i,1,n)x[i]=gi();
	rp(i,1,Q){lp l=gi(),r=gi(),s=gi();seq[l][r].pb({s,i});}
	
	rp(i,0,1024){
		rp(j,0,i)b[i][j]=1;
		Xor(b[i]);
	}
	
	rp(l,1,n){
		lp fl=0;
		rp(r,l,n)if(seq[l][r].size())fl=r;
		if(!fl)continue;
		
		//cout<<l<<'\n';
		rp(i,0,1024)f[i]=0;f[0]=1;
		Xor(f);
		
		rp(r,l,fl){
			rp(i,0,1024)f[i]=f[i]*b[x[r]][i]%mo;
			
			if(seq[l][r].size()){
				rp(i,0,1024)g[i]=f[i];
				Xor(g,0);
			}
			for(pa t:seq[l][r])ans[t.se]=g[t.fi];
		}
		
		
	}
	
	rp(i,1,Q)cout<<ans[i]<<'\n';
    return 0;
}