一道自动机的小题

题目描述：0和1构成的二进制数，求被3除的余数
改变题目：0和1构成的十进制数，求被3除的余数
（对于改变的题目，可以求1的个数，再%3就行了，这里只是用来和二进制情况做个对比）
题解：

• 假设二进制数表示如下
  $A_{n-1}A_{n-1}A_{n-3}...A_{0}$
• 写成十进制为
  $S=A_{n-1}*2^{n-1}+A_{n-2}*2^{n-2}...+A_{0}$
• 注意这样一个事实
  $m*2^{n}=m*(3-1)^{n}$
  $m*2^{n}\%3=m\%3(n>=0,m->int)$
• 所以对于S前两项之和除以3的余数实际上等于
  $M_{n-2} = (2*A_{n-1}+A_{n-2})\%3$
  $M_{n-2} = (2*M_{n-1}+A_{n-2})\%3$
• 同理，再增加一项$A_{n-2}*2^{n-2}$后前三项的余数为
  $M_{n-3} = (2*M_{n-2}+A_{n-3})\%3$
• 由此得递推公式
  $M_{n} = (2*M_{n-1}+A_{n-1})\%3$
• 所以可得到一个状态机，基于状态机用O(n)的复杂度即可求出原题的解
  

最后，附上一道用自动机能不错地解决的题数的合法字符串表示