fzyzojP1876 天津——泥人张

fzyzojP1876  天津——泥人张

fzyzojP1876  天津——泥人张

思路一:

考虑lucas定理,mod 4意义下,每一个组合数都不能是0

所以,把n变成四进制数,然后数位dp即可

f[i][0/1][0/1/2/3]表示,前i位,有没有限制,mod 4 的值是0/1/2/3

发现,4=2^2,所以如果出现一个0或者两个2都可以

所以,简化一下:f[i][0/1][0/1/2]表示,前i位,有没有限制,2的次幂出现了0,1,2次,(来一个0直接相当于出现2个2)

最后答案是:f[len][0/1][2]

len大概不到5000

但是dp要高精(可以压18位)

原来的n也可以压位(压18位也可以的)

复杂度:O(3000/18*len+5000*2*3*3000/18)这个是极限

有一定的常数

卡一卡应该能过。

大错特错,4不是质数,不能用LUCAS定理

思路二:

上面那个太暴力~~~

这个复杂度很低了:

fzyzojP1876  天津——泥人张

fzyzojP1876  天津——泥人张

fzyzojP1876  天津——泥人张

fzyzojP1876  天津——泥人张

瓶颈是2^(s(m))

压位高精的话,再用上高精快速幂,s(m)极限是10000大概(也就是len)

总复杂度:O(300*300*log(10000))这个还是最坏情况。

上一篇:ASP.NET MVC 自定义路由中几个需要注意的小细节


下一篇:Redis学习笔记一:基本安装和配置