这题我以前写过的，现在就当是再温习一遍吧，思路就是递推（也就是动态规划）根据一个公式推导出来的DP方程，首先我用f[i][j]表示第i位数以j开头的数字共有多少个，那么最容易得到的一个转移方程是：
f[i][j] = f[i – 1][j + 1] + f[i – 1][j + 2] + ……. + f[i – 1][n – 1] + f[i – 1][n].
但是这个方程给我们的感觉就是一个字——太慢了，为什么这么慢呢？因为它就是这么慢，要把所有的一个个相加一次，但是注意到上面我画红的部分！就是用这个公式，这部分能够表示成啥？很简单啊：
f[i][j + 1] = f[i – 1][j + 2] + ……. + f[i – 1][n – 1] + f[i – 1][n].
那么智商高一点的人就看到玄机了，能够把f[i][j]简化成如下的形式：
f[i][j] = f[i][j + 1] + f[i – 1][j + 1]
如此一来程序就清晰多了，代码也很好写，要注意的是搜索时j是从后向前搜索，我还是使用面向对象的思想，先封装了一套int类型的，然后再修改成高精度类型的，int类型的（40分）如下：
typedef int num;
num f[61][513];
num ans;
void give(num a, int b)
{
a = b;
}
void add(num a, num b)
{
a += b;
}
void output(num a)
{
printf("%d", a);
}
int main(void)
{
int i, j;
int n, s, k, t, l;
scanf("%d%d", &s, &n);
k = 1 << s;
for(i = 0; i < k; i++){
give(&f[0][i], 1);
}
t = n / s;
for(i = 1; i <= t; i++){
for(j = k – i – 1; j >= 1; j–){
add(&f[i][j], &f[i][j + 1]);
add(&f[i][j], &f[i – 1][j + 1]);
}
}
for(i = 1; i < t; i++){
for(j = k – i – 1; j >= 1; j–){
add(&ans, &f[i][j]);
}
}
l = n – t s;
if(l == 0){
l = k;
}else{
l = 1 << l;
}
for(i = 1; i < l; i++){
add(&ans, &f[t][i]);
}
output(&ans);
printf("\n");
return 0;
}
详细修改了一番之后，发现主函数中错了，后来详细修改了一番，弄得我以为高精度写错了，仔细检查之后发现两个地方错了，第一个是数组开小了，本来是num f[61][513]，后来发现要使用f[513][513]，再一个就是不能够直接使用用(n – 1)/s，因为如果用30000/1（k = 1, w = 30000）的话那数组又会显得小了，需要f[30000][513]，但是实际上又跟本用不到（因为k很小时最多只有
所以最终修改了一大番，确定了AC代码：
#include <stdio.h>
#define max(a, b) ((a)>(b)?(a):(b))
#define used 100000000
#define bits ((int)log10(used))
#define MAX 26
typedef struct{
int num[MAX];
int len;
}num;
num f[513][513];
//数组开小了
num ans;
void give(num a, int b)
{
int i;
for(i = 0; b != 0; i++){
a->num[i] = b % used;
b /= used;
}
a->len = i;
}
void add(num a, num b)
{
int i;
int len = max(a->len, b->len);
int re = 0;
for(i = 0; i < len; i++){
a->num[i] += b->num[i] + re;
re = a->num[i] / used;
a->num[i] %= used;
}
if(re > 0){
a->num[i] = re;
len++;
}
a->len = len;
}
void output(num a)
{
int i;
int len = a->len, num = a->num;
printf("%d", num[len – 1]);
len–;
for(i = len – 1; i >= 0; i–){
printf("%.*d", bits, num[i]);
}
}
int main(void)
{
int i, j;
int n, s, k, t, l;
scanf("%d%d", &s, &n);
k = 1 << s;
t = (n – 1) / s + 1;
if(t > k){ //一直没写这个~!! 所以可能会出现各种想象不到的情况, 如:t = 3000
t = k;
}
for(i = 0; i < k; i++){
give(&f[0][i], 1);
}
for(i = 1; i < t; i++){
for(j = k – i – 1; j >= 1; j–){
add(&f[i][j], &f[i][j + 1]);
add(&f[i][j], &f[i – 1][j + 1]);
}
}
for(i = 1; i < t; i++){
for(j = k – i – 1; j >= 1; j–){
add(&ans, &f[i][j]);
}
}
l = n % s;
if(l == 0){
l = k;
}else{
l = 1 << l;
}
for(i = 1; i < l; i++){
add(&ans, &f[t – 1][i]);
}
output(&ans);
printf("\n");
return 0;
}