题意：给定一个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;
}