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 }
...