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 }