Submission #993102

#	Time	Username	Problem	Language	Result	Execution time	Memory
993102		NValchanov	Intergalactic ship (IZhO19_xorsum)	C++17	37 / 100	2058 ms	3532 KiB

xorsum

#include <bits/stdc++.h>

#define endl '\n'

using namespace std;

typedef long long ll;

const ll MAXN = 1e3 + 10;
const ll MAXQ = 1e5 + 10;
const ll MOD = 1e9 + 7;
const ll MAXA = 128;
const ll MAXLOG = 8;

struct upd
{
    ll left, right;
    ll val;

    upd()
    {
        left = right = 1;
        val = 0;
    }

    upd(ll _left, ll _right, ll _val)
    {
        left = _left;
        right = _right;
        val = _val;
    }
};

ll n, q;
ll a[MAXN];
vector < upd > updates;
ll pow2;

void read()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    cin >> q;
    for(int i = 0; i < q; i++)
    {
        ll left, right;
        ll x;

        cin >> left >> right >> x;

        upd u = upd(left - 1, right - 1, x);

        updates.push_back(u);
    }
}

void update(bitset < MAXA >&bs, ll val)
{
    if(bs[bs._Find_first() ^ val])
        return;

    vector < int > to_add;

    for(int i = bs._Find_first(); i < MAXA; i = bs._Find_next(i))
        to_add.push_back(i ^ val);

    for(int i : to_add)
        bs[i] = 1;
}

ll binpow(ll a, ll b)
{
    ll result = 1;

    while(b)
    {
        if(b & 1)
            result = (result * a) % MOD;
        
        a = (a * a) % MOD;
        b /= 2;
    }

    return result;
}

void solve()
{
    pow2 = 1;
    for(int i = 1; i <= q; i++)
    {
        pow2 = (pow2 * 2) % MOD;
    }

    ll ans = 0;

    for(int i = 0; i < n; i++)
    {
        for(int j = i; j < n; j++)
        {
            bitset < MAXA > bs1;
            bitset < MAXA > bs2;
            bitset < MAXA > bs3;

            bs1[a[i]] = bs2[a[j]] = bs3[0] = 1;

            for(int k = 0; k < q; k++)
            {
                bool in1 = false;
                bool in2 = false;

                if(updates[k].left <= i && i <= updates[k].right)
                    in1 = true;

                if(updates[k].left <= j && j <= updates[k].right)
                    in2 = true;

                if(in1 && in2)
                    update(bs3, updates[k].val);
                else if(in1)
                    update(bs1, updates[k].val);
                else if(in2)
                    update(bs2, updates[k].val);
            } 

            ll sum = 0;

            for(int idx1 = bs1._Find_first(); idx1 < MAXA; idx1 = bs1._Find_next(idx1))
            {
                for(int idx2 = bs2._Find_first(); idx2 < MAXA; idx2 = bs2._Find_next(idx2))
                {
                    for(int idx3 = bs3._Find_first(); idx3 < MAXA; idx3 = bs3._Find_next(idx3))
                    {
                        ll cur = ((idx1 ^ idx3) * (idx2 ^ idx3)) % MOD;

                        if(i != j)
                            cur = (cur * 2) % MOD;

                        sum = (sum + cur) % MOD;
                    }
                }
            }
            ll cnt = ((i + 1) * (n - j)) % MOD;
            sum = (sum * cnt) % MOD;
            sum = (sum * pow2) % MOD;

            sum = (sum * (binpow(bs1.count() * bs2.count() * bs3.count(), MOD - 2))) % MOD;

            ans = (ans + sum) % MOD;
        }
    }

    cout << ans << endl;
}

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    read();
    solve();

    return 0;
}

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