分析：直接暴力算有30分，像斐波那契那樣推式子算有60分，如果想要得到100分就要用一種數列題的常見優化--矩陣了.

? ? ? 當前的兔子數和十年內的兔子數有關，我們需要1個1*11的矩陣，來記錄當前為0歲、1歲、2歲......兔子的數量，同時還需要一個快速冪矩陣進行計算.由于一年后a[1] = a[0],a[2] = a[1],......,a[10] = a[9],a[0] = a[1] + a[2] + a[3] + ...... + a[10],很容易構造出矩陣來.

? ? ? 因為矩陣比較復雜，還是推薦用結構體來寫.

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm>using namespace std;const int mod = 1000000007; int t; long long print,sum;struct node {int n, m;long long a[20][20];node(){memset(a, 0, sizeof(a));n = 0;m = 0;} }s,p,ans;node mul(node a, node b) {node c;c.n = a.n;c.m = b.m;for (int i = 0; i < a.n; i++)for (int j = 0; j < b.m; j++)for (int k = 0; k < a.m; k++){c.a[i][j] += (a.a[i][k] * b.a[k][j]) % mod;c.a[i][j] %= mod;}return c; }node qpow(node a, int b) {node t;t.n = 11;t.m = 11;for (int i = 0; i < 11; i++)t.a[i][i] = 1;while (b){if (b & 1)t = mul(t, a);a = mul(a, a);b >>= 1;}return t; }int main() {scanf("%d", &t);s.n = 1;s.m = 11;s.a[0][1] = 1;p.n = 11;p.m = 11;for (int i = 1; i <= 9; i++){p.a[i][0] = 1;p.a[i - 1][i] = 1;}p.a[10][0] = 1;ans = mul(s, qpow(p, t - 1));for (int i = 0; i <= 10; i++)sum = (sum + ans.a[0][i]) % mod;printf("%lld\n", sum);return 0; }

?

轉載于:https://www.cnblogs.com/zbtrs/p/7598991.html

總結

以上是生活随笔為你收集整理的noip模拟赛 蒜头君的兔子的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。