题解写得很好：https://www.luogu.com.cn/blog/pythoner713/solution-p4727
但是Part 5不是很清晰。这里用自己的语言重述Part 5。
Part 4的结论是，对于一个置换
可见，每个置换对答案的贡献仅仅取决于其循环的长度的多重集
对于这样一个循环长度的多重集：
将枚举的循环长度的多重集记为
由于置换个数
枚举循环长度的多重集实际上是枚举
rust代码：
use std::io;
const P: u32 = 997;
// Faster?
fn mpow(mut base: u32, mut ex: u32, p: u32) -> u32 {
let mut ans = 1u32;
while ex != 0 {
if ex & 1u32 != 0 {
ans = (ans as u64 * base as u64 % p as u64) as u32;
}
base = (base as u64 * base as u64 % p as u64) as u32;
ex >>= 1;
}
return ans;
}
fn get_invs(invs: &mut [u32], p: u32, n: u32) {
invs[1] = 1;
for i in 2..(n + 1) {
invs[i as usize] = (((p - p / i) as u64) * (invs[(p % i) as usize] as u64) % p as u64) as u32;
}
}
fn gcd(mut a: u32, mut b: u32) -> u32 {
while b != 0 {
let r = a % b;
a = b;
b = r;
}
return a;
}
fn work(b: &Vec<u32>, invs: &[u32; P as usize]) -> u32 {
let mut k = 0;
for bi in b {
k += bi / 2;
}
for i in 0..b.len() {
for j in 0..i {
k += gcd(b[i], b[j]);
}
}
let mut ans = mpow(2, k, P);
for bi in b {
ans = ans * invs[*bi as usize] % P;
}
let mut last = 0;
let mut ci_fact = 1;
let mut ci = 0;
for bi in b {
let bi = *bi;
if bi == last {
ci += 1;
ci_fact = ci_fact * ci % P;
} else {
ans = ans * invs[ci_fact as usize] % P;
last = bi;
ci = 1;
ci_fact = 1;
}
}
ans = ans * invs[ci_fact as usize] % P;
return ans;
}
fn dfs(n: u32, mn: u32, b: &mut Vec<u32>, inv: &[u32; P as usize]) -> u32 {
if n == 0 {
return work(b, inv);
} else if n < mn {
return 0;
}
let mut ans = 0;
for bi in mn..(n+1) {
b.push(bi);
ans = (ans + dfs(n - bi, bi, b, inv)) % P;
b.pop();
}
ans
}
fn main() {
let mut input = String::new();
io::stdin().read_line(&mut input).unwrap();
let n = input.trim().parse().unwrap();
let mut b = Vec::new();
let mut invs = [0; P as usize];
get_invs(&mut invs, P, P - 1);
println!("{}", dfs(n, 1, &mut b, &invs));
}