Problem J. Wiki with 35
Input file: standard input Time limit: 1 second
Output file: standard output Memory limit: 256 megabytes
从前，有一对夫妻生了五胞胎，这对夫妻为了让这五兄弟比较容易让老师记得，分别给他们取名"1"、
"3"、 "5"、 "7"、 "9"。而"3"和"5"这两兄弟异常的聪明！
有一天， Wiki老师为了考验"3"和"5"两兄弟的智力和默契程度，出了一道这样的题目：
现在有n个连续的方格，需要他们俩往里面写上五兄弟的名字（也就是1、 3、 5、 7、 9）， 要求这n个方格
需要填满，且只能填上他们五兄弟的名字，题目需要保证这俩兄弟的名字出现的次数一个是奇数次，一
个是偶数次，问，一共有多少种可能性？（比如说有1个方格，那么兄弟两个可以填入3或者5，一共有2种
可能性）
Input
有多个测试数据输入，每行一个正整数n(1 <= n <= 109)，表示连续方格的个数
输入n = 0时结束
Output
每输出一个答案换一行（答案可能很大，需要对109 + 7取模）
Sample

standard input	standard output
1 2 0	2 12

思路：

动态规划，计算方法：矩阵快速幂

状态转移方程：（一奇一偶为满足要求的状态）

f[i][0] = 3f[i-1][0] + 2f[i-1][1] ;不满足要求的状态

f[i][1] = 2f[i-1][0] + 3f[i-1][1] ;满足要求的状态

 

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 
 5 using namespace std ;
 6 
 7 /*
 8     3 2
 9     2 3
10 */
11 
12 const int mod = 1e9 + 7 ;
13 typedef unsigned long long ULL ;
14 
15 struct node{
16     ULL m[2][2] ;
17 };
18 ULL dp[2] ;
19 int m ;
20 
21 
22 node mul(node p,node q){
23     node tmp ;
24     memset(tmp.m,0,sizeof tmp.m) ;
25     for(int i=0;i<2;i++){
26         for(int j=0;j<2;j++){
27             for(int k=0;k<2;k++){
28                 tmp.m[i][j] = (tmp.m[i][j] + p.m[i][k] * q.m[k][j]) % mod ;
29             }
30         }
31     }
32     return tmp ;
33 }
34 
35 node qmi(node q,int k){
36     node base ;
37     memset(base.m,0,sizeof base.m) ;
38     for(int i=0;i<2;i++){
39         base.m[i][i] = 1 ;
40     }
41     while(k){
42         if(k&1){
43             base = mul(base,q) ;
44         }
45         q = mul(q,q) ;
46         k >>= 1 ;
47     }
48     return base ;
49 }
50 
51 int main(){
52     while(cin >> m, m){
53         node a,b ;
54         memset(a.m,0,sizeof a.m) ;
55         memset(b.m,0,sizeof b.m) ;
56         a.m[0][0] = a.m[1][1] = 3 ;
57         a.m[0][1] = a.m[1][0] = 2 ;
58         dp[0] = 1,dp[1] = 0 ;
59         b = qmi(a,m) ;
60         ULL ans = 0 ;
61         for(int i=0;i<2;i++){
62             ans += (dp[i] * b.m[1][i]) % mod ;
63         }
64         cout << ans << endl ;
65     }
66     
67     
68     return 0 ;
69 }

 

 

...