今天FangGG講了數位類統計的。感覺記住那個圖就行了。O((logn)^2)的初始化，O(logn)的查詢  



感覺是利用了相同規模的樹完全相同，避免重復計算，用f[i][j]記錄下來。
f[i][j]表示一棵高度為i的完全二叉樹內二進制表示中恰好含有j個1的數的個數。不包括根的。感覺那個根是虛設的
葉子的i為0....所以那個i就是二進制下的第i位（從0開始） 
論文只計算到i=31，我覺得這樣子只對于正數，第31位他認為為0了 。而負數的為1，所以我對于負數的算到i=32



ural 1057 ★★★ 不同的冪  數位統計 B進制同樣可以用二進制解決！

/*
    論文《淺談數位類統計問題》
    題意： 求給定區間[X,Y]中滿足下列條件的整數個數：這個數恰好等于K 個互不相等的B的整數次冪之和。
    例如，設X=15，Y=20，K=2，B=2，則有且僅有下列三個數滿足題意：
            17 = 24+20，
            18 = 24+21，
            20 = 24+22。
    一個數x = aiB^i + ai-1B^(i-1)++a1B+a0。如果ai>1，則表示出來的x肯定包含兩個以上的B^i
    互不相等的冪之和，亦即其B進制表示的各位數字都只能是0和1！    
    我們只需討論二進制的情況，其他進制都可以轉化為二進制求解。
    用論文給出的方法初始化O((logn)^2) 查詢O(logn)

    ★★★
    對于詢問n，我們需要求出不超過n的最大B進制表示只含0、1的數：
    找到n 的左起第一位非0、1 的數位，將它變為1，并將右面所有數位設為1。（因為大于1的肯定不可取，后面置為1使它最接近原來的數）
    將得到的B進制表示視為二進制進行詢問即可。    
*/
#include<cstdio>

int f[32][32];
int X,Y,K,B;

void init()
{
    f[0][0]=1;
    for(int i=1;i<=31;i++)//f[i]是不包含根的
    {
        f[i][0]=f[i-1][0];
        for(int j=1;j<=i;j++)
            f[i][j]=f[i-1][j]+f[i-1][j-1];
    }
}
int calc(int x,int k)//統計[0..x]內二進制表示含k個1的數的個數
{
    int ans = 0,tot =0;//tot記錄當前路徑上已有的1的數量，ans表示答案
    for(int i=31;i;i--)//就是走前綴吧  需要31雖然是正數，但下面的(1<<(i-1))<=x要用到
    {
        if(x&(1<<i))
        {
            tot++;
            if(tot>k)break;
            x^=(1<<i);
        }
        if((1<<(i-1))<=x)ans+=f[i-1][k-tot];
    }
    if(x+tot==k)++ans;//
    return ans;
}

int change(int x)
{
    int p=1,tot=0;
    //注意溢出
    while(x>=(long long)p*B)p*=B,tot++;
    int ans =0;
    while(p&&x/p<=1)ans+=x/p*(1<<tot),tot--,x%=p,p/=B;
    ans+=(1<<(tot+1))-1;
    return ans;
}
int main()
{
    init();
    scanf("%d%d%d%d",&X,&Y,&K,&B);
    printf("%d\n",calc(change(Y),K)-calc(change(X-1),K));
    return 0;
}



spoj 1182 數位統計的做法★★★ 再二分 負數看成補碼!
/*
    論文《淺談數位類統計問題》
    題意：將區間[m,n]內的所有整數按照其二進制表示中1 的數量從小到大排序。
           如果1 的數量相同，則按照數的大小排序。  m*n>=0
           求這個序列中的第k個數。其中，負數使用補碼來表示

    依次統計區間[m,n]內二進制表示中含1的數量為0,1,2,…的數，直到累加的答案超過k，
    則當前值就是答案含1的個數，假設是s。利用例一的算法可以解決這個問題。
    接下來二分答案即可。判斷[m,n]內1的個數為s的，逼近k'
    
    需要特別處理下0  使m,n非0    
*/
#include<cstdio>
#include<cstring>

int f[33][33];

