Codeforces Good Bye 2018 D (1091D) New Year and the Permutation Concatenation

题意：给n!个n的排列，按字典序从小到大连成一条序列，例如3的情况为：[1,2,3, 1,3,2, 2,1,3 ,2,3,1 ,3,1,2 ,3,2,1],问其中长度为n，且和为sum=n*(n+1)/2的序列有多少个？

思路（官方题解）：我们考虑一下next_perumation函数产生字典序递增的全排列的过程：

假设某一个序列长度为n，最长的递减的后缀长度k，那么它的下一个排列是这样产生的：选取序列第n-k个数，与后k个数中比第n - k个数大的最小的数交换，然后将后k个数按从小到大排序。

例如序列1,2,5,4,3的下一个排列为1,3,2,4,5。我们观察发现：这种时候1,2,(5,4,3,1,3,)2,4,5不满足和为sum了，因为在产生下一个排列的过程中，第n-k个位置的数被替换了。

也就是说，假设一个序列存在长度为k的递减后缀，那么这个后缀不能产生一个长度为sum的序列。例如，1,2,(5,4,3,1,3,)2,4,5不行，但是1,(2,5,4,3,1,)3,2,4,5可以。

所以，我们的任务是找出每个长度为k的递减后缀有多少个？应该为C(n,n-k)*(n-k)!=A(n,n-k)=n!/k!个。因为只要选了前面n-k个数，后面长度为k的递减的序列是固定的，所以我们只需要选n-k个数全排列就行了。

我们可以得到最终的答案了：一共有n*n!-(n-1)个序列，要减去( ∑(k from 1 to n-1) n!/k! )- (n-1)个。

为什么要减去n-1个呢？我们来看最后一个排列（假设n为5）5,4,3,2,1 。5之后的序列不存在，所以要从总的序列数中减去。而这(n-1)个不存在的序列恰好会被判定为不满足题意，也应该减去。

所以总的来说，答案应该是：(所有的序列-不存在的序列）-（不满足的序列-不存在的序列）。我们可以把答案写的更优雅一点：ans=n*n!-∑(k from 1 to n-1) n!/k!。

代码：

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cmath>

#include<cstring>

#include<map>

#include<set>

#include<bitset>

#include<queue>

#include<vector>

#include<stack>

#define INF 0x3f3f3f3f

#define pii pair<int,int>

#define LL long long

#define fi first

#define se second

#define ls(x) (x<<1)

#define rs(x) ((x<<1)+1)

#define lowbit(x) (x&(-x))

using namespace std;

const int maxn=1000010;

const LL mod=998244353;

LL s[maxn],f[maxn];//s[k]是n!/k!

int main(){

	LL n;

	scanf("%lld",&n);

	f[0]=1,s[n]=1;

	for(LL i=1;i<=n;i++){

		f[i]=(f[i-1]*i)%mod;

	}

	for(LL i=n-1;i>=1;i--){

		s[i]=(s[i+1]*(i+1))%mod;

	}

	LL ans=(n*(f[n]))%mod;

	for(LL i=1;i<=n-1;i++){

		ans=(ans-s[i]+mod)%mod;

	}

	cout<<ans<<endl;

}

巴特西

Codeforces Good Bye 2018 D (1091D) New Year and the Permutation Concatenation

最新文章

热门文章