【正经题解】2^k进制数
2024-02-21 14:22:07
发布于:浙江
14阅读
0回复
0点赞
作为 进制数,除最后一位外, 的每一位严格小于它右边相邻的那一位。
通过分析理解,题目的意思可表达为:将长度为 的二进制串 位一节划分为 / 份( / 要取上整,如 / . ,应为 份),则对应的 进制数最多是 [ / ] 位数,这个位数用 表示,加上题目规定:最少为 位数,从左到右每一个数都升序的条件,这样的 进制数共多少个呢?
它等于两类组合数之和:
第一类:位数为 — 的 进制数种数; 它等于从 个数中分别不重复地取 个、 个、……. 个数的不同组合数之和,即 ( , ) ( , ) …… ( , ),或∑ ( , ),( );
第二类:位数已经达到 的 进制数种数; 这类数的首位可能够是 , ,…… ,从第 位开始取数时 每次都要扣除小于左边相邻数的这些数,因此可供选择的数越来越少,累加起来是,。
#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;
}
这里空空如也
有帮助,赞一个