简答题 偏难
#23625

进制数 【问题描述】 设 r 是个 进制数,并满足以下条件: (1)r 至少是个 2 位的 进制数 (2)作为 进制数除最后一位外,r 的每一位严格小于它右边相…

进制数

【问题描述】

设 r 是个 进制数,并满足以下条件:

(1)r 至少是个 2 位的进制数

(2)作为进制数除最后一位外,r 的每一位严格小于它右边相邻的那一位。

(3)将 r 转换为 2 进制数 q 后,则 q 的总位数不超过 w。

在这里,正整数 k(1≤k≤9)和 w(k<w≤30000)是事先给定的。

问:满足上述条件的不同的 r 共有多少个?

我们再从另一角度作些解释:设 S 是长度为 w 的 01 字符串(即字符串 S 由 w 个“0”或“1”组成),S 对应于上述条件(3)中的 q。将 S 从右起划分为若干个长度为 k 的段,每段对应一位进制的数,如果 S 至少可分成 2 段,则 S 所对应的二进制数又可以转换为上述的进制数 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

未登录也能判分,登录后才会记录
答案与解析
正确答案:<p style="text-align: left;">1 #include&lt;iostream&gt;</p><p style="text-align: left;"> 2 using namespace std;</p><p style="text-align: left;"> 3 </p><p style="text-align: left;"> 4 typedef long long LL;</p><p style="text-align: left;"> 5 const int maxn = 1000;</p><p style="text-align: left;"> 6 int C[maxn][maxn][300];</p><p style="text-align: left;"> 7 int ans[300];</p><p style="text-align: left;"> 8 int k,n;</p><p style="text-align: left;"> 9 void add(int *A,int* B,int *C) {</p><p style="text-align: left;">10     int len=max(A[0],B[0]); C[0]=len;</p><p style="text-align: left;">11     for(int i=1;i&lt;=len;i++) {</p><p style="text-align: left;">12         C[i]+=A[i]+B[i];</p><p style="text-align: left;">13         C[i+1]+=C[i]/10;</p><p style="text-align: left;">14         C[i]%=10;</p><p style="text-align: left;">15     }</p><p style="text-align: left;">16     if(C[C[0]+1]) C[0]++;</p><p style="text-align: left;">17 }</p><p style="text-align: left;">18 void add(int* C,int* B) {</p><p style="text-align: left;">19     int len=max(C[0],B[0]); C[0]=len;</p><p style="text-align: left;">20     for(int i=1;i&lt;=len;i++) {</p><p style="text-align: left;">21         C[i]+=B[i];</p><p style="text-align: left;">22         C[i+1]+=C[i]/10;  //+=</p><p style="text-align: left;">23         C[i]%=10;</p><p style="text-align: left;">24     }</p><p style="text-align: left;">25     if(C[C[0]+1]) C[0]++;</p><p style="text-align: left;">26 }</p><p style="text-align: left;">27 </p><p style="text-align: left;">28 int main() {</p><p style="text-align: left;">29     ios::sync_with_stdio(false);</p><p style="text-align: left;">30     cin&gt;&gt;k&gt;&gt;n;</p><p style="text-align: left;">31     int b_max=1&lt;&lt;(k),h_max=1&lt;&lt;(n%k);</p><p style="text-align: left;">32     C[0][0][0]=C[0][0][1]=1;</p><p style="text-align: left;">33     for(int i=1;i&lt;b_max;i++)</p><p style="text-align: left;">34      for(int j=0;j&lt;=i;j++){</p><p style="text-align: left;">35          if(j==0) C[i][j][1]=1;</p><p style="text-align: left;">36          else add(C[i-1][j-1],C[i-1][j],C[i][j]);</p><p style="text-align: left;">37      }</p><p style="text-align: left;">38     for(int i=2;i&lt;=n/k&amp;&amp;i&lt;b_max;i++) add(ans,C[b_max-1][i]);</p><p style="text-align: left;">39     for(int i=1;i&lt;h_max&amp;&amp;n/k+i&lt;b_max;i++) add(ans,C[b_max-i-1][n/k]);</p><p style="text-align: left;">40     for(int i=ans[0];i;i--)  cout&lt;&lt;ans[i];</p><p style="text-align: left;">41     return 0;</p><p style="text-align: left;">42 }</p>
这道题暂未补解析。