这道题真好，体现了思想的灵活性。要3个连续状态以上嘛，好，那我就求出
只有1~2个状态的数量，最后总数减去即可。美妙，完结。
/* *State: 3519 0MS 256K 2354 B *题目大意： * 给定n个硬币，硬币有两种状态0或1，可以翻转，总共有2^n种 * 状态，规定如果有连续3个硬币的状态一样，即是特殊串。要求 * 特殊串的个数。 *解题思路： * 已知总数目，那么可以用相反的思想求出该串状态不含有3个 * 连续一样的数目，然后用总数去减。 * 长度为 n 的 01 串一共有 2^n 种不同的排列方法 , * 设 f(n) 为长度是 n 的不包含连续 3 个或以上相同的 1 或 0 的 01 串 , * 则 f(1)=2,f(2)=4,f(3)=6,f(4)=10 * 当 n>4 的时候 , 分情况考虑 : * 1、 如果是以 00 或者 11 结尾 , 则分别有 f(n-2)/2 种情况 , * 加起来就是 f(n-2) 种 . * 2、 如果是以 01 或者 10 结尾 , 则第 n 个字符要和第 n-1 个 * 字符不一样 , 那么分别有 f(n-1)/2 种 , 加起来就是 f(n-1) * 则统计起来就是 f(n)=f(n-1)+f(n-2)。之后构造矩阵即可。 *解题感想： * 这道题目是搜题解的，表示做法其实也就一般，关键看能否想到用反推，还有 * 公式。 * 由于最后有一步减法，由于是模的关系，有可能结果为负，注意模减法的特殊性。 * 由于这个错误贡献了两个wa,还查了半个小时不止。最后还好乱给出测试数据了嘻。 */
View Code
1 #include <iostream> 2 #include <cmath> 3 #define maxn 3 4 5 using namespace std; 6 7 struct Mat 8 { 9 int m, n; 10 int d[maxn][maxn]; 11 void init(int m, int n) 12 { 13 this->m = m; 14 this->n = n; 15 memset(d, 0, sizeof(d)); 16 } 17 void initE(int size) //生成单位阵 18 { 19 m = n = size; 20 for(int i = 0; i < n; i ++) 21 { 22 for(int j = 0; j < n; j ++) 23 { 24 d[i][j] = i==j; 25 } 26 } 27 } 28 Mat operator * (const Mat & mat) const 29 { 30 static Mat res; 31 res.init(m, mat.n); 32 for(int i = 0; i < res.m; i ++) 33 { 34 for(int k = 0; k < n; k ++) 35 { 36 if(d[i][k]==0) continue; 37 for(int j = 0; j < res.n; j ++) 38 { 39 res.d[i][j] += d[i][k] * mat.d[k][j]; 40 } 41 } 42 } 43 return res; 44 } 45 Mat mul_mod(const Mat & mat, int mod) const 46 { 47 static Mat res; 48 res.init(m, mat.n); 49 for(int i = 0; i < res.m; i ++) 50 { 51 for(int k = 0; k < n; k ++) 52 { 53 if(d[i][k]==0) continue; 54 for(int j = 0; j < res.n; j ++) 55 { 56 res.d[i][j]=(res.d[i][j]+d[i][k]*mat.d[k][j]) % mod; 57 } 58 } 59 } 60 return res; 61 } 62 void pow_mod(int k, int mod) //this = this^k % mod; 63 { 64 static Mat a; 65 a = *this; 66 for(this->initE(n); k; k>>=1, a=a.mul_mod(a, mod)) 67 if(k&1) *this=this->mul_mod(a, mod); 68 } 69 void view_arr() 70 { 71 for(int i = 0; i < m; i++) 72 { 73 for(int j = 0; j < n; j++) 74 cout << d[i][j] << " "; 75 cout << endl; 76 } 77 } 78 }; 79 80 int mod_pow(int a,int k,int m) 81 { 82 static int r; 83 for(r=1;k;k>>=1,a=a*a%m) if(k&1) r=r*a%m; 84 return r; 85 } 86 87 int main(void) 88 { 89 #ifndef ONLINE_JUDGE 90 freopen("in.txt", "r", stdin); 91 #endif 92 int n, mod; 93 94 mod = 10007; 95 96 while(scanf("%d", &n) == 1) 97 { 98 Mat a; 99 a.init(2, 2); 100 a.d[0][0] = a.d[0][1] = a.d[1][0] = 1; 101 a.d[1][1] = 0; 102 if(n == 1 || n == 2) 103 { 104 printf("0\n"); 105 continue; 106 } 107 a.pow_mod(n - 2, mod); 108 int tol = mod_pow(2, n, mod); 109 int fn = (a.d[0][0] * 4 + a.d[0][1] * 2) % mod; 110 //cout << "fn: " << fn << endl; 111 //cout << tol << endl;0 112 printf("%d\n", ((tol - fn) % mod + mod) % mod); 113 } 114 return 0; 115 }