void init()
{
    f[0][0]=1;
    for(int i=1;i<=32;i++)
    {
        f[i][0]=f[i-1][0];
        for(int j=1;j<=i;j++)
            f[i][j]=f[i-1][j-1]+f[i-1][j];
    }        
}
int calc(int x,int k)
{
    int ans=0,tot=0;
    for(int i=32;i;i--)//我是虛設一個根在第32位處，其實溢出了
    {
        if(i!=32&&(x&(1<<i)))
        {
            tot++;
            if(tot>k)break;
            x^=(1<<i);
        }
        if(x&(1<<(i-1)))//我還是寫成&吧，怕負數的話用>=有問題 雖然這題沒問題
            ans+=f[i-1][k-tot];//f[i]不含根i
    }
    if(x+tot==k)++ans;
    return ans;
}
int main()
{
    init();
    int T;
    for(scanf("%d",&T);T--;)
    {
        int m,n,k;
        scanf("%d%d%d",&m,&n,&k);
        //0的特殊處理
        if(m==0)
        {
            if(k==1){printf("0\n");continue;}
            m++;
            k--;
        }
        if(n==0)
        {
            if(k==1){printf("0\n");continue;}
            n--;
            k--;
        }
        int s=1,tmp;//s從1開始！

        //觀察那個圖，m-1負溢出也不怕
        while(tmp=calc(n,s)-calc(m-1,s),tmp<k)k-=tmp,s++;
        int L=m,R=n;
        while(R>L)
        {    
            int M=(R+L)>>1;
            if(calc(M,s)-calc(m-1,s)>=k)R=M;
            else L=M+1;//M之前的肯定不可能咯
        }
        printf("%d\n",R);
    }
    return 0;
}


SPOJ 2319
這題搞了好久，醉死。從TLE 搞到 30s 再搞到5s多。。。
貼個圖。。


/*
 *  《淺談數位類統計問題》例3
    題意：將0,1,2^k-1 這些數分成M份，每份的值為該份的1的數字之和 ，求使最大的那一份最小      K <=100 ,M<=100
             最大值最小化，二分的經典應用
             二分這個最大值X，然后看能不能組成M份 ，然后再調整
             而計算[0,S]的1的個數，可以先預處理   cntOne[k] 表示長度為k的01串中1的個數，則
             cntOne[k] = 2cntOne[k-1] + 2^(k-1)

             二分的判斷函數chk的過程如下：
             lastResult = 0  上一次的結果
             for(次數cnt<=M)
                    lastResult+=X   這一次的估計值
                    if(lastResult >= cntOne[K]) return  true;
                    lastResult = find(lastResult);  找到最接近lastResult的確切值

             而find(X) 函數就是一種逼近的過程 最大值為X 找[0,S]的1的總和最接近X的
             我沒有用論文的方法，而是不斷地減X，直至最接近0了

             用這種方法挺快的！JAVA 中rank 1
 */

package SPOJ;

import java.math.BigInteger;
import java.util.Scanner;

public class _2319
{

    static int K,M;
    static BigInteger pow2[],cntOne[];
    static BigInteger ZERO = BigInteger.ZERO,ONE = BigInteger.ONE,TWO = BigInteger.valueOf(2);

    static BigInteger find(BigInteger X)
    {
        BigInteger ans = X,tmp;
        int k=K-1,one=0;
        while(k>0&&X.compareTo(ZERO)>0)
        {
            tmp = cntOne[k].add(pow2[k].multiply(BigInteger.valueOf(one)));
            if(X.compareTo(tmp)>=0)
            {
                X=X.subtract(tmp);
                one++;
            }
            k--;
        }
        if(X.compareTo(BigInteger.valueOf(one))>=0)
                X=X.subtract(BigInteger.valueOf(one));
        return ans.subtract(X);
    }

    static boolean chk(BigInteger X)
    {
      // System.out.println("X: "+X);
       BigInteger lastResult = ZERO;
       for(int cnt=0;cnt<M;cnt++)
       {
           lastResult = lastResult.add(X);
           if(lastResult.compareTo(cntOne[K])>=0)return true;
           lastResult = find(lastResult);
       }
       return false;//cnt>M
    }

    public static void main(String[] args)
    {
        Scanner cin = new Scanner(System.in);
        K = cin.nextInt();
        M = cin.nextInt();
        pow2 = new BigInteger[K+1];
        cntOne = new BigInteger[K+1];
        pow2[0] = ONE;
        cntOne[0] = ZERO;
        for(int i=1;i<=K;i++)
        {
             pow2[i] = pow2[i-1].shiftLeft(1);
             cntOne[i] = cntOne[i-1].shiftLeft(1).add(pow2[i-1]); 
        }
        BigInteger L = ONE,R = cntOne[K],Mid;
        int cnt = 0;
        while(R.compareTo(L)>0)//R>L
        {
            Mid = R.add(L).divide(TWO);
            if(chk(Mid)) R = Mid;
            else L=Mid.add(ONE);
        }
        System.out.println(R);
    }
}