撰写时间限制(普通/Java) : 1000 MS/ 3000 MS 运行内存限制 : 65536 KByte
总提交 : 125 测试通过 : 53
比赛描述
暑假到了，阿张带着他的女友阿玉去红山动物园玩儿。女友在一旁开心地蹦蹦跳跳，阿张却是毫无心情，一心挂念着还未完成的项目。阿张想着想着，阿玉在一旁惊喜地叫了起来“啊，兔兔！好多小兔兔！”阿张看了过去，只见一只大兔子蹦在前面，后面跟了几只小兔子，可爱极了。阿张看到兔子，眼前一亮。他想到了之前困扰已久的问题，问身边的阿玉：“你知道有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，每个月的兔子总数为多少吗？”阿玉看着眼前的直男男友，一甩手，生气地走了。可是阿张却还沉浸在这道问题之中，久久不能自拔。他看向了旁边的你，作为资深僚机的你，能帮他解决这个问题吗？（难道不应该追过去吗！）聪明的你知道兔子每个月的数量就是斐波那契数列，在斐波那契数列中，F0=0，F1=1，Fn=Fn-1+Fn-2（n≥2），因而序列前十位分别为0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …，
有一个可用于计算斐波那契数列的公式如下所示：
现在给出一个整数n，请聪明的你求出Fn的最后四位数字。
输入
输入仅包含一行，这一行仅含有一个整数n（ 0 ≤ n ≤ 1,000,000,000）。
输出
输出包含Fn的最后四位数字，若这最后四位数字都为0，则输出0，否则忽略前置的0。（即输出Fn mod 10000）
样例输入
9
样例输出
34
标程
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
const int mod = 10000;
LL n;
struct Mat
{
int m[2][2];
};
Mat P=
{
1,1,
1,0
};
Mat I=
{
1,0,
0,1
};
Mat mul (Mat x,Mat y)
{
Mat z;
for(int i = 0; i < 2; i++)
{
for(int j = 0; j < 2; j++)
{
z.m[i][j] = 0;
for(int k = 0; k < 2; k++)
{
z.m[i][j] += (x.m[i][k]*y.m[k][j])%mod;
z.m[i][j] %= mod;
}
}
}
return z;
}
Mat quick_Mod(Mat a, LL b)
{
Mat ans = I;
Mat tmp = a;
while(b > 0)
{
if(b & 1)
ans = mul(ans, tmp);
tmp = mul(tmp, tmp);
b >>= 1;
}
return ans;
}
int main()
{
cin>> n;
Mat tmp = quick_Mod(P, n);
cout<< tmp.m[0][1]<< endl;
return 0;
}
赛程：
#include<algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
const ll mod = 1000000007;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
struct m{
int x1; int x2; int y1; int y2;
m(int _x1 = 1, int _x2 = 1, int _y1 = 1, int _y2 = 0){
x1 = _x1; x2 = _x2; y1 = _y1; y2 = _y2;
}
m operator*(m &a){
m t;
t.x1 = x1*a.x1 + y1*a.x2;
t.y1 = x1*a.y1 + y1*a.y2;
t.x2 = x2*a.x1 + y2*a.x2;
t.y2 = x2*a.y1 + y2*a.y2;
t.x1%=10000;
t.x2%=10000;
t.y1%=10000;
t.y2%=10000;
return t;
}
};
m mobile;
m cal(int n){
if(n==1){
return mobile;
}
m t = cal(n/2);
t = t*t;
if(n%2==1){
t = t*mobile;
}
return t;
}
int main(){
int n;
scanf("%d", &n);
if(n==0){
printf("0");
}
else{
m sum = cal(n);
printf("%d", sum.x2);
}
return 0;
}