题解 P1066 【2^k进制数】
学无止境
2020-01-21 18:08:17
好像大家都是组合数学推式子啊...
我的方法是 $dp$ / 记忆化搜索 ~~(爱怎么叫怎么叫吧)~~
想法很简单，对于一个 $2^k$ 进制数，令最高位为第一位，以此类推...令$f[ i ][ j ]$ 表示第 $i$ 位取了 $j$ 之后 ，**其后的部分**的方案数。
显然枚举下一位的取值求和就可以得到 $f[i][j]$的值了
> $(1)$ 如果$j$不为$0$ , 那么$f[i][j]={\sum_{j+1≤r≤2^k-1}}(f[i+1][r])$
> $(2)$ 否则 $f[i][j]={\sum_{j≤r≤2^k-1}}(f[i+1][r])$
> $(3)$上面的讨论并不完整，还需要简单特判来满足题目中的第一个要求(详见代码)
这里为了方便我使用了记忆化搜索来进行状态转移，其实用循环也是一样的。
现在来讨论该算法的时空复杂度：
$n≤30000$ ，$2^k ≤256$ ，建立一个$30000×256$ 的数组空间绰绰有余，但是数组里面的数都是高精度数，这样的话空间还足够吗？结论是：足够(本人高精压了 $16$ 位$QwQ$)。
事实上数组的第一维与第二维其实无法同时取到最大 , 事实上最多只有$\frac{n}{k}×2^k$ 个状态 。
每一个状态最多计算一次，计算每一个状态的时间复杂度为$O(2^k)$
理论上时间复杂度是$O(\frac{n}{k}×2^{2k})$ 但是计算每一个状态的时间普遍小于上界，同时有许多状态没有被访问到，因此可以通过本题。
(我不怎么擅长复杂度分析，如果有问题烦请指正)
Code:
```cpp
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<ctime>
#include<algorithm>
#include<cstdlib>
using namespace std;
#define base (10000000000000000ll)
//压位高精 压了16位
struct hp
{
long long a[20];
bool vis;
hp refer(int x)//将x赋值给高精度数
{
memset(a,0,sizeof(a));
a[0]=1,a[1]=x;
return *this;
}
hp operator+(hp q)//加法; 不要忘了处理vis标记
{
hp x;
x.refer(0);
x.vis=(vis||q.vis);
x.a[0]=max(a[0],q.a[0]);
for(register int i=1;i<=x.a[0];i++)
{
if(a[i]+q.a[i]+x.a[i]>=base)
x.a[i+1]++,x.a[i]=a[i]+q.a[i]+x.a[i]-base;
else
x.a[i]=a[i]+q.a[i]+x.a[i];
}
if(x.a[x.a[0]+1])
x.a[0]++;
return x;
}
void print()//输出结果
{
printf("%lld",a[a[0]]);
for(register int i=a[0]-1;i;i--)
printf("%016lld",a[i]);
cout<<endl;
}
}f[30010][256],ans;
int k,w,n,r;
hp dp(int r,int v)//记忆化搜索
{
if(f[r][v].vis)
return f[r][v];
f[r][v].vis=true;
if(v==0&&r>=n-1)//题目中的第一个要求:至少两位
return f[r][v].refer(0);
if(r==n)//边界
return f[r][v].refer(1);
hp tmp;
tmp.refer(0),tmp.vis=true;
int bound=(1<<k)-n+r;
//状态转移
if(v==0)
tmp=tmp+dp(r+1,0);
for(register int i=v+1;i<=bound;i++)
tmp=tmp+dp(r+1,i);
return f[r][v]=tmp;
}
int main()
{
scanf("%d%d",&k,&w);
r=w%k,n=w/k+(r!=0),r=(!r)?k:r;//r 表示首位所能取的位数; n表示总位数
for(register int i=1;i<=n;i++)//f 的初始化; vis表示是否已经被访问
for(register int j=0;j<(1<<k);j++)
f[i][j].refer(0),f[i][j].vis=false;
ans.refer(0);
for(register int i=0;i<(1<<r);i++)
ans=ans+dp(1,i);
ans.print();
return 0;
}
```