传送门：POJ3734
题意：用红黄绿蓝四种色块组成长为n的线段，要求红色和绿色的色块数为偶数，问有多少种组成方法。
思路：我是看着大白上的推出来的矩阵快速幂的公式做的，但是我看discuss里各路大神直接推出了线性公式，根本不用矩阵。。话说生成函数是个什么鬼啊。。要学的东西好多啊。。
想知道具体思路的请自行查阅挑战程序设计第二版，上面分析的很清楚了。
代码：
#include<iostream> #include<algorithm> #include<string.h> #include<vector> using namespace std; const int mod = 10007; typedef long long ll; typedef vector<int> vec; typedef vector<vec> mat;//用二维vector来表示矩阵 mat mul(mat &A,mat &B) { mat C(A.size(),vec(B[0].size())); for(int i=0;i<A.size();i++) for(int k=0;k<B.size();k++) for(int j=0;j<B[0].size();j++) C[i][j]=(C[i][j]+A[i][k]*B[k][j])%mod; return C; } mat poww(mat &A,ll n) { mat B(A.size(),vec(A[0].size())); for(int i=0;i<B.size();i++) B[i][i]=1; while(n) { if(n&1) B=mul(B,A); A=mul(A,A); n>>=1; } return B; } int main() { int T,n; cin>>T; while(T--) { cin>>n; mat A(3,vec(3)); A[0][0]=2;A[0][1]=1;A[0][2]=0; A[1][0]=2;A[1][1]=2;A[1][2]=2; A[2][0]=0;A[2][1]=1;A[2][2]=2; A=poww(A,n); cout<<A[0][0]<<endl; } }写这个题学到了vector套vector当二维数组用的骚方法，这样两个维度都可以动态申请，而不必提前确定好。
