Intervals
题目连接：
http://codeforces.com/gym/100231/attachments
Description
Start with an integer, N0, which is greater than 0. Let N1 be the number of ones in the binary representation of N0. So, if N0 = 27, N1 = 4. For all i > 0, let Ni be the number of ones in the binary
representation of Ni−1. This sequence will always converge to one. For any starting number, N0, let K be the minimum value of i ≥ 0 for which Ni = 1. For example, if N0 = 31, then N1 = 5, N2 = 2, N3 = 1, so K = 3. Given a range of consecutive numbers, and a value X, how many numbers in the range have a K value equal to X?
Input
There will be several test cases in the input. Each test case will consist of three integers on a single line:
l, r, X, where l and r (1 ≤ l ≤ r ≤ 1018) are the lower and upper limits of a range of integers, and X
(0 ≤ X ≤ 10) is the target value for K. The input will end with a line with three 0s.
Output
For each test case, output a single integer, representing the number of integers in the range from l to
r (inclusive) which have a K value equal to X in the input. Print each integer on its own line with no
spaces. Do not print any blank lines between answers.
Sample Input
31 31 3
31 31 1
27 31 1
27 31 2
1023 1025 1
1023 1025 2
0 0 0
Sample Output
1
0
0
3
1
1
Hint
题意
首先给你Ni的定义，表示第几轮的时候，这个数是多少，Ni = Ni-1二进制表示下的1的个数
k 表示第几步的时候，Ni = 1
给你l,r,x
问你在l,r区间内，k等于x的数有多少个
题解：
我们首先预处理vis[i]表示有i个1的时候的步数，这个用dp很容易解决
然后我们就可以数位dp去做了，做[1,x]里面二进制数为k个的数量
注意特判1的情况，比较麻烦
代码
#include<bits/stdc++.h>
using namespace std;
long long l,r,t;
int vis[100];
long long ans = 0;
int getone(long long x)
{
int c=0;
while(x>0)
{
if((x&1)==1)
c++;
x>>=1;
}
return c;
}
long long f[70][70];
void init()
{
memset(f,0,sizeof(f));
f[0][0] = 1LL;
for(int i=1;i<=62;i++)
{
f[i][0] = 1LL;
for(int j=1;j<=i;j++)
{
f[i][j] = f[i-1][j-1] + f[i-1][j];
}
}
}
long long calc(long long x,int k)
{
int tot = 0;
long long ans = 0;
for(long long i=62;i>0;i--)
{
if(x&(1LL<<i))
{
tot++;
if(tot>k) break;
x ^= (1LL<<i);
}
if((1LL<<(i-1LL))<=x)
{
if(k>=tot)
ans += f[i-1][k-tot];
}
}
if(tot + x == k) ans++;
return ans;
}
long long solve(long long limit,int x)
{
ans=0;
for(int i=1;i<=61;i++)
if(vis[i]==x)
{
if(i==1)
ans--;
ans+=calc(limit,i);
}
return ans;
}
int main()
{
init();
vis[1]=1;
for(int i=2;i<=61;i++)
vis[i]=vis[getone(i)]+1;
while(scanf("%lld%lld%d",&l,&r,&t)!=EOF)
{
if(l==0&&r==0&&t==0)return 0;
if(t==0)
{
if(l==1)
printf("1\n");
else
printf("0\n");
continue;
}
if(t==1)
{
if(l==1)
printf("%lld\n",solve(r,t)-solve(l-1,t)-1);
else
printf("%lld\n",solve(r,t)-solve(l-1,t));
}
else
printf("%lld\n",solve(r,t)-solve(l-1,t));
}
}
