题目描述

[NOIP2006 提高组] 2^k进制数

题目描述

设 $r$ 是个 $2^k$ 进制数，并满足以下条件：

• $r$ 至少是个 $2$ 位的 $2^k$ 进制数。

• 作为 $2^k$ 进制数，除最后一位外，$r$ 的每一位严格小于它右边相邻的那一位。

• 将 $r$ 转换为二进制数 $q$ 后，则 $q$ 的总位数不超过 $w$。

在这里，正整数 $k,w$ 是事先给定的。

问：满足上述条件的不同的 $r$ 共有多少个？

我们再从另一角度作些解释：设 $S$ 是长度为 $w$ 的 $01$ 字符串（即字符串 $S$ 由 $w$ 个 $0$ 或 $1$ 组成），$S$ 对应于上述条件三中的 $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$ 个。

输入格式

一行两个正整数 $k,w$ 用一个空格隔开：

输出格式

一行一个个正整数，为所求的计算结果。
即满足条件的不同的 $r$ 的个数（用十进制数表示），要求不得有前导零，各数字之间不得插入数字以外的其他字符（例如空格、换行符、逗号等）。

（提示：作为结果的正整数可能很大，但不会超过 $200$ 位）

样例 #1

样例输入 #1

3 7

样例输出 #1

36

提示

【数据范围】
$1\le k \le 9$
$1\le w \le 3\times 10^4$

NOIP 2006 提高组 第四题

这题正解不是组合数学吗

我看着机房的大佬一个个都在想正解真是瑟瑟发抖

然后我用了个递推结果还跑得贼快

思路大概是这样的

用a[i][j]表示组成一个i位数，第i位选j的所有情况

就等于a[i-1][j+1~maxx]的和

用ans表示每个a[i][j]的和，就是最后的结果

然后可以把第一维压掉，用前缀和进行优化，再加上高精度

代码里面有注释

#include<iostream>
#include<cstdio>
#define rint register int
#define ini inline int 
using namespace std;
int a[30001][201],c[201],ans[201],k,w;
ini jia(int *a,int *b)
{
    int lenc=0,x=0;
    while (lenc<a[0] || lenc<b[0])
    {
        a[++lenc]=a[lenc]+b[lenc]+x;
        x=a[lenc]/10;
        a[lenc]%=10;    
    }
    if (x>0) a[++lenc]=x;
    a[0]=lenc;
}
int main()
{
    scanf("%d%d",&k,&w);
    int kk=w%k;int hh=w/k;
    int y=0;
    for (rint i=1;i<=kk;i++)
        y+=1<<(i-1);     //最高位最大是几
    int minn=(1<<k)-1;//第一位最大是多少
    if (hh==1 || (hh==2 && kk==0))
    {
        if (kk==0) y=minn;int tot=0;
        for (rint i=1;i<=y;i++)
            tot+=minn-i;
        cout<<tot;
        return 0;
    }//特判两位以内的情况
    for (rint i=1;i<=minn-1;i++)
    {
        a[i][1]=i;a[i][0]=1;
        jia(ans,a[i]);
    }//第二位是minn-1到1各有多少种可能
    for (rint i=3;i<=hh;i++)
        for (rint j=1;j<=minn-i+1;j++)
//第i位最大是minn-i+1
//第i位是1到minn-i+1各有多少种可能
        {
            jia(a[j],a[j-1]);
            jia(ans,a[j]);
        }
//以下是单独处理最高位，因为最高位有限制
    for (rint j=1;j<=minn-hh;j++)
        jia(a[j],a[j-1]);
    for (rint j=minn-hh;j>=max(minn-hh-y+1,1);j--)
        jia(ans,a[j]);
//我们的前缀和是倒着存的
    for (rint i=ans[0];i>=1;i--)
        printf("%d",ans[i]);
}

如果能够从题目繁琐的叙述中―嗅出这是一道与组合数有关的问题，那么离解决问题就已经不远了；

假设还能够进一步猜想出样例是C(7,2)+C(6,2)，那么就已经成功一大半了。

分析题目中的第二个条件：作为2k 进制数，除最后一位外，r的每一位严格小于它右边相邻的那一位。

通过分析理解，题目的意思可表达为：将长度为w的二进制串k位一节划分为w/k份(w/k要取上整，如7/3=2.3，应为3份)，则对应的2k 进制数最多是int[w/k]+1位数，这个位数用len表示，加上题目规定：最少为2位数，从左到右每一个数都升序的条件，这样的2k 进制数共多少个呢？

它等于两类组合数之和：

第一类：位数为2—len-1的2k 进制数种数； 它等于从2k -1个数中分别不重复地取2个、3个、…….len-1个数的不同组合数之和，即c(2k-1,2)+ c(2k-1,3)+……+ c(2k -1,len-1)，或∑c(2k -1,i)，(2< =i<=len-1)；

第二类：位数已经达到len的2k 进制数种数； 这类数的首位可能够是1，2，……2k-i-1，从第2位开始取数时每次都要扣除小于左边相邻数的这些数，因此可供选择的数越来越少，累加起来是∑c(2k –(i+1),len)，(1<=i<=2k )。

上代码

#include<iostream> 
#include<cstdio> 
#include<cstring> 
using namespace std; 
const int Maxn=205; 
int K,W,N,M,P;  
int Sum[Maxn]={0},b[Maxn],c[Maxn]; 
void Print(int p[]) 
{  
    int i;  
    printf("%d",p[p[0]]);  
    for(i=p[0]-1;i>0;i--)  
        {   
            printf("%d",p[i]/1000);   
            printf("%d",p[i]/100%10);   
            printf("%d",p[i]/10%10);   
            printf("%d",p[i]%10);  
        }  
        printf("\n"); 
}  
void CalC(int n,int m) 
{  
    int i,j,k,x;  
    if(m>n) return;  
    memset(c,0,sizeof(c));  
    c[0]=c[1]=1;  
    for(k=1;k<=m;k++)  
    {   
        x=n-k+1;   
        for(i=1;i<=c[0];i++)c[i]=c[i]*x;   
        for(i=1;i<=c[0];i++){c[i+1]+=c[i]/10000;c[i]%=10000;}   
        if(c[c[0]+1]>0)c[0]++;   
        x=k; j=0;   
        for(i=c[0];i>0;i--)   
        {    
            j=j*10000+c[i];    
            c[i]=j/x;    
            j%=x;   
        }   
        while(c[c[0]]==0)c[0]--;  
    }  
    memcpy(b,Sum,sizeof(Sum));  
    Sum[0]=max(b[0],c[0]);  
    for(i=1;i<=Sum[0];i++)
        Sum[i]=b[i]+c[i]; 
    for(i=1;i<=Sum[0];i++)
    {
        Sum[i+1]+=Sum[i]/10000;
        Sum[i]%=10000;
    }  
    if(Sum[Sum[0]+1]>0)
    Sum[0]++; 
}  
main() 
{  
    int i;  
    scanf("%d%d",&K,&W);  
    N=(1<<K)-1; 
    M=W/K; 
    P=W%K; 
    P=(1<<P)-1;  
    for(i=2;i<=M;i++)
        CalC(N,i);  
    for(i=1;i<=P;i++)
        CalC(N-i,M);  
    Print(Sum);  
    return 0; 
}