bzoj3329

题目链接

数位dp_bzoj3329

题解

对于这个题有一个特别简单的思路,我觉得比老师上课讲的要简单

我们直接二进制拆分,因为当\(x\)满足x^3x=2x的时候,\(x\)在二进制下一定没有连续的1

所以我们可以根据这个特点.

设\(f[i][j]\)表示有\(i\)位最高位的时候为\(j\)的时候的数字的个数.

我们转移可以直接通过上面的思路来转移.

\[f[i][0]=f[i-1][0]+f[i-1][1]\]

\[f[i][1]=f[i-1][0]\]

初始化f[1][0]=f[1][1]=1就好了.

第二个任务与第一个思路类似,我们构造\(g[i]\)

\[g[i]=g[i-1]+g[i-2]\]

思路就是他填1的时候可以从上一位是0或者是上上一位是1转化而来.

可以发现是一个斐波那契数列,矩阵快速幂优化就好了.


By:Wahacer

2017.1.2

17:00

发表评论

电子邮件地址不会被公开。 必填项已用*标注