luoguP4778 Counting swaps

题目链接

题解

首先,对于每个\(i\)向\(a[i]\)连边.

这样会连出许多独立的环.

可以证明,交换操作不会跨越环.

每个环内的点到最终状态最少交换步数是 \(环的大小-1\)

那么设\(f[i]\)表示环大小为\(i\)的方案数

则
\[ f[i] = \sum_{x+y=i}f[x] * f[y] * g(x,y) * (^{i-1}_{x-1}) \]
其中
\[ g(x,y)=\{^{\frac{x+y}{2}{(x+y为偶数且x=y)}}_{x+y(else)} \]
打标可以发现\(f[n] = n^{n-2}(n≠1)\)

那么假设有\(k\)个环,第\(i\)个环大小为\(a[i]\)

则
\[ ans = \prod f[a[i]] *T \]
\(T\)是把\(n-k\)步分进每个环的方案数

\(T=\frac{(n-k)!}{\prod(a[i]-1)!}\)

还有另一种方法算\(T\)(具体看代码)

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, Mod = 1e9 + 9;
int fpow(int a, int b) {
    if (b <= 0) return 1;
    int res = 1;
    for (; b; b >>= 1, a = 1ll * a * a % Mod) if (b & 1) res = 1ll * res * a % Mod;
    return res;
}
bool vis[N];
int to[N], a[N];
int dfs(int x) {
    vis[x] = 1;
    if (vis[to[x]]) return 1;
    else return 1 + dfs(to[x]);
}
int fac[N], ifac[N]; 
int C(int n, int m) {
    if (n < m) return 0;
    return 1ll * fac[n] * ifac[n - m] % Mod * ifac[m] % Mod;
}
void solve() {
    int n, ans = 1;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &to[i]);
    memset(vis, 0, sizeof(vis));
    int len = 0;
    for (int i = 1; i <= n; i++) 
        if (!vis[i])
            a[++len] = dfs(i);
//  for (int i = 1; i <= len; i++) ans = 1ll * ans * fpow(a[i], a[i] - 2) % Mod * ifac[a[i] - 1] % Mod;
    for (int i = 1, sum = 0; i <= len; sum += a[i++] - 1)
        ans = 1ll * ans * fpow(a[i], a[i] - 2) % Mod * C(n - sum - len, a[i] - 1) % Mod;
    printf("%d\n", /*1ll * ans * fac[n - len] % Mod*/ans);
    return ;
}
int main() {
    int T;
    scanf("%d", &T);
    fac[0] = 1;
    for (int i = 1; i <= 100000; i++) fac[i] = 1ll * fac[i - 1] * i % Mod;
    ifac[100000] = fpow(fac[100000], Mod - 2);
    for (int i = 100000; i >= 1; i--) ifac[i - 1] = 1ll * ifac[i] * i % Mod; 
    while (T--) solve();
    return 0;
}

luoguP4778 Counting swaps

原文：https://www.cnblogs.com/zzy2005/p/11260970.html