蒜头君的兔子

 

蒜头君的兔子

 

蒜头君的小伙伴在 第一年 送给他一对 一岁 的兔子，并告诉他：这种兔子 刚生下来时算 00 岁，到了 22 岁时就可以繁殖了，它在 2-102−10 岁时，每年会生下来一对兔子，这些兔子到了 22 岁也可以繁殖，但这些兔子在 1010 岁那年 生完仔后 不久就会死亡，蒜头君想知道，第 nn 年兔子 产仔之后（第 nn 年 1010 岁的兔子此时已经死亡），他会有多少对兔子。结果对 10000000071000000007 取模。

输入格式

共一行，一个正整数 nn，表示蒜头君想知道第 nn 年的兔子总对数。

输出格式

输出一个整数，表示第 nn 年兔子总对数对 10000000071000000007 取模的值。

数据规模

对于 3030% 的数据，满足 1 \le n \le 10^31≤n≤10​3​​；

对于 6060% 的数据，满足 1 \le n \le 10^51≤n≤10​5​​；

对于 100100% 的数据，满足 1 \le n \le 10^91≤n≤10​9​​。

样例输入1

10

样例输出1

88

样例输入2

88

样例输出2

352138150

样例输入3

10086

样例输出3

405567313

题解

裸的矩阵快速幂，复杂度O(11^3logn);

 

#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<algorithm> #define mod (1000000007) using namespace std; typedef long long lol; lol n,a[11][11]={{1,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0}}; lol b[11][11]={{0,1,0,0,0,0,0,0,0,0,0},{1,0,1,0,0,0,0,0,0,0,0},{1,0,0,1,0,0,0,0,0,0,0},{1,0,0,0,1,0,0,0,0,0,0},{1,0,0,0,0,1,0,0,0,0,0},{1,0,0,0,0,0,1,0,0,0,0},{1,0,0,0,0,0,0,1,0,0,0},{1,0,0,0,0,0,0,0,1,0,0},{1,0,0,0,0,0,0,0,0,1,0},{1,0,0,0,0,0,0,0,0,0,0},{1,0,0,0,0,0,0,0,0,0,0}}; lol ans; struct matrix {lol a[11][11];matrix(){for(lol i=0;i<=10;i++)for(lol j=0;j<=10;j++)a[i][j]=0;}matrix(lol b[11][11]){for(lol i=0;i<=10;i++)for(lol j=0;j<=10;j++)a[i][j]=b[i][j];}matrix operator*(matrix b){matrix ans;for(lol i=0;i<=10;i++)for(lol j=0;j<=10;j++)for(lol k=0;k<=10;k++)ans.a[i][j]=(ans.a[i][j]+(a[i][k]*b.a[k][j])%mod)%mod;return ans;} }S,T; int main() {S=matrix(a);T=matrix(b);scanf("%lld",&n);while(n){if(n&1)S=S*T;T=T*T;n>>=1;}for(lol i=0;i<=10;i++)ans=(ans+S.a[0][i])%mod;printf("%lld\n",ans);return 0; }

 

 

 

 

转载于:https://www.cnblogs.com/huangdalaofighting/p/7259893.html

总结

以上是生活随笔为你收集整理的蒜头君的兔子的全部内容，希望文章能够帮你解决所遇到的问题。

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