oj.uz

Submission #1035432

# Submission time Handle Problem Language Result Execution time Memory
1035432 2024-07-26T11:02:02 Z alexander707070 Intergalactic ship (IZhO19_xorsum) C++14
0 / 100
 65 ms 9048 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 3668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 9048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -