1649：【例 2】2^k 进制数
时间限制: 1000 ms 内存限制: 524288 KB
【题目描述】
原题来自：NOIP 2006 提高组
设 r 是个 2 进制数，并满足以下条件：
1、r 至少是个 2 位的 2 进制数。
2、作为 2 进制数，除最后一位外，r 的每一位严格小于它右边相邻的那一位。
3、将 r 转换为 2 进制数 q 后，q 的总位数不超过 w。
在这里，正整数 k 和 w 是事先给定的。
问：满足上述条件的不同的 r 共多少个？
【输入】
输入只一行，为两个正整数 k 和 w。
【输出】
输出为一行，是一个正整数，为所求的计算结果，即满足条件的不同的 rr 的个数（用十进制数表示，要求最高位不得为 0，各数字之间不得插入数字以外的其他字符（例如空格、换行符、逗号等）。
提示：作为结果的正整数可能很大，但不会超过 200 位。
【输入样例】
3 7
【输出样例】
36
【提示】
数据范围与提示：
对于所有数据，1≤k≤9,k<w≤3×10 。
sol：这道其实是道大水题
对于条件二很容易发现是个组合数，而且是严格小于，k的范围也不大，直接n预处理组合数
统计答案是注意讨论首位是0和非0的情况
Ps：裸的高精貌似会MLE，建议压位
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
inline ll read()
{
ll s=;
bool f=;
char ch=' ';
while(!isdigit(ch))
{
f|=(ch=='-'); ch=getchar();
}
while(isdigit(ch))
{
s=(s<<)+(s<<)+(ch^); ch=getchar();
}
return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
if(x<)
{
putchar('-'); x=-x;
}
if(x<)
{
putchar(x+''); return;
}
write(x/);
putchar((x%)+'');
return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('\n')
const int Base=,power=;
int K,B,W;
struct Bignum
{
int a[];
Bignum(){memset(a,,sizeof a);}
Bignum(int x)
{
memset(a,,sizeof a);
while(x)
{
a[++a[]]=x%Base;
x/=Base;
}
return;
}
inline void print()
{
int i;
write(a[a[]]);
for(i=a[]-;i>=;i--)
{
if(a[i]<) putchar('');
if(a[i]<) putchar('');
if(a[i]<) putchar('');
write(a[i]);
}
return;
}
}C[][],ans;
#define P(x) x.print(),putchar(' ')
#define Pl(x) x.print(),putchar('\n')
inline Bignum operator+(const Bignum &p,const Bignum &q)
{
int i;
Bignum ans=p;
for(i=;i<=q.a[];i++)
{
ans.a[i]+=q.a[i];
ans.a[i+]+=ans.a[i]/Base;
ans.a[i]-=(ans.a[i]>=Base)?Base:;
}
while(ans.a[ans.a[]+]) ans.a[]++;
return ans;
}
int main()
{
int i,j;
R(K); R(W);
B=<<K;
C[][]=Bignum();
for(i=;i<=B;i++)
{
for(j=;j<=B;j++)
{
C[i][j]=C[i][j]+C[i-][j];
if(j) C[i][j]=C[i][j]+C[i-][j-];
}
}
int oo=W%K,Up=W/K;
for(i=min(Up,B-);i>=;i--)
{
ans=ans+C[B-][i];
}
if(oo)
{
int Last=(<<oo)-;
for(i=;i<=Last;i++) if((B-i-)>=Up)
{
ans=ans+C[B-i-][Up];
}
Pl(ans);
}
else
{
Pl(ans);
}
return ;
}
/*
input
3 7
output
36 input
2 8
output
4
*/