题意：给你4*n的矩形，用1*2的方格铺满。
题解：经典问题，我们可以先用公式找出前几项，然后求递推式即可，但是n很大，所以要快速幂搞搞。
我们可以由前几项推得递推公式为：f[i]=f[i-1]+5*f[i-2]+f[i-3]-f[i-4];
因此我们可以构造矩阵为：
1 5 1 -1
1 0 0 0
0 1 0 0
0 0 1 0 然后矩阵快速幂求解就好啦。
附带公式代码：
#include<set> #include<map> #include<stack> #include<queue> #include<vector> #include<string> #include<math.h> #include<stdio.h> #include<iostream> #include<string.h> #include<stdlib.h> #include<algorithm> #include<functional> using namespace std; typedef long long ll; #define inf 1000000000 #define mod 1000000007 #define maxn 2600005 #define PI acos(-1.0) #define lowbit(x) (x&-x) #define eps 1e-9 struct node { ll a[5][5]; }a, b; int main(void) { double n, m, i, j, sum; while (scanf("%lf", &m) != EOF) { sum = 1;n = 4; for (i = 1;i <= (m + 1) / 2;i++) for (j = 1;j <= (n + 1) / 2;j++) sum *= 4 * cos(PI*i / (m + 1))*cos(PI*i / (m + 1)) + 4 * cos(PI*j / (n + 1)) * cos(PI*j / (n + 1)); printf("%.0f\n", sum); } return 0; } AC代码：
#include<set> #include<map> #include<stack> #include<queue> #include<vector> #include<string> #include<math.h> #include<stdio.h> #include<iostream> #include<string.h> #include<stdlib.h> #include<algorithm> #include<functional> using namespace std; typedef long long ll; #define inf 1000000000 #define mod 1000000007 #define maxn 2600005 #define PI acos(-1.0) #define lowbit(x) (x&-x) #define eps 1e-9 struct node { ll a[5][5]; }a, b; ll c[10]; void init() { int i, j; c[1] = 1;c[2] = 5; c[3] = 11;c[4] = 36; b.a[1][1] = 1;b.a[1][2] = 5;b.a[1][3] = 1;b.a[1][4] = -1; for (i = 2;i <= 4;i++) { for (j = 1;j <= 4;j++) { if (i - j == 1) b.a[i][j] = 1; else b.a[i][j] = 0; } } } node qq(node a, node b) { node c; int i, j, k; for (i = 1;i <= 4;i++) for (j = 1;j <= 4;j++) { c.a[i][j] = 0; for (k = 1;k <= 4;k++) { a.a[i][k] %= mod; b.a[k][j] %= mod; c.a[i][j] += a.a[i][k] * b.a[k][j]; c.a[i][j] %= mod; } } return c; } node q(node a, ll y) { node tmp; int i, j; for (i = 1;i <= 4;i++) for (j = 1;j <= 4;j++) { if (i == j) tmp.a[i][j] = 1; else tmp.a[i][j] = 0; } while (y) { if (y % 2) tmp = qq(tmp, a); a = qq(a, a); y /= 2; } return tmp; } int main(void) { init(); ll n, i, j, ans; while (scanf("%lld", &n) != EOF) { ans = 0; if (n <= 4) { printf("%lld\n", c[n]); continue; } a = q(b, n - 4); for (i = 1;i <= 4;i++) { a.a[1][4 - i + 1] %= mod; ans += c[i] * a.a[1][4 - i + 1]; ans %= mod; while (ans < 0) ans += mod; } printf("%lld\n", ans); } return 0; }
