[codeforces 1391C] Cyclic Permutations 容斥原理+手工打表找规律

08/11 07:58
阅读数 423

Codeforces Round #663 (Div. 2)   参与排名人数13075

[codeforces 1391C]   Cyclic Permutations   容斥原理+手工打表找规律

总目录详见https://blog.csdn.net/mrcrack/article/details/103564004

在线测评地址https://codeforces.com/contest/1391/problem/C

Problem Lang Verdict Time Memory
C - Cyclic Permutations GNU C++17 Accepted 46 ms 3900 KB

题目大意:给出一个排列数,若j<i,a[j]>a[i],请注意,j在i的左侧,在所有大于a[i]的数据中,j是离得最近的,可将j,i连上线;若i<j,a[i]<a[j],j在i的右侧,在所有大于a[i]的数据中,j是离得最近的,可将j,i连上线。在位置序号的连线中,若出现了环,我们称这样的排列数为好的排列数。给出n,统计其中好的排列数的个数。

n=4. [4,2,1,3]是好的排列数,说明如下:
a[1]=4,
a[2]=2,(a[1]=4)>(a[2]=2),位置1,2可连线。
a[2]=2,(a[2]=2)<(a[4]=3),位置2,4可连线。
a[3]=1,(a[2]=2)>(a[3]=1),位置2,3可连线。
a[3]=1,(a[3]=1)<(a[4]=3),位置3,4可连线。
a[4]=3,(a[1]=4)>(a[4]=3),位置1,4可连线。

上述数据对应图形如下:

基本思路:

n=3
好的排列数(有山谷)
2 1 3
3 1 2
不好的排列数(只有山峰)
1 2 3
1 3 2
2 3 1
3 2 1

容斥原理3!-4=2

n=4
好的排列数(有山谷)
1 3 2 4
1 4 2 3
2 1 3 4
2 1 4 3
2 3 1 4
2 4 1 3
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
不好的排列数(只有山峰)
1 2 (4) 3
1 2 3 (4)

1 3 (4) 2
1 (4) 3 2

2 3 (4) 1
2 (4) 3 1

(4) 3 2 1
3 (4) 2 1
容斥原理4!-4*2=16

AC代码如下:

#include <stdio.h>
#define mod 1000000007
#define LL long long
int main(){
	int n,i;
	LL ans,p,q;
	scanf("%d",&n);
	p=1*2*3,q=4;//p代表排列数的数量,q代表只有山峰的数量
	for(i=4;i<=n;i++)p=p*i%mod,q=q*2%mod;
	ans=((p-q)%mod+mod)%mod;//就算p-q是负数也能处理。
	printf("%lld\n",ans);
	return 0;
}

 

展开阅读全文
c++
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部