oj.uz

Submission #341872

# Submission time Handle Problem Language Result Execution time Memory
341872 2020-12-31T10:52:51 Z Redhood Intergalactic ship (IZhO19_xorsum) C++14
17 / 100
 2000 ms 3808 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define len(x) (int)(x).size()
#define pb push_back
#define p2(x) (x)*(x)
#define all(x) (x).begin() , (x).end()
#define mkp make_pair


//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("-O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long double ld;
typedef long long ll;

#define int long long
const int BT = 8;
const int mod = (int)1e9 + 7;
const int N = 1001;
const int NN = 1e3 + 10;
int  fact[NN] , pw2[NN] , CHOOSE[NN][2];
int binpow(int a , int b){
    if(b == 0)
        return 1;
    int ans = binpow(a , b >> 1);
    ans = (1ll * ans * ans) % mod;
    if(b & 1)
        ans = (1ll * ans * a) % mod;
    return ans;
}
int INV(int x){
    return binpow(x , mod-2);
}
void md(int &a){
    a %= mod;
    if(a >= mod)
        a-=mod;
}
void prep(){
    fact[0] = 1;
    for(int i = 1; i < NN; ++i)
        fact[i] = (1ll * fact[i-1] * i) % mod;
    pw2[0] = 1;
    for(int i =1;  i < NN; ++i)
        pw2[i] = (1ll * pw2[i-1] * 2) % mod;
    CHOOSE[0][0] = 1;
    for(int i = 1; i <  NN; ++i){
        CHOOSE[i][0] = (CHOOSE[i-1][0] + CHOOSE[i-1][1]);
        md(CHOOSE[i][0]);
        CHOOSE[i][1] = (CHOOSE[i-1][1] + CHOOSE[i-1][0]);
        md(CHOOSE[i][1]);
    }
}
int Cnk(int n , int k){
    if(k == 0)
        return 1;
    return (1ll * fact[n] * (INV(fact[k]))%mod * INV(fact[n-k])%mod);
}

