Submission #651216

#	Time	Username	Problem	Language	Result	Execution time	Memory
651216		Astrayt	Intergalactic ship (IZhO19_xorsum)	C++17	17 / 100	2071 ms	2772 KiB

xorsum

//君の手を握ってしまったら
//孤独を知らないこの街には
//もう二度と帰ってくることはできないのでしょう
//君が手を差し伸べた 光で影が生まれる
//歌って聞かせて この話の続き
//連れて行って見たことない星まで
//さユリ - 花の塔
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define starburst ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pii pair<int,int>
#define pb push_back
#define ff first
#define ss second
#define N 100005

struct qry{
    int l, r, x;
};

void solve(){
    int n, ans = 0, mod = 1e9 + 7; cin >> n;
    vector<int> v(n);
    for(auto &x:v) {
        cin >> x;
    }
    int q; cin >> q;
    vector<qry> Q(q);
    for(auto &qq:Q){
        cin >> qq.l >> qq.r >> qq.x;
        qq.l--; qq.r--;
    }
    for(int s = 0; s < (1<<q); ++s){
        vector<int> tmp = v;
        for(int i = 0; i < q; ++i){
            auto qq = Q[i];
            if(s & (1 << i)){
                for(int j = qq.l; j <= qq.r; ++j){
                    tmp[j] ^= qq.x;
                }
            }
        }
        vector<int> p(1, 0), p2, p3;
        for(int i = 0; i < n; ++i){
            p.pb(tmp[i] + p[i]);
            p.back() %= mod;
        }
        p2 = p3 = p;
        for(int i = 1; i <= n; ++i){
            p2[i] = p2[i] + p2[i - 1];
            p3[i] = p3[i] * p3[i];
            p3[i] %= mod, p2[i] %= mod;
            p3[i] = p3[i - 1] + p3[i];
            p3[i] %= mod;
        }
        for(int i = 1; i <= n; ++i){
            ans = (ans + i * p[i] % mod * p[i]) % mod;
            ans = (ans - 2 * p[i] % mod * p2[i - 1] % mod) % mod;
            ans = (ans + p3[i - 1]) % mod;
        }
    }
    cout << (ans + mod) % mod;
}

signed main(){
    starburst
    int t = 1; //cin >> t;
    while(t--) solve();
}

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