IBM Ponder this 2017 February

题面：给一个函数，求多少长度为$42$的字符串输入进去之后返回值不是$0$。

仔细观察这个函数。会发现有一个奇妙的柿子

s = 6+s*(5+s*s*s*(2+s*(3+s))) + b*(5+s*(5+s*(6+s*s*(3+s*6))))

而且这个柿子还与b有关。奥妙重重。

接下来发现只有s%7的值是有用的

然后。。这不就是一个7个点的自动机么

然后考虑r是什么。。会发现就是边(1,1)($s=1$这个节点的字符1的出边)经过次数减去边(0,0)经过次数

问题就变成了。。给出这个自动机，问你多少个输入使得(1,1)经过次数不等于(0,0)经过次数

f[i][j][k]表示长度为i的输入，使得最终s=j且(1,1)经过次数减去(0,0)经过次数等于k的方案数

复杂度$O(42^2\times 7)$

所以就是个普通的傻逼题，做完了

bonus。。有病吧。。