Project Euler 458

省选前水题做做。。。

一开始想了个搞笑办法。。。
就是状压末尾7个字符中p,r,o,j,e,c,t格子的出现次数。。
总之就是个状态。。
构造个转移矩阵。。算次方后的矩阵就行了。。。
当然这显然过不了。
想了一想发现很明显有很多状态的转移是相同的。。。
然后继续压缩状态。。。
一种比较naive的想法是状态记录为末尾7个字符中p,r,o,j,e,c,t中出现了几种。然后假设出现了i种,下一步只可能转移到i-1种或i种或i+1种。
但是这个转移还是不统一。。。不好描述。
另外一种方法是,对于一个字符串,从尾巴往前取,然后如果有一个字符已经被取出来过,就停下来,记录能取出的字符数为状态。
举个例子就是projeo,从后往前取,第二次碰到o的时候,停下来,这时候已经取出了jeo共3个。而aaa只能取出1个。
那么对于现在状态为i的,往尾巴添的字符有7-i种字符能转移到i+1种的情况,有1种情况转移到i,1种转移到i-1,...
这样子矩阵就很好构造了。
一个7*7的矩阵就够了。

顺便也可以生成函数搞。
这个生成函数是

Comments

comments powered by Disqus