题解：P14568 【MX-S12-T3】排列

· · 题解

板子吧。

solution

构造排列计数题。限制给的比较强。考虑插入 dp。

从小到大插入 a_i。考虑从这个限制该怎么刻画成插入。

当我们要把某个数插入到位置 i 的时候：

所以我们就可以列出来一个状态 f_{i,j} 表示当前已经插入了前 i 个位置，并且还剩余 j 个位置可插。

转移是容易的：

暴力转移时 O(n^3) 的，后缀和优化一下即可做到 O(n^2)。

:::success[code]

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline void out(int x){
    if(x==0){putchar('0');return;}
    int len=0,k1=x,c[10005];
    if(k1<0)k1=-k1,putchar('-');
    while(k1)c[len++]=k1%10+'0',k1/=10;
    while(len--)putchar(c[len]);
}
const int N=1e6+5,mod=998244353;
int a[N],dp[N];
int addmod(int x,int y){x+=y;if(x>=mod)x-=mod;return x;}
int submod(int x,int y){x-=y;if(x<0)x+=mod;return x;}
int mulmod(int x,int y){return x*y%mod;}
bool chk(int n){
    bool flag2=0,flag3=0;
    for(int i=1;i<=n;i++){
        if(a[i]==0&&flag2)return 0;
        if(a[i]==1&&flag3)return 0;
        if(a[i]==2)flag2=1;
        if(a[i]==3)flag3=1;
    }return 1;
}
signed main(){
    int n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    if(!chk(n)){puts("0");return 0;}
    for(int i=1;i<=n;i++){
        if(a[i]==1||a[i]==0){
            if(i==1){dp[2]=1;continue;}
            for(int j=n+1;j>=1;j--)dp[j]=dp[j-1];
        }else{
            if(i==1){dp[1]=1;continue;}
            for(int j=n;j>=1;j--)dp[j]=addmod(dp[j],dp[j+1]);
        }
    }for(int i=n;i>=1;i--)dp[i]=addmod(dp[i],dp[i+1]);
    cout<<dp[1]%mod;
    return 0;
}

:::