首页 > 代码库 > Gym 100418J Lucky tickets(数位dp)
Gym 100418J Lucky tickets(数位dp)
题意:给定一个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)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。