QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#276242 | #7875. Queue Sorting | kath | RE | 0ms | 3424kb | C++17 | 1.5kb | 2023-12-05 18:36:45 | 2023-12-05 18:36:46 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int P=998244353;
ll POW(ll a,ll k=P-2,ll rs=1){
while(k)
{
if(k&1)rs=rs*a%P;
a=a*a%P;
k>>=1;
}
return rs;
}
const int N=510;
ll fac[N],inv[N];
void init()
{
fac[0]=inv[0]=1;
for(int i=1;i<N;i++)
fac[i]=fac[i-1]*i%P;
inv[N-1]=POW(fac[N-1]);
for(int i=N-2;i;i--)
inv[i]=inv[i+1]*(i+1)%P;
}
ll C(int a,int b)
{
if(a<b||a<0||b<0)
return 0;
return fac[a]*inv[a-b]%P*inv[b]%P;
}
void add(ll& x, ll y )
{
x+=y;
if(x>=P)x-=P;
}
int main()
{
init();
int n;
cin>>n;
vector<int>a(n+1);
for(int i=1;i<=n;i++)
cin>>a[i];
vector<ll>f(n+1);
f[0]=1;
int cnt=0;
for(int i=1;i<=n;i++)
{
if(a[i]==0)continue;
vector<ll>g(n+1);
g[0]=1;
for(int j=2;j<=cnt;j++)
g[j+a[i]]=f[j];
for(int k=2;k<=cnt+1;k++)
for(int x=0;x<=a[i]-1;x++)
add(g[x+k],C(cnt-(k-1)+a[i]-x-1,a[i]-x-1));
for(int j=2;j<=cnt;j++)
{
for(int x=0;x<=a[i]-1;x++)
{
for(int k=1;k<j;k++)
{
add(g[x+k+1],f[j]*C(j-1 - k + a[i]- x -1 ,a[i]-x-1)%P);
}
}
}
cnt+=a[i];
swap(g,f);
}
ll rs=0;
for(int i=0;i<=n;i++)
add(rs,f[i]);
// cout<<f[1]<<endl;
cout<<rs<<endl;
}
/*
4
1 1 1 1
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3424kb
input:
4 1 1 1 1
output:
14
result:
ok 1 number(s): "14"
Test #2:
score: -100
Runtime Error
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 ...