noip模拟赛 蒜头君的兔子

分析：直接暴力算有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模拟赛 蒜头君的兔子的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。