QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#625821#7875. Queue Sortingfrankly6TL 0ms3536kbC++171.6kb2024-10-09 21:11:492024-10-09 21:11:51

Judging History

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

  • [2024-10-09 21:11:51]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3536kb
  • [2024-10-09 21:11:49]
  • 提交

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], pre[MX];
int f[MX][2*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);}
signed main()
{
    // freopen("testdata.in","r",stdin);
    fac[0]=1;
    for(int i=1;i<=504;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];
        pre[i]=pre[i-1]+ar[i];
        if(ar[i]==0) i--, N--;
    }
    //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=2;j<=pre[i]+1;j++)
        {
            for(int k=2;k<=j+ar[i+1];k++)
            {
                int n1=j-1, n2=ar[i+1];
                // cout << "i+1=" << i+1 << ", j=" << j << ", k=" << k << ", n1=" << n1 << ", n2=" << n2 << '\n'; 
                if(n2>=1) 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);
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3536kb

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

output:


result: