11.14 小结

· · 个人记录

T1

构造一个 1\to n 的排列 P，再给出一个长度为 k 的序列 A，定义 P 合法满足：

求满足条件的序列 P 的可能数量，答案对 998244353 取模。

题解

首先考虑容斥一下。

我们很容易算出满足条件一的答案总数：n!/k!，考虑在这个的基础上减去 P 的长度为 k 的字典序最小子序列刚好是 A 的情况数。

考虑如何计算哪些情况下 P 的长度为 k 的最小子序列为 A 的情况数，我们的计算方式是向 A 添加的方式。

比如形如这样的一个 A，那么每一个 A_i 前面必然不可能插入比它小的数，否则可以用前面的数替换掉当前的数。

其次，如果一个数前面已经插入了一个比较大的数，那么这个数一定得是在排列的后缀上的，否则仍然能够替换掉当前的数使得字典序更小。

于是我们找到单调递增的最长前缀，这个以后的部分就一定是排列的一个后缀。

然后对于每一个没有出现在序列 AA 中的数，可以从小到大依次插入，根据“每一个 A_i 前面必然不可能插入比它小的数”的性质，我们可以判断有多少个“空”可以插入，然后乘法原理将所有数的插入方案乘起来就可以了。

CODE:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5,mod=998244353;
int n,k,p=1,ans=1,pos,kg;
int a[N],t[N],isfixed[N];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    for(int i=k+1;i<=n;i++){
        p=p*i%mod;
    }
    for(int i=1;i<=k;i++){
        cin>>a[i];
        t[a[i]]=1;
    }
    for(int i=1;i<=k;i++){
        if(a[i]>a[i+1]){
            pos=i;
            for(int j=pos+1;j<=n;j++){
                isfixed[a[j]]=1;//标记必须在末尾的数 
            }
            break;
        }
    }
    a[k+1]=1e9+7;
    for(int i=1;i<=n;i++){//从小到大枚举
        if(!isfixed[i]){//不是必须在后缀的数
            if(!t[i]){//需要添加的数 
                ans=ans*(kg+(i>a[pos]?1:0))%mod;
            }
            kg++;
        }
    }
    cout<<(p-ans+mod)%mod;
    return 0;
}