QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #409498 | #6625. Binaria | Dinal | 0 | 1ms | 6028kb | C++14 | 1.0kb | 2024-05-12 09:57:11 | 2024-05-12 09:57:12 |
answer
#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[1000010];
int b[1000010];
#define mod 1000003
int qpow(long long a,int b,int p){
long long c=1;
for(;b;b>>=1,a=a*a%p)
if(b&1)c=c*a%p;
return c;
}
int C(int n,int m){
if(m>n)return 0;
long long ans=1;
for(int i=1;i<=n;++i)ans=ans*i%mod;
long long tmp=1;
for(int i=1;i<=m;++i)tmp=tmp*i%mod;
for(int i=1;i<=n-m;++i)tmp=tmp*i%mod;
ans=ans*qpow(tmp,mod-2,mod)%mod;
return ans;
}
int main(){
cin>>n>>k;
for(int i=1;i<=n-k;++i)cin>>b[i];
for(int i=1;i<n-k;++i){
a[i+k]=b[i+1]-b[i];
}
// for(int i=1;i<=n;++i)printf("%d ",a[i]);puts("");
for(int i=1;i<=k;++i){
a[i]=-1;
int c=0;
for(int j=i+k;j<=n;j+=k){
c+=a[j];
if(c>1||c<-1){
puts("0");
return 0;
}
if(c==1){
a[i]=0;
}
if(c==-1){
a[i]=1;
}
}
}
int s=b[1],cnt=0;
for(int i=1;i<=k;++i)if(a[i]==1)s--;else if(a[i]==-1)cnt++;
// printf("%d %d \n",s,cnt);
printf("%d\n",C(cnt,s));
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 3
Accepted
time: 0ms
memory: 5896kb
input:
1 1 0
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 6028kb
input:
1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 6024kb
input:
10 3 1 2 2 2 2 2 2 2
output:
2
result:
ok 1 number(s): "2"
Test #4:
score: 0
Accepted
time: 1ms
memory: 6024kb
input:
10 3 1 1 0 1 2 3 2 2
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 1ms
memory: 5920kb
input:
10 3 2 2 2 2 2 2 2 2
output:
3
result:
ok 1 number(s): "3"
Test #6:
score: 0
Accepted
time: 1ms
memory: 5924kb
input:
10 3 2 1 1 1 1 2 2 3
output:
1
result:
ok 1 number(s): "1"
Test #7:
score: 0
Accepted
time: 1ms
memory: 5904kb
input:
10 3 1 1 1 0 0 0 0 0
output:
1
result:
ok 1 number(s): "1"
Test #8:
score: 0
Accepted
time: 1ms
memory: 5952kb
input:
10 3 0 0 0 0 0 0 0 0
output:
1
result:
ok 1 number(s): "1"
Test #9:
score: 0
Accepted
time: 1ms
memory: 5956kb
input:
10 2 1 1 1 1 1 1 1 1 1
output:
2
result:
ok 1 number(s): "2"
Test #10:
score: -3
Wrong Answer
time: 1ms
memory: 5900kb
input:
10 2 1 1 1 1 1 1 1 1 2
output:
2
result:
wrong answer 1st numbers differ - expected: '1', found: '2'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #5:
0%