[算进] 计数交换 (CH3602)(组合计数)

Problem

ACwing 题目地址

洛谷 题目地址

经典题,好题。另外感谢 Rose_max 大佬的博客让我搞懂了这题。


Solution 1

对于一个排列 (p_1,p_2,...,p_n),每一个 (p_i)(i) 连一条无向边,构成一张由若干个简单环组成的无向图。目标状态即 (n) 个自环。

引理:将一个大小为 (k) 的简单环变成 (k) 个自环,至少需要 (k-1) 次交换。

利用数学归纳法,证明很简单,这里省略证明。

由此我们可以得到一个推论:假设图中有 (k) 个环,那么最小交换步数是 (n-k)


下面我们来考虑计数。

(f[i]) 表示一个大小为 (i) 的环,在保证交换次数最少的情况下,有多少种方法将其变成目标状态。

每一次交换可以把大小为 (i) 的环拆成大小为 (x,y) 的两个环,(x+y=n)。设 (T(x,y)) 表示有多少种交换方法可以将一个大小为 (i) 的环拆成两个大小分别为 (x,y) 的环。可以发现:当 (x=y) 时,有一半的方法是重复的,(T(x,y)=x);否则 (T(x,y)=x+y)

将一个大小为 (i) 的环拆成大小为 (x,y) 的两个环后,(x) 环需要 (x-1) 次交换达到目标状态,将这 (x-1) 次操作记为 (x-1)(0),同理将 (y) 环的 (y-1) 次操作记为 (y-1)(1)由于 (x) 环与 (y) 环的操作互不干扰,两边的操作可以随意排列,因此这里就是一个多重集的全排列

综上所述,可以得到 (f[i]) 的状态转移方程:

[f[i]=sum_{x+y=i} f[x]*f[y]*T(x,y)*frac{(i-2)!}{(x-1)!(y-1)!} ]

(或许这个式子可以 (FFT) 一下,如果你可以将其 (FFT),记得告诉我一下做法qwq)


假设排列 (p_1,p_2,...,p_n) 中有 (k) 个大小分别为 (L_1,L_2,...,L_k) 的环。因为这 (k) 个环的操作互不干扰,可以记其中第 (i) 个环的 (L_i-1) 次操作为 (L_i-1)(i)总操作就是一个多重集的全排列。答案是:

[Ans=(prod_{i=1}^k f[L_i])*(frac{(n-k)!}{prod_{i=1}^k (L_i-1)!}) ]

(mod 10^9+9) 意义下,上述除法可以用费马小定理求得逆元解决。复杂度带一个 (log)

时间复杂度:(O(n^2 log n))

(f[ ]) 数组和阶乘部分代码(预处理)

void Init() {
	fc[0] = 1;	//阶乘 factorial
	for(int i=1;i<=1000;++i) fc[i] = fc[i-1] * i % mod;
	f[1] = 1;
	for(int i=2;i<=1000;++i) {
		for(int j=1;j<=i/2;++j) {	// (x,y)和(y,x)只能算一次 
			int inv = Pow(fc[i-j-1]*fc[j-1]%mod, mod-2);
			f[i] = (f[i] + f[i-j]*f[j]%mod*T(i-j,j)%mod*fc[i-2]%mod*inv%mod) % mod;
		}
	}
	for(int i=1;i<=10;++i) printf("%lld
",f[i]);
}

Solution 2

注意到上述算法并不能通过此题((n leqslant 10^5))。瓶颈在于求 (f[ ]) 数组这里。于是我们打表出 (f[ ]) 数组的前 (10) 项:

1 1 3 16 125 1296 16807 262144 4782969 100000000

将其输入进 (OEIS),或者是对乘方敏感的同学可以发现:(f[n]=n^{n-2})。有了这个规律,我们便可以解决这个问题了。

时间复杂度:(O(n log n))

Code

Talk is cheap.Show me the code.

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
	int x=0,f=1; char ch=getchar();
	while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
	while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
	return x * f;
}
const int N = 1e5+7, mod = 1e9+9;
int n,cnt,ans;
int p[N],f[N],fc[N],L[N];
bool vis[N];
int Pow(int x,int y) {
	int res = 1, base = x;
	while(y) {
		if(y&1) res = res*base%mod; base = base*base%mod; y >>= 1;
	}
	return res;
}
void Init2() {
	fc[0] = 1;
	for(int i=1;i<N;++i) fc[i] = fc[i-1] * i % mod;
	f[1] = 1;
	for(int i=2;i<N;++i) f[i] = Pow(i,i-2);
}
int Dfs(int u) {
	vis[u] = 1;
	if(vis[p[u]]) return 1;
	return Dfs(p[u]) + 1;
}
void work() {
	cnt = 0;
	memset(vis, 0, sizeof(vis));
	n = read();
	for(int i=1;i<=n;++i) p[i] = read();
	for(int i=1;i<=n;++i)
		if(!vis[i]) L[++cnt] = Dfs(i);
	ans = fc[n-cnt] % mod;
	for(int i=1;i<=cnt;++i) {
		int inv = Pow(fc[L[i]-1], mod-2);
		ans = ans*f[L[i]]%mod*inv%mod;
	}
	printf("%lld
",ans);
}
signed main()
{
	Init2();
	int T = read();
	while(T--) work();
	return 0;
}

Summary

模数看错自闭一中午,所以大家在任何地方都要细心呀!!

这个题目让我学会两大经典模型:

  • 将排列 (p_1,p_2,...,p_n) 变成递增序列的最小交换次数。

  • 将排列 (p_1,p_2,...,p_n) 变成递增序列,保证最小交换次数下的方案数

另外让我学会一些计数题的 技巧/思路/套路

原文地址:https://www.cnblogs.com/BaseAI/p/12221703.html