跳至正文

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;
}

发表评论

您的电子邮箱地址不会被公开。