// Author: caption_mingle #include "bits/stdc++.h" using namespace std; #define ln "\n" #define pb push_back #define fi first #define se second #define all(x) (x).begin(), (x).end() #define sz(x) ((int)(x).size()) #define ll long long const int mod = 1e6 + 3; const int inf = 2e9; const int N = 1e6 + 7; int n, k; int a[N], val[N]; vector<int> grp[N]; int mul(int x, int y) { return (1ll * x * y) % mod; } int power(int x, int y) { int ans = 1; while(y > 0) { if(y & 1) ans = mul(ans, x); y >>= 1; x = mul(x, x); } return ans; } int nCk(int n, int k) { if(n < k) return 0; int ans = 1, ext = 1; for(int i = k + 1; i <= n; i++) { ans = mul(ans, i); ext = mul(ext, n - i + 1); } return mul(ans, power(ext, mod - 2)); } struct DSU { vector<int> par, sz; DSU(int n) { par.resize(n + 1, 0); sz.resize(n + 1, 1); for(int i = 1; i <= n; i++) par[i] = i; } int find(int u) { return u == par[u] ? u : par[u] = find(par[u]); } void join(int u, int v) { u = find(u), v = find(v); if(u == v) return; if(sz[u] < sz[v]) swap(u, v); par[v] = u; sz[u] += sz[v]; } }; signed main() { cin.tie(0) -> sync_with_stdio(0); #define task "" if(fopen(task ".INP", "r")) { freopen(task ".INP", "r", stdin); freopen(task ".OUT", "w", stdout); } cin >> n >> k; for(int i = 1; i <= n - k + 1; i++) { cin >> a[i]; } for(int i = 1; i <= n - k + 1; i++) { if(a[i] > k) { cout << 0 << ln; return 0; } } DSU d(n); memset(val, -1, sizeof val); for(int i = k + 1, j = 2; i <= n; i++, j++) { if(abs(a[j] - a[j - 1]) > 1) { cout << 0 << ln; return 0; } if(a[j] == a[j - 1]) { d.join(i, i - k); } else if(a[j] > a[j - 1]) { val[i] = 1; if(val[i - k] == 1) { cout << 0 << ln; return 0; } val[i - k] = 0; } else { val[i] = 0; if(val[i - k] == 0) { cout << 0 << ln; return 0; } val[i - k] = 1; } } for(int i = 1; i <= n; i++) { grp[d.find(i)].pb(i); } for(int i = 1; i <= n; i++) { if(sz(grp[i]) == 0) continue; int comm = -1; for(int x : grp[i]) { if(val[x] != -1) { if(comm != -1 and comm != val[x]) { cout << 0 << ln; return 0; } if(comm == -1) comm = val[x]; } } for(int x : grp[i]) val[x] = comm; } int cur = k; int cnt1 = a[1]; for(int i = 1; i <= k; i++) { if(val[i] != -1) cur--; if(val[i] == 1) cnt1--; } cout << nCk(cur, cnt1) << ln; cerr << "\nTime: " << clock() * 1000 / CLOCKS_PER_SEC; }

Main.cpp: In function 'int main()':
Main.cpp:68:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         freopen(task ".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:69:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         freopen(task ".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~