2025.3.15

· · 个人记录

洛谷P4778

AcWing212

题目背景

Just like yesterday (in problem U of the practice session), Bob is busy, so Alice keeps on playing some single-player games and puzzles. In her newest puzzle she has a permutation of numbers from 1 to n. The goal of the puzzle is to sort the permutation using the smallest possible number of swaps.

Instead of simply solving the puzzle, Alice is wondering about the probability of winning it just by playing at random. In order to answer this question, she needs to know the number of optimal solutions to her puzzle.

题目描述

You are given a permutation p1, …, pn of the numbers 1 through n. In each step you can choose two numbers x < y and swap px with py.

Let m be the minimum number of such swaps needed to sort the given permutation. Compute the number of different sequences of exactly m swaps that sort the given permutation. Since this number may be large, compute it modulo 10^9 + 9.

输入格式

The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.

Each test case consists of two lines. The first line contains the integer n. The second line contains the sequence p1, …, pn: a permutation of 1, …, n.

In the easy subproblem C1, 1 ≤ n ≤ 10.

In the hard subproblem C2, 1 ≤ n ≤ 105.

输出格式

For each test case, output a single line with a single integer: x%(10^9+9), where x is the number of ways to sort the given sequence using as few swaps as possible.

输入输出样例 #1

输入 #1

3

3
2 3 1

4
2 1 4 3

2
1 2

输出 #1

3
2
1

说明/提示

In the first test case, we can sort the permutation in two swaps. We can make the first swap arbitrarily; for each of them, there’s exactly one optimal second swap. For example, one of the three shortest solutions is “swap p1 with p2 and then swap p1 with p3”.

In the second test case, the optimal solution involves swapping p1 with p2 and swapping p3 with p4. We can do these two swaps in either order.

The third sequence is already sorted. The optimal number of swaps is 0, and thus the only optimal solution is an empty sequence of swaps.
题目来源：IPSC2016

Ac代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int Mod = 1e9+9;
int jc[100005],ways[100005]; //jc 是阶乘，ways 是保证最小操作次数的情况下，变成目标的方法数 
int n,p[100005],cnt,len[100005]; //n 是序列长度，p 是原序列，cnt 是原本的自环个数，len 是原本自环的长度 
bool b[100005]; //标记有没有自环经过当前的数 
int power(int x,int y){ //龟速幂 
    int res = 1;
    while(y){
        if(y & 1) res = res * x % Mod;
        x = x * x % Mod;
        y >>= 1;
    }
    return res;
}
int dfs(int i){ // 搜出原序列各个自环的长度 
    b[i] = true;
    int nex = p[i];
    if(b[nex] == false) return dfs(nex) + 1;
    else return 114514 + 114514 - (2*114514) + 1;
}
void init(){ // <')))><<处理出1 to 1e5 的阶乘与乘法逆元 
    jc[0] = 1;
    for(int i = 1;i <= 100005;i++) jc[i] = jc[i-1] * i % Mod;
    ways[1] = 1;
    for(int i = 2;i <= 100005;i++) ways[i] = power(i,i-2); 
    /*我们可以发现 ways 的前几位长这样 ->
        "1 1 3 16 125 1296 16807 262144"
    可以发现 ways[i] = i^(i-2) (oeis神力)，可以优化一层循环 */
}
signed main(){
    ios::sync_with_stdio(0);
    init();
    int t;
    cin>>t;
    while(t--){
        cin>>n;
        for(int i = 1;i <= n;i++) cin>>p[i]; //读入 
        cnt = 0;//清空 len[] 
        memset(b,0,sizeof(b));//清空标记 
        for(int i = 1;i <= n;i++){
            if(b[i] == false)//找自环 
                len[++cnt] = dfs(i);//算自环长度 
        }
        /*我们可以找出k个大小为a1,a2...ak的环,把所有环的答案合并,
        同样每个环之间的操作是不会相互影响的,
        所以方案数要乘上一个可重集的排列数,可以得到
        ans
        =（以下为 LaTex） 
        {\textstyle \prod_{i=1}^{k}}f_{a_{i}}\times\frac{(n-k)!}{{\textstyle \prod_{i=1}^{k}(a_{i}-1)!}}*/
        int ans = jc[n-cnt] % Mod;
        for(int i=1;i<=cnt;++i) {
            int inv = power(jc[len[i]-1], Mod-2);//求逆元 
            ans = ans*ways[len[i]]% Mod*inv% Mod;
        }

        cout<<ans<<endl;//输出 
    }
    return 0;
}