2^k进制数 解题报告

这题困扰了我好几天，详细看了别人的题解，自己反复琢磨，终于琢磨透了。
把我的思路讲一下，f[i][j] 表示第i位(从右向左数, 如12中的1是第二位)，则很容易得到一个DP：
f[i][j] = f[i – 1][j + 1] + f[i – 1][j + 2] + f[i – 1][j + 3] + …. + f[i – 1][n] (n为极限，放在后面讲。)
不用说，用这个递推公式绝对会超时，所以还需要对公式观察一下：
f[i][j] = f[i – 1][j + 1] + f[i – 1][j + 2] + f[i – 1][j + 3] + …. + f[i – 1][n]
上面用红色标记出来的能够用f[i][j + 1] 表示，怎么来的？呵呵，就是因为
f[i][j] = f[i – 1][j + 1] + f[i – 1][j + 2] + f[i – 1][j + 3] + …. + f[i – 1][n] 所以
f[i][j + 1] = f[i – 1][j + 2] + f[i – 1][j + 3] + …. + f[i – 1][n].所以
f[i][j] = f[i][j + 1] + f[i – 1][j + 1]
这就好求了，但是这里需要从大数向小数递减（即j是从n – 1 递减到 1）
然后，我提供一个小剪枝，第i个数的最大值位(1 << k) – j，比如只有一位数字的时候（题目要求至少两位，但是这里只是说明。）当k=3的时候，第一位能够选择的数字是1-7；当有两位数字且k=3是，第二位就只能是1~6而不是1~7了（自己思考下）

还有一个重要的就是需要高精度！！别人都说int要压4位运算，但是这里我压了9位，原因很简单，压4位数的原因是99999^2 > 2^32，就是说当遇到最坏情况下的乘法时，只能使用4位，5位就会溢出；但是这个题目要清楚一点，高精度只用实现加法！所以可以压9位，再多的话也是会超时的。
代码就在下面提供了吧:

#include <stdio.h>
#define MAX 24
#define USED 1000000000
#define max(a, b) ((a)>(b)?(a):(b))
typedef unsigned bignum[MAX];
bignum count[513][513];
bignum ans;

void add(bignum a, bignum b)
{
 int i, j, t;
 int c = max(a[0], b[0]);
 unsigned to = 0;
 if(a[0] < b[0]){
 a[0] = b[0];
 }
 for(i = 0; i < c; i++){
 t = MAX - 1 - i;
 a[t] += b[t] + to;
 to = a[t] / USED;
 if(to > 0){
 a[t] %= USED;
 }
 }
 if(to != 0){
 a[MAX - 1 - i] = to; //狂晕,,, 这里的to写成了t 
 a[0]++;
 }
}

void output(bignum n)
{
 int i, t;
 for(i = MAX - n[0]; i <= MAX - 1; i++){
 printf(%.*d, (i == MAX - n[0]) ? 0 : 9, n[i]);
 }
}

int main(void)
{
 int i, j;
 int top, limit;
 int k, w, n;
 scanf(%d%d, &k, &w);
 n = w / k;
 top = limit = (1 << k) - 1;
 if(w - n * k > 0){
 top = (1 << (w - n * k)) - 1;
 n++;
 }
 if(limit < n){
 n = limit;
 }
 for(i = 1; i <= limit; i++){
 count[1][i][0] = 1;
 count[1][i][MAX - 1] = 1;
 }
 for(i = 2; i <= n; i++){
 for(j = limit - i + 1; j >= 1; j--){
 add(count[i][j], count[i - 1][j + 1]);
 add(count[i][j], count[i][j + 1]);
 }
 }
 for(i = 2; i < n; i++){
 for(j = 1; j <= limit; j++){
 add(ans, count[i][j]);
 }
 }
 for(j = 1; j <= top; j++){
 add(ans, count[i][j]);
 }
 output(ans);
 return 0;
}