/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 46ms 23.316 MiB
#2 Accepted 47ms 23.27 MiB
#3 Accepted 52ms 23.336 MiB
#4 Accepted 57ms 23.453 MiB
#5 Wrong Answer 50ms 23.387 MiB
#6 Wrong Answer 56ms 23.43 MiB

Code

#include <bits/stdc++.h>
#define ll long long
#define int long long
#define nl '\n'
using namespace std;
const ll mod = 1e9 + 7;
const int N = 1e6 + 5;

int fact[N];
int invfact[N];
int inv[N];
int gun(int x, int y)
{
    return ((x * 1ll * y) % mod);
}
void init()
{
    fact[0] = 1;
    invfact[0] = 1;
    inv[1] = 1;
    for (int i = 2; i < N; i++)
        inv[i] = inv[mod % i] * 1ll * (mod - mod / i) % mod;
    for (int i = 1; i < N; i++)
    {
        fact[i] = gun(fact[i - 1], i);
        invfact[i] = (invfact[i - 1] * 1ll * inv[i]) % mod;
    }
}

int ncr(int n, int r)
{
    if (n < r || n < 0 || r < 0)
    {
        return 0;
    }
    return gun(fact[n], gun(invfact[r], invfact[n - r]));
}

int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    ll n, q;
    cin >> n >> q;
    ll a[n];
    ll pre[n];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        if (i == 0)
        {
            pre[i] = (a[i] % 2 == 1) ? 1 : 0;
        }
        else
        {
            pre[i] = pre[i - 1] + (a[i] % 2 == 1 ? 1 : 0);
        }
    }
    while (q--)
    {
        ll x, y, z;
        cin >> x >> y >> z;
        y--;
        z--;
        ll odd = pre[z] - pre[y];
        if (a[y] % 2 == 1)
        {
            odd++;
        }

        ll even = z - y + 1 - odd;
        if (x == 0)
        {
            ll combination_odd = 0;
            for (int i = 2; i <= odd; i += 2)
            {
                combination_odd += ncr(odd, i) % mod;
            }
            ll combination_even = 0;
            for (int i = 1; i <= even; i++)
            {
                combination_even += ncr(even, i) % mod;
            }
            ll ans = (combination_even + combination_odd + combination_even * combination_odd) % mod;
            cout << ans << nl;
        }
        else
        {
            ll combination_odd = 0;
            for (int i = 1; i <= odd; i += 2)
            {
                combination_odd += ncr(odd, i) % mod;
            }
            ll combination_even = 0;
            for (int i = 1; i <= even; i++)
            {
                combination_even += ncr(even, i) % mod;
            }

            ll ans = combination_odd + combination_even * combination_odd;
            cout << ans % mod << nl;
        }
    }
}

Information

Submit By
Type
Submission
Problem
P1033 Lyra and the Secrets of the Grand Library
Language
C++17 (G++ 13.2.0)
Submit At
2024-11-03 08:49:20
Judged At
2024-11-03 08:49:20
Judged By
Score
15
Total Time
57ms
Peak Memory
23.453 MiB