QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#279675 | #7875. Queue Sorting | Luan_233 | AC ✓ | 25ms | 7624kb | C++14 | 1.3kb | 2023-12-08 23:03:22 | 2023-12-08 23:03:22 |
Judging History
answer
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mod 998244353
const int maxn = 505;
int n,cnt,ai[maxn],sum[maxn];
long long c[maxn][maxn],f[maxn][maxn],ans;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0),std::cout.tie(0);
std::cin>>n;
for(int i=1,a;i<=n;++i){
std::cin>>a;
if(a) ai[++cnt]=a;
}
n=cnt;
for(int i=1;i<=n;++i) sum[i]=sum[i-1]+ai[i];
c[0][0]=1;
for(int i=1;i<=sum[n];++i){
for(int j=0;j<=i;++j){
if(!j) c[i][j]=c[i-1][j];
else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
}
}
f[1][0]=1;
for(int i=1;i<n;++i){
std::memcpy(f[i+1],f[i],sizeof(long long)*maxn);
for(int j=0;j<sum[i];++j){
int res=sum[i]-j;
for(int k=0;k<ai[i+1];++k){
int lim=ai[i+1]-k+res;
for(int l=ai[i+1]-k;l<lim;++l){
(f[i+1][j+l]+=f[i][j]*c[l-1][ai[i+1]-k-1])%=mod;
}
}
}
}
// for(int i=1;i<=n;++i){
// for(int j=0;j<sum[i];++j) std::cout<<f[i][j]<<" ";
// std::cout<<std::endl;
// }
for(int i=0;i<sum[n];++i) ans+=f[n][i];
std::cout<<ans%mod<<std::endl;
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 5724kb
input:
4 1 1 1 1
output:
14
result:
ok 1 number(s): "14"
Test #2:
score: 0
Accepted
time: 25ms
memory: 6516kb
input:
300 0 5 2 2 1 0 3 2 2 5 2 1 1 2 1 3 2 3 2 0 0 0 0 1 2 2 3 0 2 2 3 2 0 2 3 0 6 0 0 2 0 1 3 2 1 1 1 3 4 0 1 0 4 1 1 1 1 1 1 2 3 2 1 2 3 2 3 0 5 3 3 2 0 1 1 0 2 1 1 2 0 0 2 1 1 3 2 2 1 2 1 3 0 3 0 1 2 2 0 5 0 2 2 0 0 0 1 2 1 4 2 1 1 0 3 0 2 0 3 1 1 2 0 2 1 1 0 2 0 1 2 2 3 3 1 1 1 1 0 1 3 3 1 0 2 2 4 2 ...
output:
507010274
result:
ok 1 number(s): "507010274"
Test #3:
score: 0
Accepted
time: 23ms
memory: 7624kb
input:
500 1 1 0 2 1 0 2 3 2 0 0 2 0 2 1 1 0 0 1 1 1 2 1 1 1 0 1 1 2 2 1 4 0 2 1 0 2 3 1 0 1 1 0 2 1 2 2 1 0 0 3 1 4 1 1 2 1 1 0 1 3 1 2 0 0 0 2 1 2 0 0 3 2 1 1 1 1 1 2 1 0 1 0 0 0 1 0 0 2 1 1 0 1 0 1 0 1 0 0 1 0 1 1 0 0 0 1 0 0 0 2 1 1 0 1 1 0 1 1 0 0 1 0 3 1 3 0 0 2 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 2 0 0 ...
output:
7590964
result:
ok 1 number(s): "7590964"
Test #4:
score: 0
Accepted
time: 23ms
memory: 7624kb
input:
200 3 1 0 3 2 1 0 3 1 1 2 3 3 1 6 2 1 3 2 1 1 2 1 2 1 5 2 2 3 4 0 4 2 1 2 2 0 2 3 1 2 3 6 3 2 3 2 2 4 2 7 2 1 5 1 9 0 4 4 8 3 3 3 1 3 0 2 2 8 1 3 5 4 3 0 6 1 6 1 3 4 2 2 1 1 4 4 4 1 0 4 3 4 3 3 0 3 2 0 0 3 4 0 3 1 3 2 4 3 2 0 3 2 2 3 2 2 2 1 2 2 1 0 2 0 3 1 3 5 1 3 3 6 5 3 2 2 2 3 6 2 0 5 2 2 2 2 1 ...
output:
507844569
result:
ok 1 number(s): "507844569"
Test #5:
score: 0
Accepted
time: 5ms
memory: 6144kb
input:
100 4 8 2 5 4 4 3 0 2 7 2 3 4 4 1 2 3 4 4 4 3 3 3 3 3 2 4 1 3 5 5 1 4 6 1 1 1 3 2 3 2 1 0 1 4 4 2 4 2 5 3 5 1 6 2 3 3 1 4 4 4 1 4 4 3 4 2 0 2 3 6 1 3 3 5 4 1 1 2 3 0 3 2 2 1 3 3 2 5 6 3 2 3 3 5 4 2 3 4 4
output:
989550242
result:
ok 1 number(s): "989550242"
Test #6:
score: 0
Accepted
time: 1ms
memory: 5732kb
input:
1 1
output:
1
result:
ok 1 number(s): "1"
Test #7:
score: 0
Accepted
time: 1ms
memory: 5704kb
input:
500 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
1
result:
ok 1 number(s): "1"
Test #8:
score: 0
Accepted
time: 0ms
memory: 5748kb
input:
10 2 1 3 3 2 3 1 1 3 1
output:
165452340
result:
ok 1 number(s): "165452340"
Test #9:
score: 0
Accepted
time: 0ms
memory: 5640kb
input:
20 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0
output:
2
result:
ok 1 number(s): "2"
Test #10:
score: 0
Accepted
time: 1ms
memory: 5744kb
input:
20 0 0 1 0 0 0 0 1 0 0 0 0 0 0 2 0 1 0 0 0
output:
28
result:
ok 1 number(s): "28"
Test #11:
score: 0
Accepted
time: 1ms
memory: 5748kb
input:
10 1 1 1 1 1 1 1 1 1 1
output:
16796
result:
ok 1 number(s): "16796"
Test #12:
score: 0
Accepted
time: 6ms
memory: 6888kb
input:
300 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
431279497
result:
ok 1 number(s): "431279497"
Test #13:
score: 0
Accepted
time: 9ms
memory: 7020kb
input:
2 232 268
output:
929717758
result:
ok 1 number(s): "929717758"
Test #14:
score: 0
Accepted
time: 1ms
memory: 5684kb
input:
1 500
output:
1
result:
ok 1 number(s): "1"
Test #15:
score: 0
Accepted
time: 13ms
memory: 6104kb
input:
3 155 180 165
output:
911108550
result:
ok 1 number(s): "911108550"
Extra Test:
score: 0
Extra Test Passed