当前位置: 代码迷 >> 综合 >> poj 2440 DNA 递推在模下存在循环节
  详细解决方案

poj 2440 DNA 递推在模下存在循环节

热度:98   发布时间:2024-01-19 05:23:24.0

题意和分析:

       题意都是废话,用动态规划列个方程化下简,最后也是这题有意思的地方是求a(n)=a(n-1)+a(n-3)+a(n-4) 在模2005下的值。

       你可能会说,这个简单啊,弄个数组,搞个for循环就行啊,没错,但这是O(n)。能快点么?

       嗯,那用矩阵相乘表示递推,在矩阵乘法结合律的保证下幂运算加速足够快了吧?嗯,是快不少,但这是O(logn),还不够快。

       这题就是这么狠,要O(1)的算法,求a(n)=a(n-1)+a(n-3)+a(n-4) 在模2005下的值。

       如果递推阶数K固定模M固定,那么K阶递推在模M下是存在循环节的,假设循环节为t,a(t+n)=a(n),令n=0得a[t]=a[0],这题的a[0]是1,我们搞个辅助程序从i=K开始求a[i],当a[i]=a[0]=1时,我们的i就是循环节t,那么不管n是啥我们输出a[n%t]就可以了,这题t试出来是200,所以代码:

//poj 2440
//sep9
#include <iostream>
using namespace std;int main()
{int a[256]={1,2,4,6},n;for(int i=4;i<200;++i)a[i]=(a[i-1]+a[i-3]+a[i-4])%2005;while(scanf("%d",&n)==1)printf("%d\n",a[n%200]);	return 0;	
}

========================休息&发呆分割线========================================================

    那么,关键的问题来了,你质疑么?为什么 如果递推阶数K固定模M固定,那么K阶递推在模M下是存在循环节的?

    

  因为阶数K固定,任意的a[n]只与a[n-k],[n-k+1]....a[n-1]有关,而因为模M固定,a[n-k],[n-k+1]....a[n-1]总共的状态数固定小于M^K,M^K是个定值,也就是说在最极限情况下,a[n+M^k]=a[n],故存在循环节t使得a[n+t]=a[n],t<M^k。

   这个循环节问题以前遇到这种恶心的题就想不明白,今天不知道为啥突然想清楚了-。-,好像也很简单的样子。