洛谷P1066 2^k进制数（题解）（递推版）

https://www.luogu.org/problemnew/show/P1066（题目传送）

(题解）https://www.luogu.org/problemnew/solution/P1066；

首先普及一下知识：一个2^k进制n位数转换成2进制数时最多有n*k位；一个n进制数的每位数字属于集合{0,1，……，n-1}。

这样我们就知道给出w、k后r的位数最多为wei=w/k向上取整，但要注意，如果w%k有余，则r在最高位上不能把集合{0,1，……，n-1}的数都取一遍。

又知道r的位数可以是2到wei的任意一个数，且r的位数为i时的状态又可以从r的位数为i-1推过来：

　　设数组a[i][j]表示r的位数为i、第i位为j时所有符合条件r的数目，则a[i][j]=a[i-1][j+1]+……+a[i-1][2^k-1]。

由此我们可以从r的位数为2时一直推至r的位数为wei。最后别忘了最高位的特殊处理。

AC代码：

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 int a[4][512][201],tot[201],mmax;
 6 int pow(int a,int b)
 7 {
 8     int ans=1,with=a;
 9     while(b)
10     {
11         if(b&1) ans*=with;
12         with*=with;
13         b>>=1;
14     }
15     return ans;
16 }
17 void jiafa(int j[],int a[])
18 {
19     int lb=1;
20     while(lb<=j[0]||lb<=a[0])
21     {
22         j[lb]+=a[lb];
23         if(j[lb]>=10) 
24         {
25             j[lb]%=10;
26             j[lb+1]++;
27         }
28         lb++;
29     }
30     while(j[lb]>=10) 
31     {
32         j[lb]%=10;
33         lb++;
34         j[lb]++;
35     }
36     while(!j[lb]&&lb>0) lb--;
37     if(lb>j[0]) j[0]=lb;
38 }
39 void jiafa1(int a[],int b)
40 {
41     int lb=0;
42     while(b)
43     {
44         a[++lb]=b%10;
45         b/=10;
46     }
47     a[0]=lb;
48     jiafa(tot,a);
49 }
50 int main()
51 {
52     int k,w;
53     cin>>k>>w;
54     int g=w/k;
55     bool youyu=0;
56     int mmax2;
57     if(w%k)
58     {
59         g++;
60         youyu=1;
61         mmax2=pow(2,w%k)-1;
62     } 
63     mmax=pow(2,k)-1;
64     for(int i=1;i<mmax;i++) jiafa1(a[0][i],mmax-i);
65     int l=0,n=1;
66     for(int i=3;i<=g;i++)
67     {
68         if(i==g&&youyu&&mmax2<mmax)
69         {
70             for(int i=mmax-1;i>mmax2;i--)
71                 jiafa(a[n][mmax2],a[l][i]);
72             jiafa(tot,a[n][mmax2]);
73             for(int j=mmax2-1;j>=1;j--)
74             {
75                 memcpy(a[n][j],a[n][j+1],sizeof(a[n][j+1]));
76                 jiafa(a[n][j],a[l][j+1]);
77                 jiafa(tot,a[n][j]);
78             }
79             break;
80         } 
81         jiafa(a[n][mmax-1],a[l][mmax]);
82         jiafa(tot,a[n][mmax-1]);
83         for(int j=mmax-2;j>=1;j--)
84         {
85             memcpy(a[n][j],a[n][j+1],sizeof(a[n][j+1]));
86             jiafa(a[n][j],a[l][j+1]);
87             jiafa(tot,a[n][j]);
88         }
89         for(int j=1;j<=mmax;j++)
90         memset(a[l][j],0,sizeof(a[l][j]));
91         n++;l++;
92         if(n==3) n=0;
93         if(l==3) l=0;
94     }
95     int lt=tot[0];
96     while(!tot[lt]&&lt>1) lt--;
97     for(;lt>0;lt--) cout<<tot[lt];
98     return 0;
99 }