2010-06-08 23:24:36.ural1057 number theory and dp 數位類統計問題
不說了，詳見國家集訓隊2009論文集 14.劉聰 <<淺談數位類統計問題>>
需要非常注意邊界條件的處理.
??1?/*
??2??*?SOUR:ural?1057
??3??*?ALGO:number?theory?and?binary?tree,?in?other?word?enumerate?the?highest?digit,
??4??*??????and?use?dp?to?reduce?calculation.
??5??*?DATE:?2010年?06月?08日?星期二?16:44:45?CST
??6??*?COMM:
??7??*?*/
??8?
??9?using?namespace?std;
?10?#define?pb(x)?push_back(x)
?11?#define?X?first
?12?#define?Y?second
?13?typedef?vector?<?int?>vi;
?14?typedef?pair?<?int,?int?>pii;
?15?typedef?long?long?LL;
?16?template?<class?T>?void?ckmin(T?&a,T?b)?{?if?(a?>?b)?{?a?=?b;?}?}
?17?template?<class?T>?void?ckmax(T?&a,T?b)?{?if?(a?<?b)?{?a?=?b;?}?}
?18?int?countbit(int?n)?{?return?n?==?0???0?:?1?+?countbit(n?&?(n?-?1));?}
?19?
?20?const?int?maxint?=?0x7fffffff;
?21?const?long?long?max64?=?0x7fffffffffffffffll;
?22?int?X,?Y,?K,?B;
?23?int?cnt[40][40];
?24?
?25?void?pre?()
?26?{
?27???int?i,?j;
?28???cnt[0][0]?=?1;
?29???for?(i?=?1;i?<=?32;i++)?{
?30???????cnt[i][0]?=?cnt[i-1][0];
?31???????for?(j?=?1;j?<=?32;j++)?{
?32???????????cnt[i][j]?=?cnt[i-1][j]?+?cnt[i-1][j-1];
?33???????}
?34???}
?35?}
?36?
?37?void?changeBase(int?X,?int?num[],?int?&top)
?38?{
?39???top?=?1;
?40???while?(X?>?0)?{
?41???????num[top++]?=?X?%?B;
?42???????X?/=?B;
?43???}
?44?}
?45?
?46?void?plus_one(int?num[],?int?&top)
?47?{
?48???int?i,j;
?49???for?(i?=?1;i?<=?top;i++)?{
?50???????if?(num[i]?==?0)?{
?51???????????num[i]?=?1;
?52???????????for?(j?=?i?-?1;j?>=?1;j--)?{
?53???????????????num[j]?=?0;
?54???????????}
?55???????????break;
?56???????}
?57???}
?58???if?(i?==?top)?{
?59???????top++;
?60???}
?61?}
?62?
?63?bool?floor(int?num[],?int?top)
?64?{
?65???int?i,j;
?66???for?(i?=?top?-?1;i?>=?1;i--)?{
?67???????if?(num[i]?>?1)?{
?68???????????for?(j?=?i;j?>=?1;j--)?{
?69???????????????num[j]?=?1;
?70???????????}
?71???????????break;
?72???????}
?73???}
?74???if?(i?>=?1)?{
?75???????return?true;
?76???}
?77???return?false;
?78?}
?79?
?80?int?num[40],?top;
?81?int?proc(int?X,bool?flag?=?false)
?82?{
?83???memset(num,?0,?sizeof(num));
?84???changeBase(X,?num,?top);
?85???if?(floor(num,?top)?||?flag)?{
?86???????plus_one(num,?top);
?87???}
?88?
?89???int?ans?=?0,?sum?=?0,?i;
?90???for?(i?=?top?-?1;i?>=?1;i--)?{
?91???????if?(K?>=?sum?&&?num[i]?==?1)?{
?92???????????ans?+=?cnt[i-1][K?-?sum];
?93???????????sum++;
?94???????}
?95???}
?96???return?ans;
?97?}
?98?
?99?int?main()
100?{
101???pre();
102???int?num[40],?top,?ans;
103???cin?>>?X?>>?Y?>>?K?>>?B;
104???ans?=?proc(Y,?1)?-?proc(X);
105???cout?<<?ans?<<?endl;
106???return?0;
107?}