NOIP 2006 2^k进制数

洛谷 P1066

【分析】

又是一道思路神题…
同时还是一道卡空间神题…
题目中的那个从另一角度分析就已经蕴含了这个题的基本思路。就以题目的例子为例，长度为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]，这样高精就只用加法了。
（分析参考hzwer）
讲道理组合数数组要开到 512*512*100，但是会MLE…然后我们惊人的发现测试数据中k最大是8…
来自NOIP 2006 2^k进制数

【程序代码】

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int ans[500],k,w,h,p,c[315][315][85]; 
inline void getsum(int x[],int y[],int z[]){//高精度 
    int i,j,add=0;
    x[0]=max(y[0],z[0]);
    for(int i=1;i<=x[0];i++){
        x[i]+=y[i]+z[i]+add;
        add=0;
        if(x[i]>=10) add=x[i]/10,x[i]%=10;
    }
    if(add) x[++x[0]]=add;
} 
inline void calc(int x[]){//高精度 
    int i,j,add=0;
    ans[0]=max(ans[0],x[0]);
    for(int i=1;i<=ans[0];i++){
        ans[i]+=x[i]+add;
        add=0;
        if(ans[i]>=10) add=ans[i]/10,ans[i]%=10;
    }
    if(add) ans[++ans[0]]=add;
}
int main(){
    scanf("%d%d",&k,&w);
    h=pow(2,w%k)-1;
    p=pow(2,k)-1;
    for(int i=0;i<=p;i++)
     for(int j=0;j<=i;j++)
      if(j==0) c[i][i][0]=c[i][j][1]=1;
      else getsum(c[i][j],c[i-1][j-1],c[i-1][j]);
    for(int i=2;i<=w/k;i++) calc(c[p][i]);//如果令首段的时候为0，那么当后面有2段，三段（指的是从第一段开始）。。。。时，一直到w/k，必定会有从2^k-1中选出来指定位数的数，组合成一个上升的序列，然后利用组合数公式可以求出这个方案数 
    for(int i=1;i<=h;i++) calc(c[p-i][w/k]);//如果首段不为0， 会有多种选择，那么在这一整段中，减去首段已经用了的数，剩下的放在整个数中会有一个方案数，然后累加 
    for(int i=ans[0];i;i--) printf("%d",ans[i]);
    printf("\n");
    return 0; 
}