【题目链接】:http://www.lydsy.com/JudgeOnline/problem.php?id=1025

【题意】

【题解】



每一个对应关系,里面其实都会生成大小不一的几个环.

每一个环的大小.对应了里面的数字经过多少轮的变换之后能恢复原状.

则最后总的变回原状相当于求各个环的大小的最小公倍数.

这个最小公倍数就是所需要的排数.

原题意就等价于

给你一个数字n;

让你挑选若干个数字

它们的和为n;

求这些数字不同的最小公倍数的个数.

正面考虑不好考虑;

考虑反面;

就是已经知道了一个最小公倍数X

这里

X=a1^b1*a2^b2…ak^bk

->质数唯一分解定理;

这样我们可以先构造一个数列

{a1^b1,a2^b2…,ak^bk}

这k个数字是和最小的,且满足他们的最小公倍数是X的数列;

则设T=a1^b1+a2^b2+…+ak^bk

如果T=n

则显然符合题意.k个数字,每个数字对应ai^bi就好;

而如果 T< n

则也符合题意;

因为你可以在ak^bk后面再加上n-T个1;

这样对它们的最小公倍数不会有影响;且总数也符合为n;

而如果T>n;

则无解了;

因为T已经是最小的了;

如果还不行就没办法了;

所以只要T<=n,则这个数字就是可达到的.

根据以上分析;

我们求出1..n里面的所有质数a[i];

然后每个质数枚举它的指数;

然后用动态规划的方法求出最终解;

设f[i][j]表示前i个质数,和为j的方案数;

f[i][j] = f[i-1][j]+∑(f[i-][j-a[i]^k]) 这里j-a[i]^k>=0

最后累加

f[tot][0..n]即可;

tot是1..n里面质数的个数.

答案会很大。开long long



【完整代码】

#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%lld",&x)
#define ref(x) scanf("%lf",&x) typedef pair<int, int> pii;
typedef pair<LL, LL> pll; const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };
const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };
const double pi = acos(-1.0);
const int N = 1e3 + 100; int n,tot;
int a[N];
LL f[N][N],ans = 0; bool is(int x)
{
int len = sqrt(x);
rep1(i, 2, len)
if (x%i == 0)
return false;
return true;
} void input_data()
{
rei(n);
} void get_ans()
{
rep1(i, 2, n)
if (is(i))
a[++tot] = i; f[0][0] = 1;
rep1(i, 1, tot)
{
rep1(j, 0, n)
{
f[i][j] = f[i - 1][j];
int k = a[i];
while (j - k >= 0)
{
f[i][j] += f[i - 1][j - k];
k = k*a[i];
}
}
} rep1(i, 0, n)
ans += f[tot][i];
} void output_ans()
{
printf("%lld\n", ans);
} int main()
{
//freopen("F:\\rush.txt", "r", stdin);
input_data();
get_ans();
output_ans();
//printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
05-27 18:01