F. Igor and Interesting Numbers

http://codeforces.com/contest/747/problem/F

cf #387 div2 problem f

非常好的一道题。看完题，然后就不知道怎么做，感觉是dp，但是不知道怎么枚举。还有就是一般求第k小的思路一般是什么？对这类题目理解的不是很好。

这道题，跟上一篇的题解里面写的hdu 1002 递增数的题目的解法差不多，但是底层的求解需要花一些时间去推敲！

不会做，就看官方题解，看不懂说的什么。就从下面的讨论找大神的题解。

I can describe my solution
Binary search on what is the answer(mi). So, the problem reduces to counting number of numbers <= mi such that each digit occurs <= t times.
In fact, we solve a more general problem — find number of numbers of length i such that each digit j occurs <= b[j] times. 0 complicates the matter somewhat but for the time assume that 0 can be placed anywhere and obeys constraint like the normal digits. Then formulate dp[i][j] = number of numbers with i digits and place only digits <= j. Iterate k = how many j digits will be there — 0 to min(i,b[j]) then dp[i][j] = sum((i choose k)*dp[i-k][j-1]). Base cases are simple to write.
Overall count can be calculated by fixing highest digit(depends on mi) and then a dp call, then next digits etc.. similar to what we do in offline digits dp solution. The prefix digits that are fixed decide what array b is(t — number of times digit has occurred till now).
Finally for 0, simply calculate for lesser lengths using a similar logic. Checkout my solution for more details.
Time complexity = O(p^3*d^3) where p=max digits in answer=9 and d=16 and = runs in 15 ms :)

看完这个之后，思路就清晰很多了，然后接下来就是二分的判断条件，对于给定mi，如何判断比它小的满足要求的数的个数呢？这个求解思路跟上面写的hdu的1002思路一致，按长度进行累加和，因为一个数的长度很小，这里int的16进制表示，最大长度为32/4 = 8，这个长度很短，可以通过预处理来快速求解。所以，首先需要解决，长度为k的满足要求的数的个数这个问题！由于题目要求的是每个数出现次数小于等于t，所以如果按位枚举的话，需要记住每一个数的出现次数，这个好像不容易解决，然后考虑可以使用的数的最大值，使用排列组合的方式，就是上面的思路进行解决。这个问题解决之后，然后就是对于一个数，先求长度比它小的数的个数，然后求解跟他长度一致的数的个数，依次从高位到低位，进行求解，枚举每一个数字的方式进行。讲的好乱，我都听不懂了！

注意上面的复杂度分析：代码运行速度非常快。

又掌握一种套路，就是上面的dp求解的过程，这个不好思考，求解每个数字出现此小于等于t的数字的个数，使用组合的方式，注意对0的单独处理。

  1 #include <vector>
  2 #include <list>
  3 #include <map>
  4 #include <set>
  5 #include <deque>
  6 #include <queue>
  7 #include <stack>
  8 #include <bitset>
  9 #include <algorithm>
 10 #include <functional>
 11 #include <numeric>
 12 #include <utility>
 13 #include <sstream>
 14 #include <iostream>
 15 #include <iomanip>
 16 #include <cstdio>
 17 #include <cmath>
 18 #include <cstdlib>
 19 #include <cctype>
 20 #include <string>
 21 #include <cstring>
 22 #include <cstdio>
 23 #include <cmath>
 24 #include <cstdlib>
 25 #include <ctime>
 26 #include <string.h>
 27 #include <fstream>
 28 #include <cassert>
 29 using namespace std;
 30 
 31 #define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
 32 #define sz(a) int((a).size())
 33 #define rep(i, s, n)  for(int i = s; i <= (n); ++i)
 34 #define rev(i, n, s)  for(int i = (n); i >= s; --i)
 35 #define fore(x, a) for(auto &&x : a)
 36 typedef long long ll;
 37 const int mod = 1000000007;
 38 const int N = 100005;
 39 
 40 int a[9];
 41 int t;
 42 int b[16];
 43 ll dp[8][16];
 44 ll c[9][9];
 45 
 46 ll go(int p, int x) {
 47   if (p == -1) return 1;
 48   if (x == 0) {
 49     if (t - b[x] >= p + 1) return 1;
 50     return 0;
 51   }
 52   ll &res = dp[p][x];
 53   if (res >= 0) return res;
 54   res = 0;
 55   rep(i, 0, min(p + 1,t-b[x])) {
 56     res += c[p+1][i]*go(p - i, x - 1);
 57   }
 58   return res;
 59 }
 60 
 61 char hex(int x) {
 62   if (x >= 10) return 'a' + (x - 10);
 63   return '0' + x;
 64 }
 65 
 66 ll g[9];
 67 
 68 ll f(int x) {
 69   ll res = 0;
 70   memset(b, 0, sizeof(b));
 71   rep(i, 1, 15) {
 72     memset(dp, -1, sizeof(dp));
 73     b[i]++;
 74     res += go(x - 1, 15);
 75     b[i]--;
 76   }
 77   return res;
 78 }
 79 
 80 int main() {
 81 #ifdef loc
 82   if (!freopen((string(FOLDER) + "inp.txt").c_str(), "r", stdin)) {
 83     assert(0);
 84   }
 85   freopen((string(FOLDER) + "out.txt").c_str(), "w", stdout);
 86 #endif
 87   boost;
 88   ll k;
 89   cin >> k >> t;
 90   rep(i, 0, 8) {
 91     c[i][0] = 1;
 92     rep(j, 1, i) {
 93       c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
 94     }
 95   }
 96   rep(i, 0, 8) {
 97     g[i] = f(i);
 98     if (i > 0) g[i] += g[i - 1];
 99   }
100   ll lo = 1, hi = (1LL << 36) - 1;
101   while (lo < hi) {
102     ll mi = (lo + hi) / 2;
103     ll p = mi + 1;
104     int td = 0;
105     rep(i, 0, 8) {
106       a[i] = p % 16;
107       p /= 16;
108       td = i;
109       if (p == 0) {
110         break;
111       }
112     }
113     ll tot = td > 0 ? g[td - 1] : 0;
114     memset(b, 0, sizeof(b));
115     rev(i, td, 0) {
116       rep(j,(i==td)?1:0, a[i] - 1) {
117         b[j]++;
118         if (b[j] <= t) {
119           memset(dp, -1, sizeof(dp));
120           tot += go(i - 1, 15);
121         }
122         b[j]--;
123       }
124       b[a[i]]++;
125       if (b[a[i]] > t) break;
126     }
127     if (tot >= k) hi = mi;
128     else lo = mi + 1;
129   }
130   vector<int> ans;
131   while (lo > 0) {
132     ans.push_back(lo % 16);
133     lo /= 16;
134   }
135   reverse(ans.begin(), ans.end());
136   fore(x, ans) {
137     cout << hex(x);
138   }
139   cout << endl;
140   return 0;
141 }