/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 37ms 23.328 MiB
#2 Wrong Answer 45ms 23.414 MiB
#3 Accepted 38ms 23.234 MiB
#4 Wrong Answer 38ms 23.281 MiB

Code

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

ll fact[N];
ll invfact[N];
ll inv[N];
ll 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;
    }
}



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



int 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[x]%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-02 17:43:46
Judged At
2024-11-02 17:43:46
Judged By
Score
5
Total Time
45ms
Peak Memory
23.414 MiB