QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#625779 | #7875. Queue Sorting | frankly6 | TL | 0ms | 3516kb | C++17 | 1.6kb | 2024-10-09 21:00:53 | 2024-10-09 21:00:53 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
const int MX=505;
const int p=998244353;
int N, ar[MX], fac[MX];
int f[MX][MX];
int read()
{
int r=0, f=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') {r=r*10+ch-'0'; ch=getchar();}
return r*f;
}
int qpow(int x, int pow)
{
int ans=1;
while(pow)
{
if(pow&1) ans=ans*x%p;
x=x*x%p;
pow>>=1;
}
return ans;
}
int inv(int x){return qpow(x,p-2);}
int C(int n, int m){return fac[n]*inv(fac[m])%p*inv(fac[n-m])%p;}
signed main()
{
// freopen("testdata.in","r",stdin);
fac[0]=1;
for(int i=1;i<=500;i++) fac[i]=fac[i-1]*i%p;
N=read();
int sum=0;
for(int i=1;i<=N;i++) ar[i]=read(), sum+=ar[i];
//f[i][j] ins <= i numbers, the increase pos is j
f[1][ar[1]+1]=1;
for(int i=1;i<N;i++)
{
for(int j=1;j<=sum;j++)
{
for(int k=2;k<=j+ar[i];k++)
{
int n1=j-1, n2=ar[i];
// cout << "i+1=" << i+1 << ", j=" << j << ", k=" << k << ", n1=" << n1 << ", n2=" << n2 << '\n';
f[i+1][k]=(f[i+1][k]+f[i][j]*(fac[n1+n2-1]*inv(fac[n1])%p*inv(fac[n2-1])%p)%p)%p;
}
}
}
// for(int i=1;i<=N;i++)
// for(int k=1;k<=sum;k++)
// cout << "i=" << i << ", k=" << k << ", f=" << f[i][k] << '\n';
int ans=0;
for(int i=1;i<=sum+1;i++) ans+=f[N][i];
cout << ans%p << '\n';
return (0-0);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3516kb
input:
4 1 1 1 1
output:
14
result:
ok 1 number(s): "14"
Test #2:
score: -100
Time Limit Exceeded
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 ...