NC50586. 2^k 进制数
描述
输入描述
输入只一行，为两个正整数k和w。
输出描述
输出为一行，是一个正整数，为所求的计算结果，即满足条件的不同的r的个数（用十进制数表示，要求最高位不得为0，各数字之间不得插入数字以外的其他字符（例如空格、换行符、逗号等）。
提示：作为结果的正整数可能很大，但不会超过200位。
示例1
输入:
3 7
输出:
36
C++14(g++5.4) 解法, 执行用时: 5ms, 内存消耗: 480K, 提交时间: 2020-08-13 16:31:19
#include<cstdio>
#include<algorithm>
#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;
scanf("%d%d",&k,&w);
if(w<=k){printf("0\n");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--)printf("%d",ans[i]);
printf("\n");
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 9ms, 内存消耗: 580K, 提交时间: 2020-06-02 20:06:02
#include<cstdio>
#include<algorithm>
#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;
scanf("%d%d",&k,&w);
if(w<=k)
{
printf("0\n");
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--)
printf("%d",ans[i]);
printf("\n");
return 0;
}
Python3(3.9) 解法, 执行用时: 115ms, 内存消耗: 14248K, 提交时间: 2021-05-10 20:58:37
C=[[0 for j in range(i+1)]for i in range(515)]
def pre():
for i in range(1,513):
C[i][0]=C[i][i]=1
for i in range(1,513):
for j in range(1,i):
C[i][j]=C[i-1][j]+C[i-1][j-1]
if __name__=="__main__":
pre()
k,w=map(int,input().split(' '))
a=int(w/k)
b=w%k
ans=0
for i in range(1,2**b+1):
## print(2**k-i,a)
if a<=2**k-i:
ans+=C[2**k-i][a]
for i in range(2,a):
## print(2**k-1,i)
if i <=2**k-1:
ans+=C[2**k-1][i]
print(ans)