首页 > 其他 > 详细

Gym 100418J Lucky tickets(数位dp)

时间:2017-06-29 19:05:58      阅读:285      评论:0      收藏:0      [点我收藏+]

题意:给定一个n。求区间[1, n]之间的全部的a的个数。a满足:

a能整除  把a表示自身二进制以后1的个数

思路:题意非常绕....

数位dp,对于全部可能的1的个数我们都dfs一次

对于某一个可能的1的个数p来说。状态dp(len, i, j, k)里的每一位分别表示当前位,当前确定位的值模除p,已经有了多少个1。是否已经小于给定的n。

注意的是这题范围非常大,要用unsigned long long 来定义n

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<ctime>
#define eps 1e-6
#define ULL unsigned long long
#define LL  long long
#define pii (pair<int, int>)
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
int digit[100];
ULL cnt_one;
ULL n;
LL d[100][100][100];
LL dfs(int len, ULL r, int k, int s) {
	if(!len) return (r==0&&k==cnt_one) ? 1:0;
	if(!s && d[len][r][k]!=-1) return d[len][r][k]; 
	LL ans = 0;
	ans += dfs(len-1, r, k, s&&!digit[len]);
	if(!(s&&!digit[len]) && k<cnt_one) ans += dfs(len-1, (r+(1ULL<<(len-1)))%cnt_one, k+1, s&&digit[len]);
	if(!s) d[len][r][k] = ans;
	return ans;
} 
ULL solve(ULL n) {
	int cnt = 0, su = 0;
	while(n) {
		digit[++cnt] = n & 1;
		su++; n >>= 1;
	}
	LL ans = 0;
	for(cnt_one = 1; cnt_one <= su; cnt_one++) {
		memset(d, -1, sizeof(d));
		ans += dfs(cnt, 0, 0, 1);
	}
	return ans;
}
int main() {
	while(cin >> n) {
		cout << solve(n) << endl;
	}
    return 0;
}

Gym 100418J Lucky tickets(数位dp)

原文:http://www.cnblogs.com/yutingliuyl/p/7095633.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!