제출 #1313295

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1313295		SpyrosAliv	Binaria (CCO23_day1problem1)	C++20	25 / 25	66 ms	24020 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MOD = 1e6+3;
const int MN = 1e6+5;
int fact[MN];
int n, k;
int a[MN], po[MN];

int binpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) {
            res = res * a % MOD;
        }
        b /= 2;
        a = a * a % MOD;
    }
    return res;
}

int inv(int a) {
    return binpow(a, MOD-2);
}

int nck(int n, int k) {
    if (k == 0 || k == n) return 1;
    return fact[n] * inv(fact[k] * fact[n-k] % MOD) % MOD;
}

void solve() {
    cin >> n >> k;
    fact[0] = 1;
    for (int i = 1; i <= n; i++) fact[i] = fact[i-1] * i % MOD;
    vector<bool> same(n+1, false);
    vector<int> val(n+1, -1);
    bool bad = false;
    for (int i = k; i <= n; i++) {
        cin >> a[i-k+1];
        int curr = a[i-k+1];
        if (i == k) continue;
        int prev = a[i-k];
        if (abs(prev - curr) > 1) bad = true;
        if (prev == curr) {
            same[i] = true;
            if (val[i-k] != -1) val[i] = val[i-k];
        }
        else {
            if (prev < curr) {
                val[i] = 1;
                if (val[i-k] == 1) {
                    bad = true;
                }
            }
            else {
                val[i] = 0;
                if (val[i-k] == 0) {
                    bad = true;
                }
            }
        }
    }
    if (bad) {
        cout << 0 << "\n";
    }
    for (int i = n; i >= k+1; i--) {
        if (val[i] == -1) continue;
        if (same[i]) {
            val[i-k] = val[i];
        }
        else val[i-k] = !val[i];
    }
    int av = a[1];
    int could = 0;
    for (int i = 1; i <= k; i++) {
        if (val[i] == -1) could++;
        if (val[i] == 1) av--;
    }
    if (av < 0 || av > could) {
        cout << 0 << "\n";
        return;
    }
    cout << nck(could, av) << "\n";
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    while (t--) 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