題目鏈接：[點擊打開鏈接](http://poj.org/problem?id=3734) 題意：個n個方塊涂色， 只能涂紅黃藍綠四種顏色，求最終紅色和綠色都為偶數的方案數。 該題我們可以想到一個遞推式 。 ? 設a[i]表示到第i個方塊為止紅綠是偶數的方案數， b[i]為紅綠恰有一個是偶數的方案數， c[i]表示紅綠都是奇數的方案數。 那么有如下遞推可能： 遞推a[i+1]：1.到第i個為止都是偶數，且第i+1個染成藍或黃；2.到第i個為止紅綠恰有一個是奇數，并且第i+1個方塊染成了奇數對應的顏色。 遞推b[i+1]：1.到第i個為止都是偶數，且第i+1個染成紅或綠；2.到第i個為止紅綠恰有一個是奇數，并且第i+1個方塊染成了藍或黃；3.到第i個方塊為止紅火綠都是奇數，并且第i+1個染成紅火綠。 遞推c[i+1]：1.到第i個為止紅綠恰有一個是奇數， 并且第i+1個方塊染成偶數對應的顏色；2.到第i個為止紅綠都是奇數，并且第i+1個方塊染成藍或黃。 即a[i+1] = 2*a[i] + b[i]; ? ? b[i+1] = 2*a[i] + 2*b[i] + 2*c[i]; ? ? c[i+1] = b[i] + 2*c[i]; 因為DP的過程中，每一步都是在重復上一個過程， 所以可以用矩陣相乘來優化算法。 將上述遞推式寫成矩陣相乘的形式： { a[i] } ? ? ?{2 ?1 ?0}^i{a[0] } { b[i] } ?= {2 ?2 ?2} ? {b[0] } { c[i] } ? ? {0 ?1 ?2} ? {c[0] } 然后用矩陣快速冪就可以了。 細節參見代碼： ~~~ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int INF = 1000000000; const int mod = 10007; const int maxn = 100; ll T,n,m; typedef vector<int> vec; typedef vector<vec> mat; mat mul(mat &a, mat &b) { mat c(a.size(), vec(a[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 pow(mat a, ll n) { mat b(a.size(), vec(a[0].size())); for(int i = 0; i < a.size(); i++) { b[i][i] = 1; } while(n > 0) { if(n & 1) b = mul(b, a); a = mul(a, a); n >>= 1; } return b; } int main() { scanf("%d",&T); mat a(3, vec(3)); while(T--) { scanf("%lld",&n); 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 = pow(a, n); printf("%d\n",a[0][0]); } return 0; } ~~~