QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#276207#7875. Queue SortingkathRE 1ms3488kbC++171.4kb2023-12-05 18:07:332023-12-05 18:07:33

Judging History

你现在查看的是最新测评结果

  • [2023-12-05 18:07:33]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3488kb
  • [2023-12-05 18:07:33]
  • 提交

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;
    ll cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]==0)continue;
        vector<ll>g=f;
        
        for(int j=1;j<=cnt;j++)
            for(int x=0;x<=a[i]-1;x++)
            add(g[j],C(cnt-j+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+1]-x-1)%P);
                }
            }
        }
        cnt+=a[i];
        swap(g,f);
    }
    ll rs=0;
    for(int i=0;i<=n;i++)
    add(rs,f[i]);
    cout<<rs*2%P<<endl;
}


/*

4
1 1 1 1

*/

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3488kb

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 ...

output:


result: