QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#564782 | #7875. Queue Sorting | Bird# | WA | 77ms | 3976kb | C++17 | 1.2kb | 2024-09-15 14:29:16 | 2024-09-15 14:29:18 |
Judging History
answer
#include<bits/stdc++.h>
#define N 500
using namespace std;
const int mod=998244353;
int n,a[N+5],f[N+5],g[N+5],ans;
inline int fmod(const int &x) {return x<mod?x:x+mod;}
inline int qmod(const int &x) {return x<0?x+mod:x;}
inline void add(int &x,const int &y) {x=fmod(x+y);}
inline void sub(int &x,const int &y) {x=qmod(x-y);}
inline int quick_pow(int x,int b)
{
int ret=1;
for(;b;b>>=1,x=1ll*x*x%mod)
if(b&1) ret=1ll*ret*x%mod;
return ret;
}
inline int inv(int x) {return quick_pow(x,mod-2);}
int fac[N+5],ifac[N+5];
void init(int n=N)
{
fac[0]=1;for(int i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%mod;
ifac[n]=inv(fac[n]);for(int i=n;i;--i) ifac[i-1]=1ll*ifac[i]*i%mod;
}
inline int C(int n,int m)
{
return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int main()
{
scanf("%d",&n),init(N);
for(int i=1;i<=n;++i) scanf("%d",a+i);
f[a[n]]=1;
for(int i=n-1;i;--i) if(a[i])
{
memset(g,0,sizeof g);
for(int j=0;j<=N;++j) if(f[j])
{
add(g[j+a[i]],f[j]);
for(int k=1;k<=a[i];++k)
for(int x=1;x<=j;++x)
add(g[x+a[i]-k],1ll*f[j]*C(j-x+k-1,k-1)%mod);
}
swap(f,g);
}
for(int i=0;i<=N;++i) add(ans,f[i]);
printf("%d\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3964kb
input:
4 1 1 1 1
output:
14
result:
ok 1 number(s): "14"
Test #2:
score: -100
Wrong Answer
time: 77ms
memory: 3976kb
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:
-288856890
result:
wrong answer 1st numbers differ - expected: '507010274', found: '-288856890'