思路一：

考虑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)）这个还是最坏情况。