oj.uz

Submission #992988

# Submission time Handle Problem Language Result Execution time Memory
992988 2024-06-05T08:47:01 Z danikoynov Intergalactic ship (IZhO19_xorsum) C++14
53 / 100
 768 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;

                                if (ch_i % 2 == 0)
                                {

                                    if (ch_i == 0)
                                    {
                                        if (d_i == 0)
                                        way_i = 1;
                                    }
                                    else
                                    way_i = pw[ch_i - 1];

                                }
                                else
                                {
                                    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 6492 KB Output is correct
2 Correct 3 ms 7884 KB Output is correct
3 Correct 10 ms 71976 KB Output is correct
4 Correct 9 ms 61788 KB Output is correct
5 Correct 9 ms 69960 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 3 ms 7884 KB Output is correct
3 Correct 10 ms 71976 KB Output is correct
4 Correct 9 ms 61788 KB Output is correct
5 Correct 9 ms 69960 KB Output is correct
6 Correct 46 ms 118876 KB Output is correct
7 Correct 42 ms 118220 KB Output is correct
8 Correct 47 ms 99044 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 768 ms 120920 KB Output is correct
2 Correct 102 ms 121296 KB Output is correct
3 Correct 44 ms 119388 KB Output is correct
4 Correct 43 ms 119124 KB Output is correct

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 132 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 14 ms 63324 KB Output is correct
2 Correct 14 ms 61276 KB Output is correct
3 Correct 14 ms 63320 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 63324 KB Output is correct
2 Correct 14 ms 61276 KB Output is correct
3 Correct 14 ms 63320 KB Output is correct
4 Correct 97 ms 63580 KB Output is correct
5 Correct 90 ms 63576 KB Output is correct
6 Correct 102 ms 63580 KB Output is correct
7 Correct 96 ms 63580 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 3 ms 7884 KB Output is correct
3 Correct 10 ms 71976 KB Output is correct
4 Correct 9 ms 61788 KB Output is correct
5 Correct 9 ms 69960 KB Output is correct
6 Correct 46 ms 118876 KB Output is correct
7 Correct 42 ms 118220 KB Output is correct
8 Correct 47 ms 99044 KB Output is correct
9 Correct 14 ms 63324 KB Output is correct
10 Correct 14 ms 61276 KB Output is correct
11 Correct 14 ms 63320 KB Output is correct
12 Correct 109 ms 119632 KB Output is correct
13 Correct 107 ms 119640 KB Output is correct
14 Correct 59 ms 117588 KB Output is correct
15 Correct 62 ms 119388 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 3 ms 7884 KB Output is correct
3 Correct 10 ms 71976 KB Output is correct
4 Correct 9 ms 61788 KB Output is correct
5 Correct 9 ms 69960 KB Output is correct
6 Correct 46 ms 118876 KB Output is correct
7 Correct 42 ms 118220 KB Output is correct
8 Correct 47 ms 99044 KB Output is correct
9 Correct 14 ms 63324 KB Output is correct
10 Correct 14 ms 61276 KB Output is correct
11 Correct 14 ms 63320 KB Output is correct
12 Correct 97 ms 63580 KB Output is correct
13 Correct 90 ms 63576 KB Output is correct
14 Correct 102 ms 63580 KB Output is correct
15 Correct 96 ms 63580 KB Output is correct
16 Correct 109 ms 119632 KB Output is correct
17 Correct 107 ms 119640 KB Output is correct
18 Correct 59 ms 117588 KB Output is correct
19 Correct 62 ms 119388 KB Output is correct
20 Runtime error 148 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 6492 KB Output is correct
2 Correct 3 ms 7884 KB Output is correct
3 Correct 10 ms 71976 KB Output is correct
4 Correct 9 ms 61788 KB Output is correct
5 Correct 9 ms 69960 KB Output is correct
6 Correct 46 ms 118876 KB Output is correct
7 Correct 42 ms 118220 KB Output is correct
8 Correct 47 ms 99044 KB Output is correct
9 Correct 768 ms 120920 KB Output is correct
10 Correct 102 ms 121296 KB Output is correct
11 Correct 44 ms 119388 KB Output is correct
12 Correct 43 ms 119124 KB Output is correct
13 Runtime error 132 ms 262144 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -