Submission #1035432

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035432		alexander707070	Intergalactic ship (IZhO19_xorsum)	C++14	0 / 100	65 ms	9048 KiB

xorsum

#include<bits/stdc++.h>
#define MAXN 1007
using namespace std;

const int maxa=128;
const long long mod=1e9+7;

int n,a[MAXN],q,l,r,x;
long long ways[MAXN][150];
int br[150];

vector<int> qs[MAXN];

long long dp[150][150],power[100007];
long long cnt[MAXN][MAXN],ans;
vector<long long> poss[MAXN];

void calcdp(){
    dp[0][0]=1;

    for(int pos=1;pos<=maxa;pos++){
        for(int xorr=0;xorr<maxa;xorr++){
            if(br[pos-1]==0)dp[pos][xorr]=dp[pos-1][xorr];
            else dp[pos][xorr]=(dp[pos-1][xorr] + dp[pos-1][xorr^(pos-1)]*power[br[pos-1]-1] )%mod;
        }
    }
}

long long calc(int x,int y){
    long long res=0;
    if(x==y){
        for(long long t:poss[x]){
            res+=((ways[x][t]*(t*t))%mod) * cnt[x][x];
            res%=mod;
        }
    }else{
        for(long long t:poss[x]){
            for(long long s:poss[y]){
                res+=((ways[x][t]*ways[y][s])%mod) * (((t*s) * cnt[x][y])%mod);
                res%=mod;
            }
        }
    }

    return res;
}

int main(){

    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }

    for(int i=1;i<=n;i++){
        for(int f=i;f<=n;f++){
            cnt[i][f]=i*(n-f+1);
            if(i!=f)cnt[i][f]*=2;
        }
    }

    cin>>q;
    for(int i=1;i<=q;i++){
        cin>>l>>r>>x;
        qs[l].push_back(x);
        qs[r+1].push_back(-x);
    }

    power[0]=1;
    for(int i=1;i<=q;i++){
        power[i]=(power[i-1]*2)%mod;
    }

    for(int i=1;i<=n;i++){
        for(int f:qs[i]){
            if(f>0)br[f]++;
            else br[-f]--;
        }

        calcdp();

        for(int f=0;f<maxa;f++){
            ways[i][f]=dp[maxa][a[i]^f];
            if(ways[i][f]>0)poss[i].push_back(f);
        }
    }

    for(int i=1;i<=n;i++){
        for(int f=i;f<=n;f++){
            ans+=calc(i,f);
            ans%=mod;
        }
    }

    cout<<ans<<"\n";
 
    return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 5
• Subtask 3: 0 / 6
• Subtask 4: 0 / 9
• Subtask 5: 0 / 8
• Subtask 6: 0 / 11
• Subtask 7: 0 / 19
• Subtask 8: 0 / 30
• Subtask 9: 0 / 8