Luogu6280 [USACO20OPEN]Exercise G

tony102

2021 年 05 月 28 日

2011 次浏览

暂无评论

1239字数

题解

[Link](https://www.luogu.com.cn/problem/P6280)

## Sol

感觉题面写的不是很清楚,原以为是翻译的问题,结果发现是英文原题面就写的很垃圾.给 Benjamin Qi 倒一杯卡布奇诺

个人理解困难的地方在于样例解释 $0$ 步的位置, 但是反过来一想如果按照我的想法(初始排列和 $A$ 一模一样) 的话那么答案就都是 $0$ 了.

首先可以猜一波东西, 要确定两个排列,一个是原排列(也就是初始位置的排列) 和 $A$ 排列(位置每次从 $i$ 变到 $A_i$) 是比较麻烦的. 先猜想应该答案跟原排列没有什么关系, 测试一下发现是对的.也就是说, 影响答案的只有这个 $A$ 排列.

再来观察 $A$ 排列每次是怎么影响每一个数的位置的.比如说现在有原排列 `1 2 3 4 5 ` 和 $A$ 排列 `2 3 4 5 1`. 你可以发现每一个位置的改变就像一个环.每一个数位置都会在这个环中持续地改变.那么要使这个排列变回原来的排列,应当是变化中所有环有一次正好同时变完一个周期时就回到了原排列.

形式话地,我们记变化过程中所有环的长度为 $c_i$ ,那么首先 $\sum c_i = n$  . 再者,有 $lcm_{c_i} = k$

解释一下为什么是 $lcm_{c_i}$ . 最简单形式的 $k$ 肯定可以被表示为 $k = \prod c_i$ , 假如 $\exist\ gcd(c_i, c_j) > 1$ , 那么 $k \div gcd(c_i,c_j)$  肯定可以变得更小, 也就是有更小的 $c_i$ 满足. 所以就是 $lcm_{c_i}$

根据算数基本定理, $lcm$ 就是取唯一分解后相同质数的最高次幂的乘积.现在就是要对 $n$ 进行分解,计算有多少中这样的分解.(这就是[P4161](https://www.luogu.com.cn/problem/P4161)) 并且同时计算一下和.

那么设 $f_{i,j}$ 表示前 $i$ 个质数和为 $j$ 的答案就可以了吧.转移的时候把当先选中的质数给它乘上去就可以了.肉眼可见 $f_i$ 的状态只会由 $f_{i-1}$ 转移过来.直接滚掉一维就可以了吧

## Code

```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int SIZE = 5e4 + 5;

int n, mod;
int f[SIZE], isPrime[SIZE], p[SIZE];

namespace GTR {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (c < 48 || c > 57) b ^= c == '-', c = fetch();
		while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
		return b ? a : -a;
	}
} using GTR::read;

signed main() {	
	// freopen("code.in", "r", stdin);
	int tot = 0;
	n = read(), mod = read(), isPrime[1] = 1;
	for (int i = 2; i <= n; ++ i) {
		if (!isPrime[i]) p[++ tot] = i;
		for (int j = 1; i * p[j] <= n; ++ j) {
			isPrime[i * p[j]] = 1;
			if (i % p[j] == 0) break;
		}
	}
	f[0] = 1;
	for (int i = 1; i <= tot; ++ i) {
		for (int j = n; j >= p[i]; -- j) {
			for (int k = p[i]; k <= j; k *= p[i]) f[j] = (f[j] + f[j - k] * k % mod) % mod;
		}
	}
	int ans = 0;
	for (int i = 0; i <= n; ++ i) ans = (ans + f[i]) % mod;
	printf("%lld\n", ans % mod);
	return 0;
}
```

最后修改：2021 年 08 月 20 日