2^k进制数 （C++代码）

解题思路:

  题目的例子为例，长度为7位的01字串按3位一段就这样分：0 000 000。其中除了首段，每段都小于(111)2，也即小于2k，而首段自然是小于2w%k（对于w%k为0时也成立）了。

    如果首段为0，则当这个2k进制数位数分别为2、3、…、[n/k]时，如果用b_max表示2k，对应的解的个数分别为C[b_max-1][2]、C[b_max-1][3]、…、C[b_max-1][n/k]（C[i][j]表示从i个数里选j个构成一组组合）。

    如果首段不为0，设首段为x，则解就有c[b_max-x-1][n/k]个。

    这样，求解的个数就搞定了，剩下的活就是高精了。求组合数可以用这个公式：C[n][m]=C[n-1][m-1]+C[n-1][m]，这样高精就只用加法了。

注意事项:





参考代码:

#include<cstdio>  

#include<algorithm>  

#include<iostream>

#define maxn1 200  

#define maxn2 1000  

using namespace std;

int ans[maxn1 + 20];

int f[maxn2 + 100][maxn1 + 20];

void add(int a[], int b[])

{

int i, j, k, last = 0;

a[0] = max(a[0], b[0]);

for (i = 1; i <= a[0]; i++)

{

a[i] += b[i] + last;

last = a[i] / 10, a[i] %= 10;

}

if (last>0)a[++a[0]] = last;

}

int main()

{

int i, j, k, x, y, w;

cin >> k >> w;

if (w <= k) { 

cout << "0" << endl; 

return 0;

}

y = (1 << k) - 1;

if (w%k == 0)x = y, k = w / k - 1;

else x = (1 << (w%k)) - 1, k = w / k;

f[1][0] = 1, f[1][1] = 1;

ans[0] = 0;

for (i = 1; i <= y; i++)

{

for (j = i + 1; j >= 1; j--)

add(f[j], f[j - 1]);

if (i >= y - x && i<y)add(ans, f[k + 1]);

}

for (i = 3; i <= k + 1; i++)

add(ans, f[i]);

for (i = ans[0]; i >= 1; i--)

cout << ans[i];

cout << endl;

return 0;

}