#C231114A. 平凡(ordinary)
标签（Label）
- 思维
- 值域转下标
网址（Website）
题目（Problem）
对于一个排列 $P$，定义 $f_{K}(P)$ 为排列 $P$ 中长度为 $K$ 且字典序最小的子序列。定义一个长度为 $K$ 的序列 $A$ 的平凡度为满足以下条件的长度为 $N$ 的排列 $P$ 数量：
- $A$ 是 $P$ 的子序列。
- $f_{K}(P) \neq A$ 。
现在给定 $N, K, A$，求 $A$ 的平凡度。
由于答案可能很大, 你只用输出答案 $\bmod \ 998244353$ 后的值即可。
输入格式
从文件 $ordinary.in$ 中读入数据。
第一行两个整数 $N,K$ 。
第二行 $K$ 个整数，表示序列 $A$ 。
保证 $A_{i}$ 互不相同。
输出格式
输出一行，一个整数，表示 $A$ 的平凡度。
样例
输入数据 1
3 2
1 2输出数据 1
0输入数据 2
10 5
2 7 8 3 6输出数据 2
30240【样例 $3-6$ 】
见选手目录下的 $ordinary/ordinary3\sim 6.in$ 与 $ordinary/ordinary3\sim 6.ans$。
数据规模与约定
对于 $100 %$ 的数据：$1 \leq K \leq N \leq 10^{6}；1 \leq A_{i} \leq N$。
保证 $A_{i}$ 互不相同。
本题使用打包测评。各子任务的附加限制及分值如下表所示:
| 子任务编号 | 附加限制 | 分值 |
|---|---|---|
| $1$ | $K \leq N \leq 10$ | $10$ |
| $2$ | $K=N$ | $5$ |
| $3$ | $A_{i}=i$ | $5$ |
| $4$ | $N=K+1$ | $15$ |
| $5$ | $A_{i}$ 单调递增 | $15$ |
| $6$ | $K≤N≤2000$ | $15$ |
| $7$ | 无特殊限制 | $35$ |
题解（Solution）
$\qquad$正反向考虑都是可以的，但是正向考虑相对较复杂：
$\qquad$对于当前的数，首先要保证这个数不在原来的序列 $a_i$ 中，其次，如果要“干掉” $a_i$ 序列，那么其一定要放在比当前数大的 $a_i$ 周围，或者放在首个满足 $a_i>a_{i+1}$ 的地方的后面，那么容斥一下就好了。
$\qquad$倒着来就比较简单，直接求出乱加的方案数 $ \frac{n !}{m !}$ ，然后求出 $f_K(P)=A$ 的情况，处理就好了。
后补：这里面有一个很重要的点：如果 $A$ 序列中出现 $a[i]>a[i+1]$ 那么 $i+1$ 后面的位置就不能放。因此，对于一个点 $x$ ，能对平凡度产生贡献的位置只有 $a[i]<x$ 的位置，这样统计满足条件的贡献即可。
代码（Code）
#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define int long long
inline int input(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int N = 1012345;
int n,m,a[N];
bitset<N> fix,vst;
signed main(){
freopen("ordinary.in","r",stdin);
freopen("ordinary.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>m;
int p=1,ans=1,pos=0;
for(int i=m+1;i<=n;i++) p=p*i%mod;
for(int i=1;i<=m;i++){
a[i]=input();
if(vst[a[i]]) return cout<<'0',0;vst[a[i]]=true;
}for(int i=1;i<=m;i++)
if(a[i]>a[i+1]){pos=i;for(int j=i+1;j<=n;j++) fix[a[j]]=true;break;}
a[m+1]=inf;
for(int i=1,sum=0;i<=n;i++)
if(!fix[i]){//如果当前的值不在pos后面
//当且仅当不在a[i]中时有答案（当前值大于a[pos]的值时可以放在a[pos]的前面（否则放在a[pos]前面就是当前值更优了）
if(!vst[i]){ans=ans*(sum+(i>a[pos]))%mod;}
sum++;//大的数只能放在小的数后面，sum记录的是小的数的个数
}
cerr<<ans<<'\n';
cout<<(p-ans+mod)%mod<<'\n';
return 0;
}
