今天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);
    }
}