POJ 3252 Round Numbers
http://poj.org/problem?id=3252
パスカルの三角形をあらかじめ計算しておく。
まず、((数字の桁数) - 1)桁以下の2進数についてRound Numberを求める。
これは、iを桁数、jを0の個数として
iCj - (i-1)C(j-1)
の和を計算すればよい。
次に(数字の桁数)桁の2進数についてRound Numberを求める。
桁を上から見ていって1が現れたら、そこを0であるRound Numberの個数を組み合わせで求めていけばよい。
#include <cstdio> #include <algorithm> using namespace std; typedef long long ll; int t[34][34]; int digi(ll a){ for(int d = 33; d >= 0; d--) if((a&(((ll)1)<<d)) > 0) return d+1; } int solve(ll a){ if(a == 0) return 0; int digit, dig, ans = 0, one = 1, zero = 0; digit = digi(a); for(int i=2;i<digit;i++)for(int j=i-1;j*2>=i;j--){ ans += t[i][j] - t[i-1][j-1]; } for(int d = digit-2; d >= 0; d--){ dig = d+1; if((a&(1<<d)) > 0){ for(int j=dig-1;(j+zero+1)*2>=digit;j--){ ans += t[dig-1][j]; } one++; }else{ zero++; } } if(zero >= one) ans++; return ans; } int main(){ ll a,b; for(int i=0;i<34;i++) t[i][0] = 1; t[1][1] = 1; for(int i=2;i<34;i++)for(int j=0;j<=i;j++) t[i][j] = t[i-1][j]+t[i-1][j-1]; scanf("%lld %lld", &a, &b); printf("%d\n", solve(b)-solve(a-1)); }