题意描述

Counting swaps

给定一个 \(1∼n\) 的排列，求用最少的交换次数将给定排列变成单调上升的序列 \(1,2,\cdots,n\) 的方案数。

结果对 \(10^9+9\) 取模。

据说很套路的计数题，那么我连套路都不会了。

算法分析

基本性质

假设我们将初始序列 \(p\) 的每一对 \((i,p_i)\) 连边，我们将得到一张 \(n\) 个点 \(n\) 条边的图。

而且这张图由 \(k\leq n\) 个环构成，证明如下：

由于 \(p\) 是 \(1∼n\) 的一个排列，所以每个点的入度和出度一定均为 \(1\)。

允许自环的存在，显然这张图由多个环组成。

同时不难证明：一个长的为 \(n\) 的环变为 \(n\) 个自环的最少操作次数为 \(n-1\) 次。

以上是本题基本性质，是计数前比不可少的转化。

简单计数

显然每个环与其它环无关，我们只考虑环内情况，之后再合并。

同时环内的交换顺序也是任意的，这也是需要考虑的。

转化为图上模型后发现交换两个数相当于将环 \(n\) 断开为环 \(x+y(x+y=n)\)。

其中断开方式记为 \(T(x,y)\)，讨论一下不难求解。

设 \(F_n\) 表示用最少步数将长度为 \(n\) 的环变为 \(n\) 个自环的方案数，则有：

\[F_n=\sum_{x+y=n} T(x,y)\times F_x\times F_y\times \frac{(n-2)!}{(x-1)!(y-1)!} \]

假设 \(k\) 为环的个数，\(l_i\) 表示环 \(i\) 的长度，那么显然：

\[ans=\Pi_{i=1}^k F_{l_i}\times \frac{(n-k)!}{\Pi_{i=1}^k (l_i-1)!} \]

可惜这样时间复杂度为 \(O(n^2\log n)\)，好像不太行，主要时间浪费在 \(F_i\) 的预处理上。

当时我们可以用这个代码打表找规律求解。

代码如下：

LL fac[2000], f[2000];
const LL MOD = 1e9 + 9;

LL T(LL x,LL y){return (x == y && ((x + y) % 2 == 0)) ? x : x + y;}

LL Pow(LL a, LL b){
    int sum=1;
    for(; b; b >>= 1){
        if(b & 1) sum = sum * a % MOD;
        a = a * a % MOD;
    }
    return sum;
}

int main(){
    fac[0] = 1;
    for(int i=1; i<=1000; i++) fac[i] = fac[i-1] * i % MOD;
    f[1] = 1;
    for(LL i=2; i<=1000; i++)
        for(LL j=1; j<=i/2; j++){
            LL x = i-j, y = j;
            LL ans = T(x, y) * Pow(fac[x-1] * fac[y-1] % MOD, MOD - 2) % MOD;
            f[i] = (f[i] + ans * f[x] % MOD * f[y] % MOD * fac[i-2] % MOD) % MOD;
        }
    for(int i=1; i<=10; i++) printf("%lld\n", f[i]);
    return 0;
}

优化求解

打出表后不难发现，\(F_i=i^{i-2}\)。

然后根据上述思路进行求解即可。

时间复杂度 \(O(n\log n)\)。

代码实现

注意细节。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;

const int N = 100010;
const LL MOD = 1e9 + 9;

int n;
int p[N], l[N];
bool vis[N];
LL fac[N], f[N];

int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0' || c>'9') f=(c=='-')?-1:1,c=getchar();
    while(c>='0' && c<='9') x=x*10+c-48,c=getchar();
    return x*f;
}

LL Pow(LL a, LL b){
    int sum=1;
    for(; b; b >>= 1){
        if(b & 1) sum = sum * a % MOD;
        a = a * a % MOD;
    }
    return sum;
}

void init(){
    fac[0] = 1;
    for(int i=1; i<=100000; i++) fac[i] = fac[i-1] * i % MOD;
    f[1] = 1;//细节
    for(int i=2; i<=100000; i++) f[i] = Pow(i, i-2);
}

int dfs(int x){
    vis[x] = true;
    if(vis[p[x]]) return 1;
    return dfs(p[x]) + 1;
}

void work(){
    n = read();
    for(int i=1; i<=n; i++) p[i] = read();
    int cnt=0;
    memset(vis, false, sizeof(vis));
    for(int i=1; i<=n; i++)
        if(!vis[i]) l[++cnt] = dfs(i);
    LL ans = 1, inv = 1;
    for(int i=1; i<=cnt; i++){
        ans = ans * f[l[i]] % MOD;
        inv = inv * Pow(fac[l[i] - 1], MOD - 2) % MOD;
    }
    ans = ans * fac[n - cnt] % MOD * inv % MOD;
    printf("%lld\n", ans);
}

int main(){
    init();
    int T;
    T = read();
    while(T--) work();
    return 0;
}

完结撒花