Submission #1016088

#TimeUsernameProblemLanguageResultExecution timeMemory
1016088Khanhcsp2Binaria (CCO23_day1problem1)C++14
0 / 25
1 ms600 KiB
#include<bits/stdc++.h> #define el '\n' #define fi first #define sc second #define int ll #define pii pair<int, int> #define all(v) v.begin(), v.end() using namespace std; using ll=long long; using ull=unsigned long long; using ld=long double; const int mod=1e6+3; const int N=1e6+11; int n, k, a[N], ned[N], f[N]; int po(int a, int b) { int r=1; while(b) { if(b&1) r=r*a%mod; b/=2; a=a*a%mod; } return r%mod; } void sol() { cin >> n >> k; for(int i=1;i<=n-k+1;i++) cin >> a[i]; for(int i=1;i<=n;i++) ned[i]=-1; for(int i=1;i<=n-k;i++) { if(abs(a[i]-a[i+1])>=2) { cout << 0; return; } if(a[i]>a[i+1]) { if(ned[i]==0) { cout << 0; return; } ned[i]=1; } else if(a[i]<a[i+1]) { if(ned[i]==1) { cout << 0; return; } ned[i]=0; } else if(a[i]==a[i+1]) ned[i]=ned[i+k]; } f[0]=1; int s1=a[1], s2=0; for(int i=1;i<=k;i++) { if(ned[i]==1) s1--; else if(ned[i]==-1) s2++; } for(int i=1;i<=k;i++) f[i]=f[i-1]*i%mod; if(s1>s2) cout << 0; else cout << f[s2]*po(f[s1], mod-2)%mod*po(f[s2-s1], mod-2)%mod; } signed main() { // freopen("divisor.INP", "r", stdin); // freopen("divisor.OUT", "w", stdout); ios_base::sync_with_stdio(0); cin.tie(0); int t=1; //cin >> t; while(t--) { sol(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...