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

板子吧。

solution

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

从小到大插入

a_i

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

当我们要把某个数插入到位置

i

的时候：

$op_i=0$ 时，要求其左侧最终没有比它更小的数。即在插入按递增的过程中，这只能在当前它是剩余区间的最左端时满足。
$op_i=1$ 时，同理只能在剩余区间最右端才能满足。
$op_i=2$ 时，要求其左侧最终的最大值小于它。递增插入时，这等价于当前已放的左侧不存在。
$op_i=3$ 时，同 $op_i=2$ 。

所以我们就可以列出来一个状态

f_{i,j}

表示当前已经插入了前

i

个位置，并且还剩余

j

个位置可插。

转移是容易的：

$op=\{0,1\}$ 时，每次插入相当于新增一个可插入位置。直接由 $f_{i-1,j-1}$ 转移过来即可。
$op=\{2,3\}$ 放这个数时它要放在已有的已预留的位置中的某一个，放完后可插入位置数不会增加，而且 $j$ 可以变成任意不超过原来的值，因此由 $f_{i-1,k}\ (∀k\le j)$ 转移而来。

暴力转移时

O(n^3)

的，后缀和优化一下即可做到

O(n^2)

。

code

CPP

#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;
}

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

文章操作

solution

相关推荐

评论

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