ural 1057Amount of Degrees ——数位DP

link:http://acm.timus.ru/problem.aspx?space=1&num=1057

论文： 浅谈数位类统计问题 刘聪

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <queue>
#include <deque>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <functional>
#include <fstream>
#include <iomanip>
#include <sstream>
#include <numeric>
#include <cassert>
#include <ctime>
#include <iterator>
const int INF = 0x3f3f3f3f;
const int dir[8][2] = {{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};
using namespace std;
int a[33][33];
int bto2(int x, int b)
{
    int tm[33], cnt = 0, ans = 0;
    while (x)
    {
        tm[cnt++] = x % b; x /= b;
    }
    for (int i = cnt - 1; i >= 0; --i)
    {
        if (tm[i] && (tm[i] != 1))
        {
            ans += ((1<<(i+1))-1); break;
        }
        else if(tm[i]) ans += (1<<i);
    }
    return ans;
}
int calc(int x, int k)
{
    int tot = 0, ans = 0;
    for (int i = 31; i > 0; --i)
    {
        if (x & (1<<i))
        {
            ++tot; if (tot > k) break;
            x = x ^ (1<<i);
        }
        if ((1<<(i - 1)) <= x) ans += (a[i-1][k-tot]);
    }
    if (tot + x == k) ++ans;
    return ans;
}
int main(void)
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin );
    #endif // ONLINE_JUDGE
    int x,y,k,b;
    memset(a, 0, sizeof(a));
    a[0][0] = 1;
    for (int i = 1; i <= 31; ++i)
    {
        a[i][0] = a[i-1][0];
        for (int j = 1; j <= i; ++j) a[i][j] = a[i-1][j] + a[i-1][j-1];
    }
    while (~scanf("%d%d%d%d",&x, &y, &k, &b))
    {
        long long int ans = 0;
        if (b == 2)
        {
            ans = calc(y, k) - calc(x - 1, k);
        }
        else
        {
            int X = bto2(x - 1, b), Y = bto2(y, b);
            ans = calc(Y, k) - calc(X, k);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

走吧，小胖！