前言
讲过没听懂，再讲没调出来的题——有价值的题，需要写题解的题
题目
讲解
配合代码食用更佳
这题用(DP)应该很好看出来吧(只是可能会想到奇怪的状压= =)
首先我们发现我们受到了数字长度的限制，不知道长度使我们的转移难上加难，所以我们先要把该数字的长度算出来
这是一个DP：(getlen函数)
我们令(dp[i][j])为只使用前(i)个数字，目前填了(j)个位置的方案数(当然是忽略了前导零的)
然后我们选择暴力枚举长度，计算出每种长度的方案数加上后是否达到了(k)，如果达到了，那么说明该数的长度为(k)，没达到就减去，为之后统计答案做准备
设枚举长度为(len)
由于忽略了前导零，所以(dp[0][i]=C(len-1,i))(习惯这么表达组合数= =)
对于其它的(dp[i][j])，我们考虑从(dp[i-1][j-k])转移
上一个状态是填了(j-k)个位置，剩下(len-(j-k))个位置，我们要填(k)个位置
那么(dp[i][j] = sum^{min {j,t}}_{k=0} dp[i-1][j-k]*C(len-(j-k),k))
然后我们就可以计算出该数字的长度了
这是另一个DP：(solve函数)
接下来我们要考虑在知道长度的情况下的第(k)小的数字是什么(因为我们已经把长度小于该数的数减掉了)
其实与上面的思路和DP都很类似
我们 从高位到低位 再 从小到大 枚举当前位置的数字
然后用类似的方法统计个数，看是否达到(k)，没达到就减去
由于我们枚举了当前位置的数字，所以在用DP统计方案数的时候0就可以作为首位计算
仍然是这个式子，只是(len)的含义不同了，是没选的位置的长度
(dp[i][j] = sum^{min {j,t}}_{k=0} dp[i-1][j-k]*C(len-(j-k),k))
当然我们还是需要特殊处理(i=0)的时候的DP值
因为(0)之前没有状态了，无法从前面转移
我们发现如果(j eq k)，那么由于无法从前面转移，那么方案数为0
否则就是(C(len-j,k))，方案数依然是(C()总长(-)已填长度(=)剩余长度(,)选填长度())
所以两个DP只是有一个要不要管前导零的区别
代码
//12252024832524
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 165;
const int MAXJZ = 16;
int n,t,len;
int lim[MAXJZ];
char dic[MAXJZ];
LL C[MAXN][MAXN],dp[MAXN][MAXN];
int Read()
{
int x = 0,f = 1;char c = getchar();
while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
void Put1(int x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
void Put(int x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x);
if(c >= 0) putchar(c);
}
template <typename T>T Max(T x,T y){return x > y ? x : y;}
template <typename T>T Min(T x,T y){return x < y ? x : y;}
template <typename T>T Abs(T x){return x < 0 ? -x : x;}
void pre()
{
C[0][0] = 1;
for(int i = 1;i <= 160;++ i)//其实20左右就够用了
{
C[i][0] = 1;
for(int j = 1;j <= i;++ j)
C[i][j] = C[i-1][j] + C[i-1][j-1];
}
for(int i = 0;i <= 9;++ i) dic[i] = '0' + i;
for(int i = 10;i < MAXJZ;++ i) dic[i] = 'a' + i - 10;
}
void getlen()
{
for(len = 1;;++len)
{
memset(dp,0,sizeof(dp));
for(int i = 0;i < Min(len,t+1);++ i) dp[0][i] = C[len-1][i];
for(int i = 1;i < MAXJZ;++ i)
{
for(int j = 0;j <= len;++ j)//现在的总长度
{
for(int k = 0;k <= Min(j,t);++ k)//填k个i
dp[i][j] += dp[i-1][j-k] * C[len-(j-k)][k];
}
}
if(dp[15][len] >= n) break;
n -= dp[15][len];
}
//printf("len : %d
",len);
}
void solve()
{
//printf("less : %d
",n);//935395
LL dz;
for(int i = 0;i < MAXJZ;++ i) lim[i] = t;
for(int LEN = len;LEN >= 1;-- LEN)
{
int MIN = 0 + (LEN == len);//这一位是否能为0
for(int i = MIN;i < MAXJZ;++ i)//枚举当前这一位
{
if(!lim[i]) continue;
memset(dp,0,sizeof(dp));
lim[i]--;
//需要填的长度：LEN-1
for(int j = 0;j < MAXJZ;++ j)//枚举现在填什么数字
for(int lennow = 0;lennow <= LEN-1;++ lennow)//现在的长度
for(int k = 0;k <= Min(lennow,lim[j]);++ k)//填k个j
{
if(!j)
{
if(k == lennow) dz = 1;
else dz = 0;
}
else dz = dp[j-1][lennow-k];
dp[j][lennow] += dz * C[LEN-1-(lennow-k)][k];
}
if(dp[15][LEN-1] >= n)
{
putchar(dic[i]);
break;
}
n -= dp[15][LEN-1];
lim[i]++;
}
}
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n = Read(); t = Read();
pre();
getlen();
solve();
return 0;
}