相关链接
题目传送门:http://codeforces.com/contest/747/problem/F
优雅的暴力:http://codeforces.com/blog/entry/49171?#comment-331886
官方题解:http://codeforces.com/blog/entry/49171
神犇代码:http://codeforces.com/contest/747/submission/23125896
解题报告
首先这题推一推式子发现答案最多9位的样子
于是我们就可以暴力搜索,用Meet in Middle来做就好
当然这题有更加清真的、类似数位DP的做法
假定我们能够做到给定字符串长度和每个数字可以用多少次,求有多少种合法情况
的话
显然可以像数位DP一样,从高位到低位逐位确定每一位的数字应该是多少
现在问题转化为如何求的合法情况。
依次考虑每一种数字,显然对答案的贡献只与有多少个空位有关
于是f[i][j]表示现在考虑到第i种数字,还剩j个空位的方案数
这样的话,暴力转移即可。
时间复杂度:O(16^3+16*9)
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int k,t,C[21][21],res[21];
char ori[]={'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'};
inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}
inline LL solve(int len, bool ty) {
static LL f[2][20]; bool w,p;
memset(f,0,sizeof(f));
f[p=0][ty] = 1; w = 1;
for (int i=0;i<16;i++,w^=1,p^=1) {
memset(f[w],0,sizeof(f[w]));
for (int j=len;~j;j--)
for (int k=min(len-j,res[i]-(ty&(i==0)));~k;k--)
f[w][j+k] += f[p][j] * C[k][len-j];
}
return f[p][len];
}
int main() {
for (int i=0;i<=20;i++) {
C[0][i] = C[i][i] = 1;
for (int j=1;j<i;j++)
C[j][i] = C[j-1][i-1] + C[j][i-1];
}
k = read(); t = read();
for (int i=0;i<=15;i++)
res[i] = t;
LL tmp; int len=1;
while ((tmp = solve(len,0) - solve(len,1)) < k)
k -= tmp, len++;
for (int i=len,ret=1;i;ret=0,i--) {
res[ret]--;
while ((tmp = solve(i-1,0)) < k)
res[ret++]++, res[ret]--, k -= tmp;
printf("%c",ori[ret]);
}
return 0;
}