QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#626205#7875. Queue Sortingfrankly6TL 0ms0kbC++171.7kb2024-10-10 00:23:462024-10-10 00:23:46

Judging History

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

  • [2024-10-10 00:23:46]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-10-10 00:23:46]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
typedef long long ll;
const int MX=505;
const int p=998244353;

int N, ar[MX], fac[MX], pre[MX], invf[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);}
int C(int n, int m){return fac[n]*invf[m]%p*invf[n-m]%p;}
signed main()
{
    freopen("testdata.in","r",stdin);
    fac[0]=1;
    for(int i=1;i<=504;i++) fac[i]=fac[i-1]*i%p;
    for(int i=0;i<=504;i++) invf[i]=inv(fac[i]);
    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[0][0]=1;
    for(int i=1;i<=N;i++)
    {
        for(int j=0;j<=pre[i-1];j++)
        {
            if(!f[i-1][j]) continue;
            f[i][j]=(f[i][j]+f[i-1][j])%p;
            for(int k=j+1;k<pre[i];k++) //up pos
            {   
                int l=max(ll(0),ar[i]-(k-j));
                int r=min(ar[i]-1,pre[i]-k-1);
                for(int m=l;m<=r;m++) // m num before
                    f[i][k]=(f[i][k]+f[i-1][j]*C(k-j-1,ar[i]-m-1)%p)%p;
            }
        }
    }
    // for(int i=0;i<=N;i++) for(int k=0;k<=sum;k++) cout << "i=" << i << ", k=" << k << ", f=" << f[i][k] << '\n';
    int ans=0;
    for(int i=0;i<=sum;i++) ans=(ans+f[N][i])%p;
    cout << ans << '\n';
    return (0-0);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

4
1 1 1 1

output:


result: