oj.uz

Submission #992973

# Submission time Handle Problem Language Result Execution time Memory
992973 2024-06-05T08:42:27 Z danikoynov Intergalactic ship (IZhO19_xorsum) C++14
53 / 100
 908 ms 262144 KB 
#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const ll mod = 1e9 + 7;

const int maxn = 1010;

const int maxbit = 7;
const int maxq = 1e5 + 10;

int n, q;
int a[maxn];

struct query_data
{
    int l, r, x;

    void input()
    {
        cin >> l >> r >> x;
    }
} task[maxq];

bool is_affected(int i, int bit_i, int t)
{
    if (task[t].r < i || task[t].l > i)
        return false;

    if ((task[t].x & (1 << bit_i)) == 0)
        return false;

    return true;
}

ll fac[maxq], inv[maxq];

ll power(ll base, ll st)
{
    ll res = 1;
    while(st > 0)
    {
        if (st % 2 == 1)
            res = (res * base) % mod;

        base = (base * base) % mod;
        st /= 2;
    }
    return res;
}

ll comb(ll from, ll take)
{
    if (take < 0 || take > from)
        return 0;
    return ((fac[from] * inv[take]) % mod * inv[from - take]) % mod;
}

ll pw[maxq];

const int maxmask = (1 << maxbit);
int spot[(1 << maxbit)][maxn][maxn];
int pref[(1 << maxbit)][maxn][maxn];
int ch[maxbit][maxn];

int get_both(int mask, int left, int right)
{
    int cnt = 0;
    for (int i = 1; i <= left; i ++)
    {
        for (int cur : spot[mask][i])
            if (cur >= right)
                cnt ++;
    }
    return cnt;
}
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];
    cin >> q;
    fac[0] = inv[0] = pw[0] = 1;
    for (int i = 1; i < max(q + 1, maxbit * 2); i ++)
    {
        pw[i] = (pw[i - 1] * 2) % mod;
    }


    for (int i = 1; i <= q; i ++)
    {

        fac[i] = (fac[i - 1] * (ll)(i)) % mod;
        inv[i] = power(fac[i], mod - 2);
    }

    for (int i = 1; i <= q; i ++)
    {
        task[i].input();

        for (int bit1 = 0; bit1 < maxbit; bit1 ++)
            for (int bit2 = bit1; bit2 < maxbit; bit2 ++)
            {
                int mask = ((1 << bit1) | (1 << bit2));
                if ((task[i].x & mask) == mask)
                {
                    spot[mask][task[i].l][task[i].r] ++;
                }
            }
    }

    for (int mask = 0; mask < (1 << maxbit); mask ++)
    {
        for (int r = 1; r <= n; r ++)
        {
            for (int l = 1; l <= r; l ++)
            {
                pref[mask][l][r] = pref[mask][l - 1][r] + spot[mask][l][r];
            }
        }
    }
    for (int i = 1; i <= n; i ++)
    {
        for (int bit = 0; bit < maxbit; bit ++)
        {

            for (int j = 1; j <= q; j ++)
            {
                ch[bit][i] += is_affected(i, bit, j);
            }
        }
    }

    ll ans = 0;

    for (int bit_i = 0; bit_i < maxbit; bit_i ++)
    {

        for (int bit_j = 0; bit_j < maxbit; bit_j ++)
        {
            int both = 0;
            int mask =((1 << bit_i) | (1 << bit_j));
            for (int i = 1; i <= n; i ++)
            {
                for (int j = i; j <= n; j ++)
                    both += spot[mask][i][j];

                if (i > 1)
                {
                    for (int j = 1; j < i; j ++)
                        both -= spot[mask][j][i - 1];
                }
                int rem = 0;
                for (int j = i; j <= n; j ++)
                {

                    ///int both = 0;
                    int ch_i = 0;
                    int ch_j = 0;
                    int neit = 0;

                    if (j > i)
                    {
                        int l = 0;
                        l = pref[mask][i][j - 1];

                        rem += l;
                        both -= l;
                    }
                    //ch_i = bt[bit_i][i].count();
                    //ch_j = bt[bit_j][j].count();

                    ch_i = ch[bit_i][i];
                    ch_j = ch[bit_j][j];

                    ch_i -= both;
                    ch_j -= both;
                    neit = q - both - ch_i - ch_j;


                    int val_i = ((a[i] & (1 << bit_i)) > 0);
                    int val_j = ((a[j] & (1 << bit_j)) > 0);

                    ll res = 0;
                    for (int d_i = 0; d_i < 2; d_i ++)
                        for (int d_j = 0; d_j < 2; d_j ++)
                            for (int b = 0; b < 2; b ++)
                            {
                                if ((val_i + d_i + b) % 2 == 0 ||
                                        (val_j + d_j + b) % 2 == 0)
                                    continue;

                                ll way_i = 0;
                                ll way_j = 0;
                                ll way_b = 0;


                                {
                                    for (int l = d_i; l <= ch_i;  l += 2)
                                    {
                                        way_i += comb(ch_i, l);
                                        if (way_i >= mod)
                                            way_i -= mod;
                                    }
                                }
                                for (int l = d_j; l <= ch_j; l += 2)
                                {
                                    way_j += comb(ch_j, l);
                                    if (way_j >= mod)
                                        way_j -= mod;
                                }
                                for (int l = b; l <= both; l += 2)
                                {
                                    way_b += comb(both, l);
                                    if (way_b >= mod)
                                        way_b -= mod;
                                }
                                ///if ((a[i] & (1 << bit_i)) > 0 && (a[j] & (1 << bit_j)) > 0)
                                {
                                    ///cout << "ways " << way_i << " " << way_j << " " << way_b << endl;
                                }

                                ll ways = ((way_i * way_j) % mod * way_b) % mod;
                                res = res + ways;
                                if (res >= mod)
                                    res -= mod;
                            }



                    res = (res * (pw[bit_i + bit_j])) % mod;
                    res = (res * pw[neit]) % mod;
                    res = (res * (ll)(i) * (ll)(n - j + 1)) % mod;
                    if (i != j)
                        res = (res * 2) % mod;
                    ans += res;
                    if (ans >= mod)
                        ans -= mod;
                    ///if ((a[i] & (1 << bit_i)) > 0 && (a[j] & (1 << bit_j)) > 0)
                    {
                        ///cout << i << " " << j << " " << bit_i << " " << bit_j << " " << res << endl;
                        ///cout << pw[bit_i + bit_j] << " " << (i * (n - i + 1)) << endl;
                        ///cout << ans << endl;
                    }

                }
                both += rem;
            }
        }
    }

    cout << ans << endl;
}

