[SCOI2009][bzoj1025]游戏

标签： DP 置换

---

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

题解

很套路的题目了。

一个置换的复原最少需要次数为所有循环的最小公倍数。

那么就是问能够组成多少种不同的最小公倍数。

这就dp了。

设dp[i][j]代表到了第i个质数，用j组成的方案数。

显然有\(dp[i][j]=\sum dp[i][j-prime[i]^k])\)

代码

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cmath>

#include<queue>

#include<stack>

#include<set>

#include<map>

using namespace std;

#define ll long long

#define REP(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)

#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)

#define EREP(i,a) for(int i=start[(a)];i;i=e[i].next)

inline int read()

{

	int sum=0,p=1;char ch=getchar();

	while(!(('0'<=ch && ch<='9') || ch=='-'))ch=getchar();

	if(ch=='-')p=-1,ch=getchar();

	while('0'<=ch && ch<='9')sum=sum*10+ch-48,ch=getchar();

	return sum*p;

}

const int maxn=1e3+20;

int n,tot,prime[maxn],mark[maxn];

ll dp[maxn][maxn];

void init()

{

	n=read();

	REP(i,2,n)

	{

		if(!mark[i])prime[++tot]=i;

		for(int j=1;j<=tot && prime[j]*i<=n;j++)

		{

			int k=i*prime[j];

			mark[k]=1;

			if(!(i%prime[j]))break;

		}

	}

}

void doing()

{

	REP(i,0,n)dp[0][i]=1;

	REP(i,1,tot)

	{

		REP(j,0,n)

		{

			int x=prime[i];dp[i][j]=dp[i-1][j];

			while(x<=j)dp[i][j]+=dp[i-1][j-x],x*=prime[i];

		}

	}

	printf("%lld\n",dp[tot][n]);

}

int main()

{

	freopen("game.in","r",stdin);

	freopen("game.out","w",stdout);

	init();

	doing();

	return 0;

}