詳見國家集訓隊2009論文集 14.劉聰 <<淺談數(shù)位類統(tǒng)計問題>>
這到題需要非常注意復數(shù)的操作，其實完全可以講負數(shù)轉(zhuǎn)化為整數(shù)操作
也就是int轉(zhuǎn)換成unsigned int
還有就是要注意，int型正數(shù)，右移補0，負數(shù)右移是補1的，
??1?
??2?/*
??3??*?SOUR:spoj1182
??4??*?ALGO:dp,?number?theory,?binary?search
??5??*?DATE:?2010年?06月?08日?星期二?19:47:51?CST
??6??*?COMM:5
??7??*?*/
??8?#include<iostream>
??9?#include<cstdio>
?10?#include<cstdlib>
?11?#include<cstring>
?12?#include<algorithm>
?13?#include<queue>
?14?#include<vector>
?15?#include<map>
?16?using?namespace?std;
?17?#define?pb(x)?push_back(x)
?18?//#define?X?first
?19?//#define?Y?second
?20?typedef?vector?<?int?>vi;
?21?typedef?pair?<?int,?int?>pii;
?22?typedef?long?long?LL;
?23?typedef?unsigned?long?long?ULL;
?24?typedef?unsigned?int?uint;
?25?
?26?template?<class?T>?void?ckmin(T?&a,T?b)?{?if?(a?>?b)?{?a?=?b;?}?}
?27?template?<class?T>?void?ckmax(T?&a,T?b)?{?if?(a?<?b)?{?a?=?b;?}?}
?28?int?countbit(int?n)?{?return?n?==?0???0?:?1?+?countbit(n?&?(n?-?1));?}
?29?
?30?const?int?maxint?=?0x7fffffff;
?31?const?long?long?max64?=?0x7fffffffffffffffll;
?32?int?cnt[40][40],?sum[40];
?33?int?X,?Y,?K;
?34?
?35?void?pre()
?36??????//算出cnt[長度][含多少個1]的方案數(shù)
?37?{
?38???int?i,j;
?39???cnt[0][0]?=?1;
?40???for?(i?=?1;i?<=?32;i++)?{
?41???????cnt[i][0]?=?cnt[i-1][0];
?42???????for?(j?=?1;j?<=?32;j++)?{
?43???????????cnt[i][j]?=?cnt[i-1][j]?+?cnt[i-1][j-1];
?44???????}
?45???}
?46?}
?47?
?48?int?num[40],?top;
?49?int?summ(uint?X,?int?R,?bool?flag?=?false)
?50?{
?51???memset(num,?0,?sizeof(num));
?52???top?=?1;
?53???while?(X)?{
?54???????num[top++]?=?X?&?1;
?55???????X?>>=?1;
?56???}
?57???if?(flag)?{
?58???????for?(int?i?=?1;i?<=?top;i++)?{
?59???????????if?(num[i]?==?0)?{
?60???????????????num[i]?=?1;
?61???????????????for?(int?j?=?i?-?1;j?>=?1;j--)?{
?62???????????????????num[j]?=?0;
?63???????????????}
?64???????????????if?(i?==?top)?{?top++;?}
?65???????????????break;
?66???????????}
?67???????}
?68???}
?69???int?ans?=?0,?one?=?0,?i;
?70???for?(i?=?top?-?1;i?>=?1;i--)?{
?71???????if?(R?>=?one?&&?num[i]?==?1)?{
?72???????????ans?+=?cnt[i?-?1][R?-?one];
?73???????????one++;
?74???????}
?75???}
?76???return?ans;
?77?}
?78?
?79?int?summarize(uint?X,?uint?Y,?int?digit)
?80??????//[X,?Y]?中1的個數(shù)為digit的?數(shù)字個數(shù)
?81?{?return?summ(Y,?digit,?1)?-?summ(X,?digit,?0);?}
?82?
?83?void?proc()
?84?{
?85???int?i,?j,?one?=?-1;
?86???memset(sum,?0,?sizeof(sum));
?87???for?(i?=?0;i?<?32;i++)?{
?88???????sum[i]?=?summarize(X,?Y,?i)?;
?89???????if?(K??>?sum[i])?{
?90???????????K?-=?sum[i];
?91???????}else?{
?92???????????one?=?i;
?93???????????break;
?94???????}
?95???}
?96???if?(Y?<?X)?{?swap(X,?Y);?}
?97???int?left?=?X,?right?=?Y;
?98???while?(left?<?right)?{?//binary?search?the?value?expected
?99???????int?mid?=?(left?+?right?+?1)?/?2;
100???????if?(summarize(X,?mid,?one)?<=?K)?{
101???????????left?=?mid;
102???????}else?{
103???????????right?=?mid?-?1;
104???????}
105???}
106???while?(countbit(left)?!=?one)?{?left?--;?}?//?attention
107?
108???int?ans?=?0;
109???for?(i?=?0;i?<?32;i++)?{
110???????if?(left?&?(1?<<?i))?{
111???????????ans?|=?1?<<?i;
112???????}
113???}
114???printf("%d\n",?ans);
115?}
116?
117?int?main()
118?{
119???int?i,?j,?testcase;
120???pre();
121???scanf("%d",?&testcase);
122???while?(testcase--?)?{
123???????scanf("%d?%d?%d",?&X,?&Y,?&K);
124???????proc();
125???}
126???return?0;
127?}
128?