思路一:
考虑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定理
思路二:
上面那个太暴力~~~
这个复杂度很低了:
瓶颈是2^(s(m))
压位高精的话,再用上高精快速幂,s(m)极限是10000大概(也就是len)
总复杂度:O(300*300*log(10000))这个还是最坏情况。