[SCOI2009]游戏

链接

[SCOI2009]游戏

题解

先把图建出来，容易发现这是一张由点和环构成的图，每个环转回去需要的步数就是环的长度，多个环同时转回去的最小长度为(lcm(len_1, len_2, len_3, ... , len_n))。
又环的长度和为(n)，问题可转化成把一个正整数(n)分解成若干数的和，求他们的(lcm)的可能方案数
把(lcm)分解质因数，考虑一堆数的(lcm)是他们出现过的质因数的最高次幂的乘积，为了不产生损耗，构造的时候直接用质数的幂来凑，这样(gcd(..) = 1)，不会产生损耗
注意他们的和可以小于(n)，因为剩下的可以用(1)补齐
于是问题转化为一个背包问题，设(dp[i][j])表示用了(i)个质数，总和为(j)的总方案数，(dp[i][j] = sum f[i - 1][j - p_i^k])

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = (int)1e3 + 10;
int n;
int prime[N], tot, f[N], ans[N];
bool vis[N];
void Prime (int n) {
	for (register int i = 2; i <= n; ++i) {
		if (!vis[i]) prime[++tot] = i;
		for (register int j = 1; j <= tot; ++j) {
			if (prime[j] * i > n) break;
			vis[i * prime[j]] = 1;
			if (i % prime[j] == 0) break;
		}
	}
}
signed main() {
	cin >> n;
	if (n == 1) return cout << 1, 0;
	Prime(n);
	ans[0] = 1;
	for (register int i = 1; i <= tot; ++i) 
		for (register int j = n; j >= prime[i]; --j) {
			int tmp = prime[i];
			while (tmp <= j) {
				ans[j] += ans[j - tmp];
				tmp *= prime[i];
			}
		}
	ans[0] = 0;
	for (register int i = 1; i <= n; ++i) ans[0] += ans[i];
	printf("%lld", ans[0] + 1);
	return 0;
}