#C231114A. 平凡(ordinary)

前言（Front talk)

总结一下这道题：

认真读题！！！

网址（Website）

题目详情 - 平凡(ordinary) - Super

题解 - 平凡(ordinary) - Super

Problem - I - Codeforces

题目（Problem）

对于一个排列，定义为排列中长度为且字典序最小的子序列。定义一个长度为的序列的平凡度为满足以下条件的长度为的排列数量：

是的子序列。
。

现在给定，求的平凡度。

由于答案可能很大, 你只用输出答案后的值即可。

输入格式

从文件中读入数据。

第一行两个整数。

第二行个整数，表示序列。

保证互不相同。

输出格式

输出一行，一个整数，表示的平凡度。

样例

输入数据 1

3 2 
1 2

输出数据 1

输入数据 2

10 5
2 7 8 3 6

输出数据 2

【样例】

见选手目录下的与。

数据规模与约定

对于的数据： $；$ 。

保证互不相同。

本题使用打包测评。各子任务的附加限制及分值如下表所示:

子任务编号	附加限制	分值




	单调递增

	无特殊限制

题解（Solution）

正反向考虑都是可以的，但是正向考虑相对较复杂：

对于当前的数，首先要保证这个数不在原来的序列中，其次，如果要“干掉”序列，那么其一定要放在比当前数大的周围，或者放在首个满足的地方的后面，那么容斥一下就好了。

倒着来就比较简单，直接求出乱加的方案数，然后求出的情况，处理就好了。

代码（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;
}