QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#487021#6410. Classical DP Problemucup-team1525#WA 7ms103524kbC++202.1kb2024-07-22 15:20:502024-07-22 15:20:52

Judging History

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

  • [2024-07-22 15:20:52]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:103524kb
  • [2024-07-22 15:20:50]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=5e3;
const int mod=998244353;
int fac[N+5],ifac[N+5];
int add(int x,int y){ return (x+=y)>=mod?x-mod:x; }
int sub(int x,int y){ return (x-=y)<0?x+mod:x; }
int ksm(ll x,int tp,int s=1){
    for(;tp;x=x*x%mod,tp>>=1) if(tp&1) s=x*s%mod;
    return s;
}
void prep(){
    fac[0]=1;
    for(int i=1;i<=N;i++) fac[i]=1ll*fac[i-1]*i%mod;
    ifac[N]=ksm(fac[N],mod-2);
    for(int i=N;i;i--) ifac[i-1]=1ll*ifac[i]*i%mod;
}
int C(int n,int m){
    return n<0||m<0||n<m?0:1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int n;
int a[N+5];
int r,s;
int work1(int c0,int c1,int c2){
    static int f[N+5][N+5];
    memset(f,0,sizeof f);
    int x=a[c0];
    f[0][0]=1;
    for(int i=1;i<=c2;i++){
        int h=a[c0+i];
        for(int j=0;j<=min(i,x);j++){
            f[i][j]=1ll*(h-x+j)*f[i-1][j]%mod;
            if(j) f[i][j]=(f[i][j]+1ll*(x-j+1)*f[i-1][j-1])%mod;
        }
    }
    return f[c2][x];
}
void work2(int c0,int c1,int c2){
    static int f[N+5][N+5],c[N+5];
    for(int i=1;i<=c0+c1;i++)
        c[a[i]]++;
    for(int j=n;j;j--) c[j]+=c[j+1];
    f[0][0]=1;
    for(int i=1;i<=r;i++)
        for(int j=0;j<=min(r-c2,i);j++){
            f[i][j]=f[i-1][j];
            if(j) f[i][j]=(f[i][j]+1ll*c[i]*f[i-1][j-1])%mod;
        }
    for(int c=c2;c<=r;c++){
        int t=0;
        for(int i=0;i<=c2;i++){
            if(c2-i&1) t=sub(t,ksm(i,c,C(c2,i)));
            else t=add(t,ksm(i,c,C(c2,i)));
        }
        s=(s+1ll*f[r][r-c]*(t+mod))%mod;
    }
    if(c1+c2==r){
        s=add(s,sub(work1(c0,0,n-c0),fac[r]));
    }
}
int main(){
    prep();
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=n;i;i--)
        if(a[i]<=n-i){
            r=n-i;
            break;    
        }
    int c0,c1,c2; c0=c1=c2=0;
    for(int i=1;i<=n;i++)
        if(a[i]<r) c0++;
        else if(a[i]==r) c1++;
        else c2++;
    if(c1==0){
        s=work1(c0,c1,c2);
    }
    else{
        work2(c0,c1,c2);
    }
    printf("%d %d\n",r,s);
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 102684kb

input:

3
1 2 3

output:

2 6

result:

ok 2 number(s): "2 6"

Test #2:

score: -100
Wrong Answer
time: 7ms
memory: 103524kb

input:

1
1

output:

0 1

result:

wrong answer 1st numbers differ - expected: '1', found: '0'