Codeforces - 1391C - Cyclic Permutations（思维 + 组合数学 + 数论 + 图论、*1500）

1391C - Cyclic Permutations（⇔源地址）

• 1391C - Cyclic Permutations（⇔源地址）
  • tag
  • 题意
  • 思路
  • AC代码
  • 错误次数：0

tag

⇔思维、⇔组合数学、⇔数论、⇔图论、⇔*1500。

看起来是大杂烩题，实际上只用到了各个知识点的定义，只要深入的掌握这些定义，这就是一道结论题。

题意

给出一个长度为 \(N\) 的全排列，用 \(a_1a_2a_3…a_N\) 表示，对于每一个位置的数 \(a_i\) ，分别找到其左、右大于其的第一个数，记为 \(a_l,a_r\) ，建图连结 \(a_i,a_l\) 和 \(a_ia_r\) 。

对于这样操作所构造的图，如果它存在一个环，那么称这个图是GOOD。

现在给出 \(N\) ，求解所有长度为 \(N\) 的全排列构造的 \(N\) 张图有多少张是GOOD的。

思路

这是一道思维题。容易发现，无论怎么连，这张图上至少有 \(N-1\) 条边，因为除了最大的那个数以外每个数都至少跟一个点连结。

再由图论基础知识，对于一棵树，只需要再连任意一条边就会成环，而我们发现，无法再连边的排列比较好构造，即拥有单峰的序列。那么，答案即为：能构造出的全部合法序列的数量减去单峰序列的数量。

现在问题在于怎么求解单峰序列。我们移走最大的那个数，对于剩下的 \(N-1\) 个元素，我们从中任选 \(0,1,2,…,N-1\) 个放到峰左边，剩下的放峰右边，根据组合数公式，得到这样一共有 \(2^{N-1}\) 种合法单峰序列。

最终，答案即为 \(N!-2^{N-1}\) ，套用 \(\tt Zmod\) 函数无脑求解即可。

AC代码

using namespace Zmod;
signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int n; cin >> n;
	Z ans = 1;
	for (int i = 1; i <= n; ++ i) ans *= i;
	ans -= mypow((Z)2, n - 1);
	cout << ans;
	
	return 0;
}

错误次数：0

文 / WIDA
2022.11.01 成文
首发于WIDA个人博客，仅供学习讨论