2^k进制数 总时间限制: 10000ms 单个测试点时间限制: 1000ms 内存限制: 65536kB
描述 设r是个2k 进制数，并满足以下条件： （1）r至少是个2位的2k 进制数。 （2）作为2k 进制数，除最后一位外，r的每一位严格小于它右边相邻的那一位。 （3）将r转换为2进制数q后，则q的总位数不超过w。 在这里，正整数k（1≤k≤9）和w（k≤30000）是事先给定的。 问：满足上述条件的不同的r共有多少个？ 我们再从另一角度作些解释：设S是长度为w 的01字符串（即字符串S由w个“0”或“1”组成），S对应于上述条件（3）中的q。将S从右起划分为若干个长度为k 的段，每段对应一位2k进制的数，如果S至少可分成2段，则S所对应的二进制数又可以转换为上述的2k 进制数r。 例：设k=3，w=7。则r是个八进制数（23=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个。
输入 输入文件digital.in只有1行，为两个正整数，用一个空格隔开： k W
输出 输出文件digital.out为1行，是一个正整数，为所求的计算结果，即满足条件的不同的r的个数（用十进制数表示），要求最高位不得为0，各数字之间不得插入数字以外的其他字符（例如空格、换行符、逗号等）。 （提示：作为结果的正整数可能很大，但不会超过200位）
样例输入 3 7
样例输出 36
拿到题后，我们应该首先看看怎么构造一个r。 首先，我们尝试让r的最低位为 2^k，则第二位最大为 2^k - 1… 稍有经验的人就知道，这样做是不行的。我们再来考虑一下，由于题目中说每一位数严格递增，设r的位数为 x，是不是说构造r就等于从1到2^k-1选x个数呢？如果想到这一点，就算是有一个比较确切的思路了。 让我们再来考虑一下细节。
设这个2^k进制数的位数为x，当w/k（整除）>=x时，一定可以知道每一位都可以取[1, 2^k-1]。因为题目要求 r 对应的二进制数的位数 小于等于 w ，所以就可以得到如下代码：
LargeInt ans(0); //初始值为0 int digit=w/k; //最大“满”位数 for(int i=2; i<=digit; i++) //从2开始，到最大 { if(i>(1<<k)-1) break; //如果每一位数都用上后都不能表示i位数，则不用再算了 LargeInt temp; //初始值为1 temp.C(i,(1<<k)-1); //从2^k-1中选i个 ans.add(temp); //加到答案上 }如果k可以整除w，那么现在ans就是答案。如果不能整除呢？这就影响了最后一步的计算。设x=ceil(w/k)，则最高位可以取 1~min(2^k - x, 2^(w%k)-1) （注意x的含义）。我们若设最高位为y的话，答案就是 Σ C(x-1, i) , i>=1 且 i<=2^(w%k) - 1 且 2^k - 1 - i > 0。这句话有点难懂，看代码会更容易些。
if(w%k) { //取最高位可能出现的最大值 int times=std::min((1<<k)-1-digit, (1<<w%k)-1); for(int i=1; i<=times; i++) { LargeInt temp; //这个地方的digit是除开最高位的位数 temp.C(digit, (1<<k)-1-i); //最高位已经是i，后面的还能取2^k-1-i ans.add(temp); } }高精度计算的代码见参考代码
#include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <string> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <deque> #include <map> #include <set> using std::cin; using std::cout; using std::endl; int k,w; struct LargeInt { static const int carry=10000; std::vector<int> num; LargeInt(int x=1): num(1,x) //默认为1 { } void C(int Up, int Down) { int maxi=std::max(Up, Down - Up); for(int i=maxi+1; i<=Down; i++) { mul(i); } for(int i=2; i<=Down-maxi; i++) { div(i); } } void print() { printf("%d",num[num.size()-1]); for(int i=num.size()-2; i>=0; i--) { printf("d",num[i]); } puts(""); } void add(const LargeInt &b) { if(num.size()<b.num.size()) num.resize(b.num.size()); for(int i=0; i<b.num.size(); i++) { num[i]+=b.num[i]; } for(int i=0; i<num.size(); i++) { if(num[i]>carry) { if(i+1>=num.size()) num.push_back(0); num[i+1]+=num[i]/carry; num[i]%=carry; } } } void div(int x) { int mod=0; int quo=0; for(int i=num.size()-1; i>=0; i--) { num[i]+=mod*carry; quo=num[i]/x; mod=num[i]%x; num[i]=quo; } while(num.size() && !num[num.size()-1]) num.pop_back(); } void mul(int x) { for(int i=0; i<num.size(); i++) { num[i]*=x; //x最大512，不会溢出 } for(int i=0; i<num.size(); i++) { if(num[i]>carry) { if(i+1>=num.size()) num.push_back(0); num[i+1]+=num[i]/carry; num[i]%=carry; } } } }; namespace Regular { void run() { LargeInt ans(0); int digit=w/k; for(int i=2; i<=digit; i++) { if(i>(1<<k)-1) break; LargeInt temp; temp.C(i,(1<<k)-1); ans.add(temp); } if(w%k) { int times=std::min((1<<k)-1-digit, (1<<w%k)-1); for(int i=1; i<=times; i++) { LargeInt temp; temp.C(digit, (1<<k)-1-i); ans.add(temp); } } ans.print(); } void input() { scanf("%d%d",&k,&w); } } int main() { Regular::input(); Regular::run(); return 0; }