题解：CF1091DNew Year and the Permutation Concatenation

好题

很明显可以把答案拆成两部分计算

第一部分很明显，每个排列都满足排列，即为

!n

那第二部分就是两个排列的部分拼一块儿，我们枚举 i 表示前半部分有i个数，要选数，所以有

C_{n}^{i}

，数字要排列，所以乘上

!i

(其实就是

A_{n}^{i}

)，前面的数已经确定，再乘排列

!(n-i)

挺有道理，但没结束

我们拿

n=3

的第二部分来举例，当

i=1

时前半部分为：23,13,12 ,注意到不会有 32 ,31, 21，因为他们要搭配的数，在自己的排列中正好最后一次出现在最前面，前面数的全排列少了一半，故将

!(n-i)

减一

答案：

ans=!n+\sum_{i = 1}^{n-1} A_{n}^{i}*!(n-i)

别忘取模。

Code:

CPP

#include<bits/stdc++.h>
#define int long long
#define lowbit(x) x&-x
#define P(x,y) make_pair(x,y)
#define PII pair<int,int>
#define x first
#define y second
using namespace std;
const int mod=998244353;
double eps=1e-6;
const int N=1e6+10;
int jie[N];

int n;
int qpow(int a,int b)
{
	int res=1;
	for(;b;b>>=1)
	{
		if(b&1)	res=res*a%mod;
		a=a*a%mod;
	}
	return res;
}
int inv(int x)
{
	return qpow(x,mod-2);
}
int C(int n,int m)
{
	return jie[m]*inv(jie[n])%mod*inv(jie[m-n])%mod;
}
signed main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout.tie(0);
	cin>>n;
	jie[0]=1;
	for(int i=1;i<=n;i++)	jie[i]=jie[i-1]*i%mod;
	int ans=jie[n];
	for(int i=1;i<n;i++)
	{
		ans=(ans+C(i,n)*jie[i]%mod*(jie[n-i]+mod-1)%mod)%mod;
	}
	cout<<ans<<endl;
	return 0;
}

感觉码风还行

总结：这个题顺水推舟就想出来了，但是要注意到

!(n-i)

减一的细节

题解：CF1091DNew Year and the Permutation Concatenation

文章操作

相关推荐

评论

题解：CF1091DNew Year and the Permutation Concatenation