JZOJ 1038. 【SCOI2009】游戏

题目

自己找

思路

大致过程见 JZOJ 3232. 【佛山市选2013】排列
而本题改成种类数
那么我们不需要 (ln) 这个东东
直接转移
(f) 改成种类数
对于可能转移过来的状态，直接加上他们的 (f) 值就行了

(Code)

#include<cstdio>
#include<cmath>
using namespace std;
typedef long long LL;

const int N = 1e3 + 5;
int n , vis[N] , tot , pr[N];
LL f[N][N] , ans;

inline void getprime(int Mx)
{
	vis[1] = 1;
	for(register int i = 2; i <= Mx; i++)
	{
		if (!vis[i]) pr[++tot] = i;
		for(register int j = 1; j <= tot && pr[j] * i <= Mx; j++)
		{
			vis[pr[j] * i] = 1;
			if (i % pr[j] == 0) break;
		}
	}
}

int main()
{
	getprime(1e3);
	scanf("%d" , &n);
	f[0][0] = 1;
	for(register int i = 1; i <= tot; i++)
		for(register int j = 0; j <= n; j++)
		{
			f[i][j] = f[i - 1][j];
			int w = pr[i];
			while (j - w >= 0)
			{
				f[i][j] += f[i - 1][j - w];
				w *= pr[i];
			}
		}
	for(register int i = 0; i <= n; i++) ans += f[tot][i];
	printf("%lld" , ans);
}