#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+1,mod=1e6+3;
int fac[N],ifac[N],a[N];
int pxp(int x,int p)
{
if(!p) return 1;
if(p&1) return (x*pxp(x,p-1)%mod)%mod;
int ret=pxp(x,p/2);
return (ret*ret)%mod;
}
signed main()
{
ios::sync_with_stdio(0); cin.tie(0);
fac[0]=1;
for(int i=1;i<N;i++) fac[i]=(fac[i-1]*i)%mod;
ifac[N-1]=pxp(fac[N-1],mod-2);
for(int i=N-2;i>=0;i--) ifac[i]=(ifac[i+1]*(i+1))%mod;
int n,k; cin>>n>>k;
int b[n-k+1]; for(int i=0;i<n-k+1;i++) cin>>b[i];
memset(a,-1,sizeof a);
bool f=false;
for(int i=0;i<n-k;i++){
if(a[i]==-1){
if(b[i]>b[i+1]) a[i]=1,a[i+k]=0;
else if(b[i]<b[i+1]) a[i]=0,a[i+k]=1;
}
else if(a[i]==1){
if(b[i]==b[i+1]) a[i+k]=a[i];
else if(b[i]>b[i+1]) a[i+k]=0;
else f=true;
}
else {
if(b[i]==b[i+1]) a[i+k]=a[i];
else if(b[i]<b[i+1]) a[i+k]=1;
else f=true;
}
}
for(int i=n-k;i>0;i--){
if(a[i+k-1]==1){
if(b[i]==b[i-1]) a[i]=1;
else if(b[i]>b[i-1]) a[i]=1;
}
else if(a[i+k-1]==0){
if(b[i]==b[i-1]) a[i-1]=0;
else if(b[i]<b[i-1]) a[i-1]=1;
}
}
int s=0;
for(int i=0;i<k;i++){
if(a[i]==-1) s++;
else if(a[i]) b[0]--;
}
if(f||s<b[0]) { cout<<0<<endl; return 0; }
cout<<(((ifac[b[0]]*ifac[s-b[0]])%mod)*fac[s])%mod;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
23752 KB |
Output is correct |
2 |
Correct |
18 ms |
23900 KB |
Output is correct |
3 |
Incorrect |
17 ms |
23900 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
23752 KB |
Output is correct |
2 |
Correct |
18 ms |
23900 KB |
Output is correct |
3 |
Incorrect |
17 ms |
23900 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
23752 KB |
Output is correct |
2 |
Correct |
18 ms |
23900 KB |
Output is correct |
3 |
Incorrect |
17 ms |
23900 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
23752 KB |
Output is correct |
2 |
Correct |
18 ms |
23900 KB |
Output is correct |
3 |
Incorrect |
17 ms |
23900 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
23752 KB |
Output is correct |
2 |
Correct |
18 ms |
23900 KB |
Output is correct |
3 |
Incorrect |
17 ms |
23900 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
23752 KB |
Output is correct |
2 |
Correct |
18 ms |
23900 KB |
Output is correct |
3 |
Incorrect |
17 ms |
23900 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |