专栏首页饶文津的专栏【HDU - 4345 】Permutation(DP)

【HDU - 4345 】Permutation(DP)

BUPT2017 wintertraining(15) #8F

题意

1到n的排列,经过几次置换(也是一个排列)回到原来的排列,就是循环了。 现在给n(<=1000),求循环周期的所有可能数。

题解

问题等价于几个正整数加起来等于n,求最小公倍数的可能数。 因为1不影响最小公倍数,所以等价于求几个正整数加起来小于等于n,最小公倍数的可能数。

最小公倍数与每个质因子在正整数里最大出现次数有关,所以枚举质因子的幂,进行dp。

dp[i][j]表示前i个质数,和为j时,最小公倍数的可能数。

dp[0][0]=1 转移就是

(dp[i][j]=sum_{k=1}^{p[i]^kle j}{dp[i-1][j-p[i]^k]})

最后把dp[cnt][j]累加起来,答案就是dp[cnt][n]了。 可以写成一维的。

代码

#include <cstdio>
#define N 1001
typedef long long ll;
ll dp[N];
bool com[N];
int cnt;
int prime[N];
int main(){
	for(int i=2;i<N;++i)
	if(!com[i]){
		prime[++cnt]=i;
		for(int j=i+i;j<N;j+=i)
			com[j]=true;
	}
	dp[0]=1;
	for(int i=1;i<=cnt;++i)
		for(int j=N-1;j>=prime[i];--j)
			for(int k=prime[i];k<=j&&k<N;k*=prime[i])
				dp[j]+=dp[j-k];
	for(int i=1;i<N;++i)
		dp[i]+=dp[i-1];
	int n;
	while(~scanf("%d",&n))
		printf("%lld\n", dp[n]);
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【POJ 2923】Relocation(状压DP+DP)

    题意是给你n个物品,每次两辆车运,容量分别是c1,c2,求最少运送次数。 好像不是很好想,我看了网上的题解才做出来。 先用状压DP计算i状态下,第一辆可以运送的...

    饶文津
  • 【ZOJ 3502】Contest

      n个问题,解决的顺序影响正确的概率,无论之前解决的问题是否答对,当前问题 j 答对概率为max{a[i][j]} (i为解决过的问题)。求答对题目的最大期望...

    饶文津
  • 【HDU 5115】Dire Wolf

    n只狼排成一行,每次击败第i只狼需要ai+bi-1+bi+1代价,击败后,相当于出列了,与i相邻两只狼成了相邻的。求击败所有狼的最小总代价。

    饶文津
  • 动态规划:不同路径

    题目链接:https://leetcode-cn.com/problems/unique-paths/

    代码随想录
  • POJ-2096-Collecting Bugs

    ACM模版 描述 ? image.png image.png 代码 #include <iostream> #include <cstdio> using n...

    f_zyj
  • 算法训练 K好数

    问题描述 如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字,那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4,L = ...

    AI那点小事
  • Uva_10253 Series-Parallel Networks

        2:G1,G2为串并联网络, 将它们的源点与汇点分别连接起来, 得到的也是串并联网络(并联)

    若羽
  • P1034 矩形覆盖

    题目描述 在平面上有 n 个点(n <= 50),每个点用一对整数坐标表示。例如:当 n=4 时,4个点的坐标分另为:p1(1,1),p2(2,2),p3(3,...

    attack
  • LeetCode 122. Best Time to Buy and Sell Stock II

    题目:https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/description/

    ShenduCC
  • poj 3254 Corn Fields (状态压缩dp)

    题意:Farmer John 放牧cow,有些草地上的草是不能吃的,用0表示,然后规定两头牛不能相邻放牧。问你有多少种放牧方法。

    xindoo

扫码关注云+社区

领取腾讯云代金券