一道自动机的小题
题目描述：0和1构成的二进制数，求被3除的余数
改变题目：0和1构成的十进制数，求被3除的余数
（对于改变的题目，可以求1的个数，再%3就行了，这里只是用来和二进制情况做个对比）
题解：
- 假设二进制数表示如下
An−1An−1An−3...A0 - 写成十进制为
S=An−1∗2n−1+An−2∗2n−2...+A0 - 注意这样一个事实
m∗2n=m∗(3−1)n
m∗2n%3=m%3(n>=0,m−>int) - 所以对于S前两项之和除以3的余数实际上等于
Mn−2=(2∗An−1+An−2)%3
Mn−2=(2∗Mn−1+An−2)%3 - 同理，再增加一项An−2∗2n−2后前三项的余数为
Mn−3=(2∗Mn−2+An−3)%3 - 由此得递推公式
Mn=(2∗Mn−1+An−1)%3 - 所以可得到一个状态机，基于状态机用O(n)的复杂度即可求出原题的解
最后，附上一道用自动机能不错地解决的题数的合法字符串表示