[SCOI2009]游戏
[SCOI2009]游戏
https://ac.nowcoder.com/acm/problem/20271
根据题意每个数经过k次变换终会回到自身；
置换的思想；
离散数学里的知识；
n个数可以分成m个集合，这m个集合元素的总数==n;
相当于在n个数中分别选取a,b,c...个数组成m个集合；
比如：假设8个数组成3个集合
可以为224 （即第一个集合元素2，第二个2，第三个4）
为了节省时间：
每个集合大小ai可以表达为若干个质因数的h次幂形式；
即从质数中选取k个按照一定的幂次，使其和等于h
dp[i][j]表示前i个质数，和为j的种类数
dp[i][j]+=dp[i-1][j-is_prime[i]^k];
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1010;
int dp[maxn],cnt=0,is_prime[maxn],prime[maxn];
void find(int n)
{
prime[1]=1,prime[0]=1;
for(int i=2;i<=n;i++)
{
if(prime[i]==1) continue;
is_prime[cnt++]=i;//记录n以内的质因数
for(int j=i+i;j<=n;j+=i)
{
prime[j]=1;
}
}
return;
}
signed main()
{
int n;
scanf("%d",&n);
memset(prime,0,sizeof(prime));
memset(is_prime,0,sizeof(is_prime));
find(n);
dp[0]=1;//完全背包
for(int i=0;i<cnt;i++)
{
for(int j=n;j>=is_prime[i];j--)
{
int l=is_prime[i];
while(l<=j) dp[j]+=dp[j-l],l*=is_prime[i];
}
}
int ans=0;
for(int i=0;i<=n;i++)
{
ans+=dp[i];
}
cout<<ans<<endl;
}每日打卡 文章被收录于专栏
牛客里的每日一题~~也可能有我自己每天的练习~~
