Description
设r是个2^k 进制数，并满足以下条件：
(1)r至少是个2位的2^k 进制数。
(2)作为2^k 进制数，除最后一位外，r的每一位严格小于它右边相邻的那一位。
(3)将r转换为2进制数q后，则q的总位数不超过w。
在这里，正整数k(1<=k<=9)和w(k<W<=30000)是事先给定的。
问：满足上述条件的不同的r共有多少个？
我们再从另一角度作些解释：设S是长度为w 的01字符串(即字符串S由w个“0”或“1”组成)，S对应于上述条件(3)中的q。将S从右起划分为若干个长度为k 的段，每段对应一位2^k进制的数，如果S至少可分成2段，则S所对应的二进制数又可以转换为上述的2^k 进制数r。
例：设k=3，w=7。则r是个八进制数（2^3=8）。由于w=7，长度为7的01字符串按3位一段分，可分为3段(即1，3，3，左边第一段只有一个二进制位)，则满足条件的八进制数有：
2位数：高位为1：6个(即12，13，14，15，16，17)，高位为2：5个，…，高位为6：1个(即67)。共6+5+…+1=21个。
3位数：高位只能是1，第2位为2：5个(即123，124，125，126，127)，第2位为3：4个，…，第2位为6：1个(即167)。共5+4+…+1=15个。
所以，满足要求的r共有36个。
Input
输入文件只有1行，为两个正整数，用一个空格隔开：
k W
Output
输出文件为1行，是一个正整数，为所求的计算结果，即满足条件的不同的r的个数(用十进制数表示)，要求最高位不得为0，各数字之间不得插入数字以外的其他字符(例如空格、换行符、逗号等)。
(提示：作为结果的正整数可能很大，但不会超过200位)
Sample Input
3 7
Sample Output
36
分析：
对于这种统计问题，很容易想到的方法就是递推。
我们先尝试着列出递推式：F[i,j]=F[i-1,0]+F[i-1,1]+F[i-1,2]+...F[i-1,j-1]
这里F[i,j]表示递第i位是j的数有多少种。
边界条件是:
1.F[1,t]=1 (1<=t<=limit)
(1)w%k>0时 limit=2^(w%k)-1
(2)w%k=0时 limit=2^k-1
2.F[i,0]=1 (i<len-1) PS:“不超过”w位
F[i,0]=0 (i>=len-1) PS:至少是两位数
当然，如果直接这样做，肯定会严重超时。
注意到F[i,j-1]=F[i-1,1]+..F[i-1,j-2]
我们可以将原递推式转换成：
F[i,j]=F[i-1,j-1] + F[i,j-1] j>1
F[i-1,j-1] j=1
这样程序效率就大幅度提高了。
最后注意使用高精度计算即可
【参考程序】：
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int f[10][1050][201],blank[201],ans[201];
int k,w;
int Max(int a,int b)
{
if(a>b) return a;
else return b;
}
void add(int c[],int a[],int b[])
{
c[0]=max(a[0],b[0]);
for(int i=1;i<=c[0];i++)
{
c[i]=a[i]+b[i];
c[i+1]+=c[i]/10;
c[i]%=10;
}
while(c[c[0]+1])
{
c[0]++;
c[c[0]+1]+=c[c[0]]/10;
c[c[0]]%=10;
}
}
void print(int a[])
{
for(int i=a[0];i>=1;i--) printf("%d",a[i]);
printf(" ");
}
int main()
{
blank[0]=1;
scanf("%d%d",&k,&w);
int limit;
limit=w%k;
if(limit==0) limit=k;
w=(w-limit)/k;
limit=(1<<limit)-1;
memset(f,0,sizeof(f));
memset(blank,0,sizeof(blank));
memset(ans,0,sizeof(ans));
for(int i=0;i<=limit;i++)
{
f[1][i][0]=1; f[1][i][1]=1;
}
if(w<=1)
{
f[1][0][0]=1; f[1][0][1]=0;
}
for(int i=2;i<=w+1;i++)
{
if(i<w)
{
f[i%2][0][0]=1; f[i%2][0][1]=1;
}
else
{
f[i%2][0][0]=1; f[i%2][0][1]=0;
}
for(int j=1;j<=(1<<k)-1;j++)
{
memcpy(f[i%2][j],blank,sizeof(blank));
add(f[i%2][j],f[(i-1)%2][j-1],f[i%2][j]);
if(j>1) add(f[i%2][j],f[i%2][j-1],f[i%2][j]);
}
}
for(int i=0;i<=(1<<k)-1;i++)
add(ans,ans,f[(w+1)%2][i]);
for(int i=ans[0];i>=1;i--)
printf("%d",ans[i]);
printf("\n");
return 0;
}