QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #767440 | #7195. Non-descending Sequence | dongyc666 | WA | 0ms | 5696kb | C++17 | 682b | 2024-11-20 20:56:57 | 2024-11-20 20:57:05 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int NR=2020;
const int MOD=2017;
int n,a[NR],inv[NR],f[NR][NR],dp[NR];
void add(int &x,int y){x=(x+y)%MOD;}
void sub(int &x,int y){x=(x-y%MOD+MOD)%MOD;}
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=n-1;i>=1;i--)a[i]=min(a[i],a[i+1]);
inv[1]=1;
for(int i=2;i<MOD;i++)inv[i]=(MOD-(MOD/i))*inv[MOD%i]%MOD;
for(int i=1;i<=n;i++){
f[i][0]=1;
for(int j=1;j<=n;j++)f[i][j]=f[i][j-1]*(a[i]-j+2)%MOD*inv[j]%MOD;
}
dp[0]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<i;j++)
if((i-j-1)&1)sub(dp[i],dp[j]*f[j+1][i-j]);
else add(dp[i],dp[j]*f[j+1][i-j]);
cout<<dp[n]<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3696kb
input:
2 1 1
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
3 1 2 4
output:
19
result:
ok 1 number(s): "19"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
1 0
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
10 2 0 2 0 1 1 1 2 0 1
output:
2
result:
ok 1 number(s): "2"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
10 1 9 5 10 9 2 3 0 3 8
output:
30
result:
ok 1 number(s): "30"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
10 5 13 10 9 13 1 20 6 10 5
output:
546
result:
ok 1 number(s): "546"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
10 20 35 10 30 3 34 24 39 12 49
output:
100
result:
ok 1 number(s): "100"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
10 62 65 20 53 87 84 61 68 38 46
output:
376
result:
ok 1 number(s): "376"
Test #9:
score: 0
Accepted
time: 0ms
memory: 5696kb
input:
10 51 223 427 369 264 124 222 241 87 496
output:
1041
result:
ok 1 number(s): "1041"
Test #10:
score: 0
Accepted
time: 0ms
memory: 5600kb
input:
10 979 399 460 97 912 441 201 975 168 999
output:
1963
result:
ok 1 number(s): "1963"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
10 1566 1646 139 307 1044 1630 1804 1297 1570 300
output:
720
result:
ok 1 number(s): "720"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
10 208 4884 3032 3287 328 3351 244 1250 3797 528
output:
1808
result:
ok 1 number(s): "1808"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
10 39532 139764 61334 65512 103253 123977 122087 108745 39728 21293
output:
1422
result:
ok 1 number(s): "1422"
Test #14:
score: -100
Wrong Answer
time: 0ms
memory: 3720kb
input:
10 973577511 924860842 135145374 333683082 866710766 260390187 469183413 342124177 106180997 379641830
output:
241
result:
wrong answer 1st numbers differ - expected: '966', found: '241'