Submission #1273870

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273870		phtung	Binaria (CCO23_day1problem1)	C++20	25 / 25	56 ms	16088 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1000003; // 10^6 + 3

ll modpow(ll a, ll e){
    ll r=1;
    while(e){
        if(e&1) r = (r*a)%MOD;
        a = (a*a)%MOD;
        e >>= 1;
    }
    return r;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N,K;
    if(!(cin>>N>>K)) return 0;
    int M = N - K + 1;
    vector<int> S(M+1);
    for(int i=1;i<=M;i++) cin>>S[i];

    if(M==0){
        // K > N? but constraints say K <= N. fallback
        cout<<0<<"\n";
        return 0;
    }

    // differences d[i] = S[i+1]-S[i], for i = 1..M-1
    vector<int> d(M+1,0);
    for(int i=1;i<=M-1;i++) d[i] = S[i+1] - S[i];

    int forcedOnes = 0, forcedZeros = 0, freeChains = 0;
    for(int r=1; r<=K; r++){
        // traverse positions r, r+K, r+2K, ...
        int pos = r;
        int c = 0; // c_t
        bool impossible = false;
        bool hasPos1 = false; // c_t == 1
        bool hasNeg1 = false; // c_t == -1
        // t=0 (pos=r) => c=0 check
        if(abs(c) >= 2) impossible = true;
        if(c == 1) hasPos1 = true;
        if(c == -1) hasNeg1 = true;
        // advance while pos <= N-K (i.e., there exists d[pos])
        while(pos <= N - K){
            // step: c += d[pos], move to pos+K
            c += d[pos];
            pos += K;
            if(abs(c) >= 2){ impossible = true; break; }
            if(c == 1) hasPos1 = true;
            if(c == -1) hasNeg1 = true;
        }
        if(impossible){ cout << 0 << '\n'; return 0; }
        if(hasPos1 && hasNeg1){ cout << 0 << '\n'; return 0; }
        if(hasPos1) forcedZeros++;       // c==1 forces x_r = 0
        else if(hasNeg1) forcedOnes++;   // c==-1 forces x_r = 1
        else freeChains++;               // all c==0 -> free
    }

    int need = S[1] - forcedOnes;
    if(need < 0 || need > freeChains){ cout << 0 << '\n'; return 0; }

    // compute C(freeChains, need) modulo MOD
    int n = freeChains;
    int k = need;
    // precompute factorials up to n
    vector<ll> fact(n+1,1), invfact(n+1,1);
    for(int i=1;i<=n;i++) fact[i] = (fact[i-1]*i)%MOD;
    invfact[n] = modpow(fact[n], MOD-2);
    for(int i=n;i>=1;i--) invfact[i-1] = (invfact[i]*i)%MOD;
    ll ans = fact[n];
    ans = ans * invfact[k] % MOD;
    ans = ans * invfact[n-k] % MOD;
    cout << ans % MOD << '\n';
    return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 3 / 3
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 7 / 7