Submission #1309471

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309471		ayuxhkumxr22	Binaria (CCO23_day1problem1)	C++20	25 / 25	196 ms	16072 KiB

Main

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

long long MOD = 1000003; // 10^6 + 3 is prime

long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

long long modInverse(long long n) {
    return power(n, MOD - 2);
}

long long nCr(int n, int r, const vector<long long>& fact, const vector<long long>& invFact) {
    if (r < 0 || r > n) return 0;
    return fact[n] * invFact[r] % MOD * invFact[n - r] % MOD;
}

void solve() {
    int N, K;
    if (!(cin >> N >> K)) return;

    vector<int> A(N - K + 1);
    for (int i = 0; i < N - K + 1; i++) cin >> A[i];

    int free_chains = 0;
    int required_ones = 0;
    
    // Process K chains
    for (int r = 0; r < K; r++) {
        // Current logical value relative to start of chain (0)
        // We track min_val and max_val relative to start
        // If start=0, values are rel_val.
        // If start=1, values are rel_val+1.
        
        int current_rel = 0;
        int min_rel = 0;
        int max_rel = 0;
        
        for (int i = r; i + K < N; i += K) {
            // Index in sum array corresponds to window starting at i
            // Difference A[j+1] - A[j] corresponds to S[i+K] - S[i]
            // where j is the index of the window starting at i.
            // Window at i is A[i]. Window at i+1 is A[i+1].
            // But A is 0-indexed in code.
            // A[x] covers indices x...x+K-1.
            // S[i+K] - S[i] = A[i - (K-1) + K]... no wait
            
            // Simpler: A[i+1] - A[i] = S[i+K] - S[i].
            // We need to check if A index i exists.
            if (i < A.size() - 1) {
                int diff = A[i + 1] - A[i];
                current_rel += diff;
                min_rel = min(min_rel, current_rel);
                max_rel = max(max_rel, current_rel);
            }
        }

        // Validity check for the chain starting at S[r]
        bool can_be_0 = true;
        bool can_be_1 = true;

        // If S[r]=0, all values are (0 + relative). Must be in [0,1].
        // So min_rel >= 0 AND max_rel <= 1.
        if (min_rel < 0 || max_rel > 1) can_be_0 = false;

        // If S[r]=1, all values are (1 + relative). Must be in [0,1].
        // So min_rel >= -1 AND max_rel <= 0.
        if (min_rel < -1 || max_rel > 0) can_be_1 = false;

        if (can_be_1 && !can_be_0) {
            required_ones++;
        } else if (can_be_0 && can_be_1) {
            free_chains++;
        } 
        // If neither, output 0 (though problem says input is valid)
    }

    int target = A[0] - required_ones;
    
    // Prepare Combinatorics
    vector<long long> fact(free_chains + 1);
    vector<long long> invFact(free_chains + 1);
    fact[0] = 1;
    invFact[0] = 1;
    for (int i = 1; i <= free_chains; i++) {
        fact[i] = (fact[i - 1] * i) % MOD;
        invFact[i] = modInverse(fact[i]);
    }

    cout << nCr(free_chains, target, fact, invFact) << endl;
}

int main() {
    solve();
    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