C++(g++ 7.5.0) 解法, 执行用时: 1588ms, 内存消耗: 100136K, 提交时间: 2022-11-04 20:49:08

#include<bits/stdc++.h>
using namespace std;
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define until(F) while(!(F))
#define ll long long
#define mod 1000000007
#define N 1024
#define M 10
#define invN 71289063
int n,Q,a[N];
int bl[N],pos[N],k;
struct FF{
	ll f[N];
	void FWT(){
		fr(j,0,M-1){
			fr(i,0,N-1){
				if(i>>j&1){
					ll x=f[i^(1<<j)],y=f[i];
					f[i^(1<<j)]=(x+y)%mod;
					f[i]=(x+mod-y)%mod;
				}
			}
		}
	}
}b[N],tmp[105],S1[105][M][M],S2[105][105];
FF mul(FF A,FF B){
	FF C;
	fr(i,0,N-1)C.f[i]=A.f[i]*B.f[i]%mod;
	return C;
}
void build(){
	for(int l=1,r;l<=n;l=r+1){
		r=min(n,l+M-1);
		pos[++k]=l;
		fr(i,l,r){
			bl[i]=k;
			S1[k][i-l][i-l]=b[i];
			fr(j,i+1,r){
				S1[k][i-l][j-l]=mul(S1[k][i-l][j-l-1],b[j]);
			}
		}
	}
//	printf("orz:%d\n",k);
	pos[k+1]=n+1;
	fr(i,1,k)tmp[i]=S1[i][0][pos[i+1]-pos[i]-1];
	fr(i,1,k){
		S2[i][i]=tmp[i];
		fr(j,i+1,k)S2[i][j]=mul(S2[i][j-1],tmp[j]);
	}
}
void query(int l,int r,int s){
	int pl=bl[l],pr=bl[r];
	FF res;
	if(pl==pr){
		res=S1[pl][l-pos[pl]][r-pos[pl]];
	}
	else{
		res=mul(S1[pl][l-pos[pl]][pos[pl+1]-pos[pl]-1],S1[pr][0][r-pos[pr]]);
		if(pl<pr-1)res=mul(res,S2[pl+1][pr-1]);
	}
	ll ans=0;
	fr(i,0,N-1){
		if(__builtin_popcount(i&s)&1)ans-=res.f[i];
		else ans+=res.f[i];
	}
	ans=(ans%mod+mod)%mod;
	printf("%lld\n",ans*invN%mod);
}
int main(){
//	return system("fc my.out .out"),0;
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	scanf("%d%d",&n,&Q);
	fr(i,1,n)scanf("%d",&a[i]);
	fr(i,1,n){
		fr(j,0,a[i])b[i].f[j]=1;
		b[i].FWT();
	}
	build();
//	FF res=S1[2][0][1];
//	res.FWT();
//	fr(i,0,15)printf("%lld ",res.f[i]*invN%mod);puts("");
	while(Q--){
		int l,r,s;
		scanf("%d%d%d",&l,&r,&s);
		query(l,r,s); 
	}
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 1631ms, 内存消耗: 27052K, 提交时间: 2022-11-05 10:50:37

#include<iostream>
#include<vector>
using namespace std;

#define int long long
const int N=1055,mod=1e9+7;

int n,q;
int a[N][N];
pair<int,int> f[N][N];

int ksm(int a,int b)
{
    int ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ans;
}

void XOR(int *a,int n,int x)
{
    for(int o=2,k=1;o<=n;o<<=1,k<<=1)
    {
        for(int i=0;i<n;i+=o) 
         for(int j=0;j<k;j++)
          {
              int x=a[i+j],y=a[i+j+k];
              a[i+j]=(x+y)%mod;
              a[i+j+k]=(x-y+mod)%mod;
          }
    }
}

int calc(int l,int r,int i)
{
    if(f[r][i].second>f[l-1][i].second) return 0;
    return f[r][i].first*ksm(f[l-1][i].first,mod-2)%mod;
}

signed main()
{
    cin>>n>>q;
    for(int i=0;i<1024;i++) f[0][i]={1,0};
    for(int i=1,j;i<=n;i++) 
    {
        cin>>j;
        for(int s=0;s<=j;s++) a[i][s]=1;
        XOR(a[i],1024,1);
        for(int s=0;s<1024;s++) 
        {
            f[i][s]=f[i-1][s];
            if(a[i][s]==0) f[i][s].second++;
            else f[i][s].first=(f[i][s].first*a[i][s])%mod;
        }
    }
    int d=ksm(1024,mod-2);
    while(q--)
    {
        int l,r,s;
        cin>>l>>r>>s;
        int ans=0;
        for(int i=0;i<1024;i++) 
        {
            if(__builtin_popcount(i&s)&1) ans=(ans-calc(l,r,i)+mod)%mod;
            else ans=(ans+calc(l,r,i))%mod;
        }
        cout<<ans*d%mod<<'\n';
    }
    return 0;
}