hdu2604 Queuing

只要能找到递推公式就可以马上切掉这题。

 

设f(n)为字符串长度为n时复合条件的字符串个数，以字符串最后一个字符为分界点，当最后一个字符为m时前n-1个字符没有限制，即为f(n-1)；当最后一个字符为f时就必须去除最后3个字符是fmf和fff的情况,在考虑最后两个字符为mf和ff的情况，显然不行；最后3个字符为fmf、mmf和fff、mff时只有当最后3个字符为mmf时前n-3个字符没有限制，即为f(n-3)，当为mff时第n-3个字符可能为f因而对前n-3个字符串有限制；最后4个字符为fmff和mmff时mmff可行。这样就讨论完了字符串的构成情况，得出结论：

f(n)=f(n-1)+f(n-3)+f(n-4)

然后就像fibonacci那样构建矩阵用快速幂取模。。。

 

 

上面讨论字符串的构成有点麻烦，可以直接用trie图搞定，由字符串fmf和fff构建trie图：

 

 

假定根节点为字符串的最后一个字符，由根结点到根节点的回路有m、fmm、ffmm，注意这是从一个字符串的后面向前走这些字符到达另一个字符串，恰好和上面的扩展递推相一致。。。