int main()
{
    speed();
    solve();
    return 0;
}
/**
2
1 3
2
1 2 2
1 1 1

*/

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 3 ms 8024 KB Output is correct
3 Correct 10 ms 72028 KB Output is correct
4 Correct 9 ms 61788 KB Output is correct
5 Correct 9 ms 69976 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 3 ms 8024 KB Output is correct
3 Correct 10 ms 72028 KB Output is correct
4 Correct 9 ms 61788 KB Output is correct
5 Correct 9 ms 69976 KB Output is correct
6 Correct 43 ms 120924 KB Output is correct
7 Correct 46 ms 118100 KB Output is correct
8 Correct 38 ms 98896 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 908 ms 120952 KB Output is correct
2 Correct 125 ms 123144 KB Output is correct
3 Correct 45 ms 123024 KB Output is correct
4 Correct 37 ms 122712 KB Output is correct

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 137 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 63324 KB Output is correct
2 Correct 14 ms 61276 KB Output is correct
3 Correct 18 ms 63412 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 63324 KB Output is correct
2 Correct 14 ms 61276 KB Output is correct
3 Correct 18 ms 63412 KB Output is correct
4 Correct 116 ms 63576 KB Output is correct
5 Correct 119 ms 63580 KB Output is correct
6 Correct 116 ms 63580 KB Output is correct
7 Correct 118 ms 63580 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 3 ms 8024 KB Output is correct
3 Correct 10 ms 72028 KB Output is correct
4 Correct 9 ms 61788 KB Output is correct
5 Correct 9 ms 69976 KB Output is correct
6 Correct 43 ms 120924 KB Output is correct
7 Correct 46 ms 118100 KB Output is correct
8 Correct 38 ms 98896 KB Output is correct
9 Correct 13 ms 63324 KB Output is correct
10 Correct 14 ms 61276 KB Output is correct
11 Correct 18 ms 63412 KB Output is correct
12 Correct 123 ms 125552 KB Output is correct
13 Correct 132 ms 125612 KB Output is correct
14 Correct 48 ms 125276 KB Output is correct
15 Correct 61 ms 125020 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 3 ms 8024 KB Output is correct
3 Correct 10 ms 72028 KB Output is correct
4 Correct 9 ms 61788 KB Output is correct
5 Correct 9 ms 69976 KB Output is correct
6 Correct 43 ms 120924 KB Output is correct
7 Correct 46 ms 118100 KB Output is correct
8 Correct 38 ms 98896 KB Output is correct
9 Correct 13 ms 63324 KB Output is correct
10 Correct 14 ms 61276 KB Output is correct
11 Correct 18 ms 63412 KB Output is correct
12 Correct 116 ms 63576 KB Output is correct
13 Correct 119 ms 63580 KB Output is correct
14 Correct 116 ms 63580 KB Output is correct
15 Correct 118 ms 63580 KB Output is correct
16 Correct 123 ms 125552 KB Output is correct
17 Correct 132 ms 125612 KB Output is correct
18 Correct 48 ms 125276 KB Output is correct
19 Correct 61 ms 125020 KB Output is correct
20 Runtime error 141 ms 262144 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 3 ms 8024 KB Output is correct
3 Correct 10 ms 72028 KB Output is correct
4 Correct 9 ms 61788 KB Output is correct
5 Correct 9 ms 69976 KB Output is correct
6 Correct 43 ms 120924 KB Output is correct
7 Correct 46 ms 118100 KB Output is correct
8 Correct 38 ms 98896 KB Output is correct
9 Correct 908 ms 120952 KB Output is correct
10 Correct 125 ms 123144 KB Output is correct
11 Correct 45 ms 123024 KB Output is correct
12 Correct 37 ms 122712 KB Output is correct
13 Runtime error 137 ms 262144 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -