Submission #341882

#	Time	Username	Problem	Language	Result	Execution time	Memory
341882		Redhood	Intergalactic ship (IZhO19_xorsum)	C++14	53 / 100	2085 ms	4580 KiB

xorsum

#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 = 1e5 + 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;

}
int both[BT][BT][4];
int fir[BT][2];


/// lulz
int sec[BT][2];
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;


    auto add = [&](int ind  ,int val){
//        if(lines[ind].fi > i || lines[ind].se < j)
//            return;
        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]+=val;
        }
    };
    auto addFir = [&](int ind , int val){
        for(int b1=0;b1<BT;++b1){
            int bit1;
            bit1 = ((1 << b1) & X[ind]) > 0;
            fir[b1][bit1]+=val;
        }
    };
    auto addSec = [&](int ind , int val){
        for(int b1=0;b1<BT;++b1){
            int bit1;
            bit1 = ((1 << b1) & X[ind]) > 0;
            sec[b1][bit1]+=val;
        }
    };

    for(int i = 0 ; i < n; ++i){
        /// like YO
        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 z = 0;  z < BT; ++z)
            for(int zz = 0 ; zz < 2; ++zz)
                fir[z][zz] = 0;
        for(int z = 0;  z < BT; ++z)
            for(int zz = 0 ; zz < 2; ++zz)
                sec[z][zz] = 0;

        vector < vector < int > > del(n + 1) , ADD(n + 1) , DEL(n + 1);
        int CNTBOTH = 0;
        for(int j = 0 ; j  < len(lines); ++j){
            if(lines[j].fi <= i && lines[j].se >= i){
                add(j , +1);
                CNTBOTH++;
                del[lines[j].se+1].pb(j);
            }
        }

        /// calculate SEC
        for(int ind = 0 ; ind < len(lines); ++ind){
            if(lines[ind].fi > i)
                ADD[lines[ind].fi].pb(ind) , DEL[lines[ind].se+1].pb(ind);
        }
        for(int j = i; j < n; ++j){

            for(auto u : ADD[j])
                addSec(u , +1);
            for(auto u : DEL[j])
                addSec(u , -1);
            for(auto u : del[j]){
                add(u , -1);
                addFir(u , +1);
                CNTBOTH--;
            }





            int CNTALL = fir[0][0]+fir[0][1]+sec[0][0]+sec[0][1]+CNTBOTH;
            int nowhere = q - CNTALL;



            /// 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 = 1ll*pw2[fir[B1][0]]*CHOOSE[fir[B1][1]][bit1^BIT1]%mod;
                        for(int bit2=0;bit2<=1;++bit2){

                            int cur2 = 1ll*pw2[sec[B2][0]]*CHOOSE[sec[B2][1]][bit2^BIT2]%mod;
                            /// 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 / 4
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 0 / 9
• Subtask 5: 8 / 8
• Subtask 6: 11 / 11
• Subtask 7: 19 / 19
• Subtask 8: 0 / 30
• Subtask 9: 0 / 8