题意：
求f(n)=f(n-1)+2*f(n-2)+3*f(n-3)...(n-1)*f(1)+f(0),f(0)=f(1)=1的值。
分析：
转换为f(n)=3*f(n-1)-f(n-2)的二阶递推，用矩阵乘法可以做到logn的复杂度，可是由于测试用例数多和n实在太大，logn也超时。。其实n阶递推在模下是存在循环节的，设循环节=t,y=x+t,则f(x)=f(y),f(x+1)=f(y+1) ==>f(x-1)=f(y-1),所以循环节是从第0项就开始的。那么如何确定循环节t呢，只要从2开始遍历f(n),当f(n)==f(0)且f(n+1)=f(1)就可以了，这题可遍历出最小循环节t=75000。
代码：
//poj 2748
//sep9
#include <iostream>
using namespace std;
const int mod=100000;
const int period=75000;int f[80000];int main()
{int cases;f[0]=f[1]=1;for(int i=2;i<period;++i)f[i]=(3*f[i-1]-f[i-2]+mod)%mod;scanf("%d",&cases);int x;while(cases--){scanf("%d",&x);printf("%d\n",f[x%period]);}return 0;
}