Submission #967940

#	Time	Username	Problem	Language	Result	Execution time	Memory
967940		leolin0214	Binaria (CCO23_day1problem1)	C++17	25 / 25	102 ms	16124 KiB

Main

#include <iostream>
#include <vector>
#define mod 1000003
using namespace std;
struct DisjointSetUnion {
    int n;
    int com;
    vector<int> fa;
    void init(int _n) {
        n = _n;
        com = n;
        fa.resize(n);
        for (int i=0; i<n; i++) fa[i] = i;
    }
    int find(int x) {
        if (fa[x] == x) return x;
        return fa[x] = find(fa[x]);
    }
    void merge(int x, int y) {
        if (find(x) == find(y)) return;
        com--;
        fa[find(y)] = find(x);
    }
};
inline long long invmod(long long x) {
    long long ans = 1;
    for (int i=mod-2; i; i>>=1) {
        if (i&1) ans = ans * x % mod;
        x = x * x % mod;
    }
    return ans;
}
DisjointSetUnion DSU;
long long fac[1000001];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector<int> a(n-k+1);
    vector<int> ans(n, -1);
    for (int i=0; i<n-k+1; i++) cin >> a[i];
    DSU.init(n+2);
    for (int i=0; i<n-k; i++) {
        int diff = a[i+1] - a[i];
        if (diff == 1) {
            DSU.merge(n, i);
            DSU.merge(n+1, i+k);
        }else if (diff == -1) {
            DSU.merge(n+1, i);
            DSU.merge(n, i+k);
        }else if (diff == 0) {
            DSU.merge(i, i+k);
        }else{
            cout << "0\n";
            return 0;
        }
    }
    if (DSU.find(n) == DSU.find(n+1)) {
        cout << "0\n";
        return 0;
    }
    for (int i=0; i<n; i++) {
        if (DSU.find(i) == n) ans[i] = 0;
        if (DSU.find(i)== n+1) ans[i] = 1;
    }


    fac[0] = 1;
    for (int i=1; i<=k; i++) fac[i] = fac[i-1] * i % mod;


    int space = 0, one = 0;
    for (int i=0; i<k; i++) {
        if (ans[i] == -1) space++;
        if (ans[i] == 1) one++;
    }
    if (one > a[0]) {
        cout << "0\n";
        return 0;
    }
    int zero = a[0] - one;

    cout << fac[space] * invmod(fac[zero]) % mod * invmod(fac[space-zero]) % mod << "\n";
}

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