void brute(vector < int > &a , vector < pair < int , int > > &lines , vector < int > &X){
    int answer = 0;
    int S2 = 0 , Mult = 0;
    for(int msk = 0 ; msk < (1 << len(lines)); ++msk){
        vector < int > nw = a;
        for(int j = 0 ; j < len(lines); ++j){
            if((1 << j) & msk){
                for(int f = lines[j].fi; f <= lines[j].se; ++f)
                    nw[f] ^= X[j];
            }
        }
        for(int f = 0 ; f < len(a); ++f)
            S2 += (f + 1) * (len(a) - f) * nw[f] * nw[f];
        for(int f = 0 ; f < len(a); ++f)
            for(int j = f + 1; j < len(a); ++j)
                Mult +=2 * (f + 1) * (len(a) - j) * nw[f] * nw[j];
        for(int f = 0 ; f < len(a); ++f){
            int cursum = 0;
            for(int z = f; z < len(a); ++z){
                cursum += nw[z] , md(cursum);
                answer += 1ll * cursum * cursum % mod;
                md(answer);
            }
        }
    }
    #ifdef LOCAL
        cout << " BRUTE ";
    #endif // LOCAL
    cout << S2 << ' ' << Mult << ' ';
    cout << answer;

}
signed main()
{
    prep();
    ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
    int n;
    cin >> n;
    vector < int > a(n);
    for(auto &i : a)cin >> i;
    int q;
    cin >> q;


    vector < pair < int , int > > lines;
    vector < int > X;
    for(int i = 0 ; i < q; ++i){
        int l , r , x;
        cin >> l >> r >> x;
        --l , --r;
        lines.pb({l , r});
        X.pb(x);
    }

//    brute(a , lines , X);
//    cout << endl;
    int Sin2 = 0;


    int Smult = 0;
    for(int i = 0 ; i < n; ++i){
        for(int j = i; j < n; ++j){

            int fir[BT][2] , sec[BT][2] , nowhere = 0;

            for(int z = 0 ; z < BT; ++z)
                for(int zz = 0; zz < 2; ++zz)
                    fir[z][zz] = sec[z][zz] = 0;

            for(int ind = 0 ; ind < len(lines); ++ind){
                if(lines[ind].fi <= i && lines[ind].se >= j)
                        continue;

                for(int b = 0 ; b < BT; ++b){
                    int bit = ((1 << b) & X[ind]) > 0;
                    if(lines[ind].fi <= i && lines[ind].se >= i)
                        fir[b][bit]++;
                    if(lines[ind].fi <= j && lines[ind].se >= j)
                        sec[b][bit]++;
                }
                int bad = 0;
                if(lines[ind].fi <= i && lines[ind].se >= i)
                    bad += 0;
                else bad += 1;
                if(lines[ind].fi <= j && lines[ind].se >= j)
                    bad += 0;
                else bad += 1;
                if(bad == 2){
                    nowhere++;
                }
            }
            int both[BT][BT][4];


            for(int z = 0 ; z < BT; ++z)
                for(int zz = 0 ; zz < BT; ++zz)
                    for(int zzz = 0; zzz < 4; ++zzz)
                            both[z][zz][zzz]= 0;

            for(int ind = 0 ;  ind < len(lines); ++ind){
                if(lines[ind].fi > i || lines[ind].se < j)
                    continue;
                for(int b1=0;b1<BT;++b1)
                for(int b2=0;b2<BT;++b2){
                    int bit1,bit2;
                    bit1 = ((1 << b1) & X[ind]) > 0;
                    bit2 = ((1 << b2) & X[ind]) > 0;
                    both[b1][b2][(bit1<<1)|bit2]++;
                }
            }



            /// it's dp motherfuckaaa


            for(int B1=0;B1<BT;++B1){
                for(int B2=0;B2<BT;++B2){
                    /// okay
                    /// omg that's strange task
                    /// weird
                    /// lulz okay

                    int dp[2][4];
                    int bt = 0;
                    fill(dp[0], dp[0]+4 , 0);
                    dp[0][0] = 1;
                    for(int msk = 0; msk < 4; ++msk){
                        /// lulz okay
                        bt ^= 1;
                        fill(dp[bt] , dp[bt] + 4 , 0);
                        for(int prvmsk = 0; prvmsk < 4; ++prvmsk){
                            dp[bt][prvmsk] += (1ll * dp[bt^1][prvmsk] * CHOOSE[both[B1][B2][msk]][0]) % mod;
                            md(dp[bt][prvmsk]);
                            dp[bt][prvmsk^msk] += (1ll * dp[bt^1][prvmsk] * CHOOSE[both[B1][B2][msk]][1]) % mod;
                            md(dp[bt][prvmsk^msk]);
                        }
                    }
                    int BIT1 , BIT2;
                    BIT1 = ((1 << B1) & a[i]) > 0;
                    BIT2 = ((1 << B2) & a[j]) > 0;
                    for(int bit1=0;bit1<=1;++bit1){
                        int cur1 = pw2[fir[B1][0]]*CHOOSE[fir[B1][1]][bit1^BIT1];
                        for(int bit2=0;bit2<=1;++bit2){

                            int cur2 = pw2[sec[B2][0]]*CHOOSE[sec[B2][1]][bit2^BIT2];
                            /// and yo
                            /// lul from both we need bit1^1 , bit2^1

                            int that = 1ll*pw2[nowhere]*1ll*(i+1)%mod*(n-j)%mod*cur1%mod*cur2%mod*dp[bt][((bit1^1)<<1)|(bit2^1)]%mod*(1<<B1)%mod*(1<<B2)%mod;
                            if(i == j)
                                Sin2 += that , md(Sin2);
                            else
                                Smult += that , md(Smult);
//                            if(i == 0 && j == 1 && max(B1,B2) < 2){
//                                cout << " BIT'S \n";
//                                cout << B1 << ' ' << bit1 << '\n';
//                                cout << B2 << ' ' << bit2 << '\n';
//
//                                cout << nowhere << '\n';
//                                cout << cur1 << ' ' << cur2 << ' ' << dp[bt][((bit1^1)<<1)|(bit2^1)] << '\n';
//                                cout << " XM " << pw2[sec[B1][0]] << ' ' << CHOOSE[sec[B2][1]][bit2^BIT2] << ' ' << BIT2 << endl;
//                                cout <<  " THAT " << that << endl;
//                            }
                        }
                    }
                }
            }
        }
    }
//    cout << " YO " << Sin2 << endl;
    int answer = (1ll*Sin2 + 1ll*Smult*2)%mod;
    cout << answer;
//    assert(answer != 52);
    return 0;
}
/*
3
1 2 3
3
2 3 1
1 2 4
1 3 7


2
1 2
2
1 2 4
2 2 1



*/

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 72 ms 492 KB Output is correct
7 Correct 69 ms 364 KB Output is correct
8 Correct 73 ms 424 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2088 ms 3808 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2083 ms 364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 364 KB Output is correct
2 Correct 7 ms 364 KB Output is correct
3 Correct 7 ms 364 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 364 KB Output is correct
2 Correct 7 ms 364 KB Output is correct
3 Correct 7 ms 364 KB Output is correct
4 Incorrect 120 ms 748 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 72 ms 492 KB Output is correct
7 Correct 69 ms 364 KB Output is correct
8 Correct 73 ms 424 KB Output is correct
9 Correct 7 ms 364 KB Output is correct
10 Correct 7 ms 364 KB Output is correct
11 Correct 7 ms 364 KB Output is correct
12 Incorrect 132 ms 364 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 72 ms 492 KB Output is correct
7 Correct 69 ms 364 KB Output is correct
8 Correct 73 ms 424 KB Output is correct
9 Correct 7 ms 364 KB Output is correct
10 Correct 7 ms 364 KB Output is correct
11 Correct 7 ms 364 KB Output is correct
12 Incorrect 120 ms 748 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 72 ms 492 KB Output is correct
7 Correct 69 ms 364 KB Output is correct
8 Correct 73 ms 424 KB Output is correct
9 Execution timed out 2088 ms 3808 KB Time limit exceeded
10 Halted 0 ms 0 KB -