QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #750077 | #6199. 数圈圈 | jason_sun | 0 | 0ms | 3888kb | C++14 | 1.8kb | 2024-11-15 12:32:56 | 2024-11-15 12:32:57 |
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2005, mod=998244353;
void add(ll &x, ll y){
x=(x+y)%mod;
}
int a[N], b[N];
ll f[N][N];
ll qp(ll x, ll y){
ll ans=1;
for(;y;y/=2,x=x*x%mod){
if(y&1) ans=ans*x%mod;
}
return ans;
}
int main(){
// freopen("story.in", "r", stdin);
// freopen("story.out", "w", stdout);
int c, n, y;
scanf("%d%d%d", &c, &n, &y);
for(int i=1; i<=n; ++i){
scanf("%d", &a[i]);
}
for(int i=1; i<=n; ++i){
b[i]=b[i-1];
while(b[i]<n&&a[b[i]+1]>=i) b[i]++;
}
if(c<=5){
f[0][0]=1;
for(int i=1; i<=n; ++i){
if(a[i]>=i){
for(int j=0; j<=n; ++j){
add(f[i][j], f[i-1][j]);
add(f[i][j+1], f[i-1][j]*(a[i]-1-j));
add(f[i][j+1], f[i-1][j]*y);
}
}else{
for(int j=0; j<=n; ++j){
add(f[i][j], f[i-1][j]);
add(f[i][j+1], f[i-1][j]*(a[i]-j));
}
}
}
for(int i=0; i<=n; ++i){
printf("%lld%c", f[n][i], " \n"[i==n]);
}
}else{
f[n+1][0]=1;
for(int i=n; i>=1; --i){
if(a[i]>=i){
// if(a[i]>=b[i]){
for(int j=0; j<=n; ++j){
add(f[i][j], f[i+1][j]);
add(f[i][j+1], f[i+1][j]*(a[i]-1+y-j));
}
// }else{
// ll t=(b[i]-a[i]+1)*qp(b[i]-i+1, mod-2)%mod;
// for(int j=0; j<=n; ++j){
// add(f[i][j], f[i+1][j]);
// add(f[i][j+1], f[i+1][j]*(a[i]-j+(y-1)*t%mod));
// }
// }
}else{
for(int j=0; j<=n; ++j){
add(f[i][j], f[i+1][j]);
add(f[i][j+1], f[i+1][j]*(a[i]-j));
}
}
}
for(int i=0; i<=n; ++i){
printf("%lld%c", f[1][i], " \n"[i==n]);
}
}
return 0;
}
//6 3 1
//3 2 2
//
//0 0 1 : 1
//2 0 1 : 1
//3 0 1 : y
//0 2 1 : y
//3 2 1 : y^2
//
//0 0 2 : 1
//1 0 2 : y
//3 0 2 : 1
//0 1 2 : 1
//3 1 2 : y
/*
6 4 1
4 2 2 2
5 5 3 3 1
5 4 4 2 2
*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 0
Time Limit Exceeded
input:
1 915080344 1
output:
result:
Subtask #2:
score: 0
Wrong Answer
Test #8:
score: 0
Wrong Answer
time: 0ms
memory: 3672kb
input:
15 0 1 1 1 3 6 8 10 11 11 12 13 13 14 15 15
output:
1
result:
wrong answer Answer contains longer sequence [length = 16], but output contains 1 elements
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Wrong Answer
Test #19:
score: 0
Wrong Answer
time: 0ms
memory: 3888kb
input:
74999 1 1 2 3 3 4 4 4 4 4 4 4 4 7 8 8 9 9 9 10 13 13 14 14 16 19 20 21 22 24 25 25 26 26 29 31 32 32 35 35 36 38 39 39 40 41 43 43 44 45 45 45 46 48 49 50 50 50 51 53 54 57 59 59 60 60 62 63 63 65 66 69 71 73 76 78 78 78 79 79 79 80 81 81 81 82 82 83 83 85 87 89 91 94 94 94 94 98 99 99 100 100 101 1...
output:
1 2
result:
wrong answer 2nd numbers differ - expected: '807105292', found: '2'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Wrong Answer
Test #28:
score: 0
Wrong Answer
time: 0ms
memory: 3872kb
input:
15 0 15 15 15 13 13 13 12 10 10 9 9 6 6 4 2
output:
1
result:
wrong answer Answer contains longer sequence [length = 16], but output contains 1 elements
Subtask #7:
score: 0
Skipped
Dependency #6:
0%
Subtask #8:
score: 0
Runtime Error
Test #38:
score: 0
Runtime Error
input:
74999 604849250 72634 60382 41531 20689 20667 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
result:
Subtask #9:
score: 0
Skipped
Dependency #6:
0%