题解 P4461 【[CQOI2018]九连环】
WinXP
2018-05-23 22:19:55
#啊
~~我一定要写这篇题解祭奠我逝去的一下午~~
拿到这题，乍一看是一个 $dp$ 题。也的确是一个 $dp$，而且非常水。
根据题中关于 $4$ 连环的解释，你可以发现 $4$ 连环的拆卸就是这样的一个规律：
$1$ : 拆 $2$ 连坏使其变为 $1100$ ；
$2$ : 拿掉最左面的 $1$ ;
$3$ : 加 $2$ 连环使其变为 $0111$ ；
$4$ : 拆 $3$ 连环。
仔细观察，两条规则中都是"任意装上或卸下。"那么可想而知装 $x$ 连环与卸 $x$ 连环都是同样的步数。
所以设 $dp(x)$ 表示 $x$ 连环拆卸的次数，~~这题已经结束了。~~（才怪)
$$dp(4)=dp(2) + 1 + dp(2) + dp(3)$$
$dp(n)=dp(n-2)$ (拆 $(n-2)$ 连环变成 $110000...$ ）$+$ $1$ ( $010000...$ )
$+$ $dp(n-2)$ (装 $(n-2)$ 连环变成 $011111...$ ) $+$ $dp(n-1)$ (拆 $(n-1)$ 连环)。
$$dp(n)=2dp(n-2)+dp(n-1)+1$$
于是我兴致冲冲地打了一发递推交上去30分。
然后我发现了一个问题：没有取膜？
没有取膜。我说怎么那么水。
于是我陷入了沉思。
。
沉思之中顺手打了个表：
$1$ $2$ $5$ $10$ $21$ $42$ $85$ $170...$
发现一个问题。每一项约等于前一项的 $2$ 倍。仔细分析，发现
$$dp(n)=2dp(n-1)+ (n\&1)?1:0$$
既然是 $2$ 倍，为什么不打一下 $2$ 进制表示呢？
$1$ $10$ $101$ $1010$ $10101$ $101010$ $1010101......$
有点意思。
其实也很容易能从 $dp$ 中发现这个规律，每当 $n$ 为奇数时$++$，就会使每隔 $1$ 位 $+1$ 。
这也不太好办。$n=1e5$ 时，这个 $2$ 进制数就有 $1e5$ 位。$10$ 进制的高精位数只知道比 $1e5$ 小却没有办法确定。隔一位一个 $1$ 也不方便化成 $10$ 进制啊。不过好像没有什么好办法能直接从 $2$ 进制的高精转化为 $10$ 进制的高精。(仅为思考过程)
能不能直接从 $10$ 进制的高精推过来呢？
如果是二进制表示是 $1000000....$ ，它就可以轻松地表示为 $2^n$ 然后用快速幂做了。
那么现在考虑对这个 $2$ 进制数 $×3$ 。哦不对，是 $11$ 。我们来看变成了什么。。
$11$ $110$ $1111$ $11110$ $111111$ $1111110 ......$
这就可以说是非常显然了吧。( $+1$ 或 $+2$ 变成 $10000...$ )
写出来也就是其他题解中大佬们的公式。只不过我用了这种另类思路得到。
可是有一个问题。 多项式乘法是 $n^2$ 的。即便有快速幂，它的复杂度也是 $n^2logn$ 的。
那么就写一个 $FFT$ 加速一下多项式乘法就行啦！
然后你要感谢你看到了这篇题解。如果你是那种对复杂度要求严格，认为复杂度决定一切和是否$AC$的选手，你可以少写一个$FFT$。
$n^2logn$ 中 $n^2$ 的 $n$ 是什么？是数据位数。
首先当 $n$ 为 $1e5$ 时你的 $2$ 进制数是 $1e5$ 位的。如果它变成 $10$ 进制，可以变成 $Xe4$ 级别。如果再对它压一下位直接 $1e8$ 进制，它可以变成 $Xe3$ 级别。复杂度瞬间变成$O($可过$)$。
实际上当 $n=1e5$ 时最后的答案压位后只有 $3762$ 位。
而且另外一点，普通的相乘常数可是比 $FFT$ 小了不止几倍。也就是说如果你用了 $FFT$ 去"优化"它，你反而会更慢。
$FFT$ + 小数相乘时暴力的优化 $=$ $132ms$
压位爆乘 + 输出优化 + 开小内存 $=$ $8ms$
伤感的故事。
```
#include <bits/stdc++.h>
#define rap(i,s,n) for(int i=s;i<=n;i++)
#define drap(i,n,s) for(int i=n;i>=s;i--)
#define N 5111
#define Q 100000000
#define ll long long
#define m(s,k) memset(s,k,sizeof s)
char xA[1<<16],xZ[20]; int xC=-1,xzz=0;
inline void wt_z(){fwrite(xA,1,xC+1,stdout),xC=-1;}
template<class T>inline void wt(T x,int t){
if(xC>(1<<15)) wt_z();
while(xZ[++xzz]=(char)(x%10+'0'),(x/=10)||(t>0)) --t;
while(xA[++xC]=xZ[xzz],--xzz);
}
//得益于luogu的代码公开计划我可以愉快地抄大佬的快输板子了（不算抄袭吧QAQ）
using namespace std;
ll res[N],a[N],d[N];
int sz1,sz2;
int cheng(ll *a,int n,ll *b,int m){
m(d,0); rap(i,0,n) rap(j,0,m) d[i+j]+=a[i]*b[j];
rap(i,0,n+m) d[i+1]+=d[i]/Q,d[i]%=Q;
int t=n+m+1; while(d[t]) d[t+1]+=d[t]/Q,d[t]%=Q,t++; t--;
rap(i,0,t) a[i]=d[i]; return t;
}
//非常暴力又写的不是一般难看的乘
int main(){
int n,m; scanf("%d",&m); rap(i,1,m){
scanf("%d",&n); int t=n+1;
m(res,0); res[0]=1; m(a,0); a[0]=2; sz1=sz2=0;
while(t){
if(t&1) sz1=cheng(res,sz1,a,sz2); t>>=1;
if(t) sz2=cheng(a,sz2,a,sz2);
}
if(n&1) res[0]++; res[0]-=2; if(res[0]<0) res[0]+=Q,res[1]--;
ll k=0; drap(i,sz1,0){k=k*Q+res[i]; res[i]=k/3; k%=3;}
while(res[sz1]==0) sz1--;
wt(res[sz1],0); drap(i,sz1-1,0) wt(res[i],7); xA[++xC]='\n'; wt_z();
}
return 0;
}
```
~~当我知道暴力可以过，而且快的飞起的时候，我就好像看到了岩浆里燃烧的钻石，就好像看到了3滴血跑路的盖伦,就好像看到了我被一个就是破不了防的血条里只剩下真空的妖梦反杀。~~
~~别和我提python.~~