HDU 4291 A Short problem(2012 ACM/ICPC Asia Regional Chengdu Online)

HDU 4291 A Short problem(2012 ACM/ICPC Asia Regional Chengdu Online)

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=4291

Description

给一个式子求结果。类似Fibonacci的公式g(n)=3*g(n-1)+g[n-2]。

Input

给你n(1<=n<=1e18)

Output

求g(g(g(n)))

Sample Input

样例第一个就是0什么鬼,虽然没影响。

0

1

2

Sample Output

0

1

42837

题意:

如公式所示

题解:

这题首先类似Fibonacci数列,那么首先是使用矩阵快速幂。然后就是坑爹的取模,首先我们可以知道到对于最后的结果是对1e9+7取模。但还是不能明白为什么要分别取模,我的理解是如果在内层取模过大那么取出的循环节就有问题,而题目要求的是对最后的结果取模。

来自其他人的讲解,首先对于g(g(g(x)))对于mod1(1e9+7)取模,那么首先我们找出了循环节mod2即我们可以知道g(g(g(x)))%mod1 = (g(g(x)) - k * mod2)%mod1,同理我们可以得到

对于最内层g(x)的循环节。

代码:

#include <bits/stdc++.h>
using namespace std;
const long long mod1 = 1000000007;
const long long mod2 = 222222224;
const long long mod3 = 183120;
struct Matrix{
long long a,b;
long long c,d;
}; Matrix Mul(Matrix A,Matrix B,long long p)
{
Matrix ret;
ret.a = (A.a*B.a%p + A.b*B.c%p)%p;
ret.b = (A.a*B.b%p + A.b*B.d%p)%p;
ret.c = (A.c*B.a%p + A.d*B.c%p)%p;
ret.d = (A.c*B.b%p + A.d*B.d%p)%p;
return ret;
} long long f(long long n,long long p)
{
Matrix ret;
ret.a = 1;ret.b = ret.c = 0;ret.d = 1;
Matrix acc;
acc.a = 3;acc.b = acc.c = 1;acc.d = 0;
while (n){
if (n&1)
ret = Mul(ret,acc,p);
n >>= 1;
acc = Mul(acc,acc,p);
}
return ret.a;
}
int main()
{
long long n;
while (~scanf("%lld",&n)){
if (n >= 2) n = f(n-1,mod3);
if (n >= 2) n = f(n-1,mod2);
if (n >= 2) n = f(n-1,mod1);
printf("%lld\n",n);
}
return 0;
}
posted @
2016-08-09 00:59 
Thecoollight 
阅读(...) 
评论(...) 
编辑 
收藏

上一篇:20181115 python-第一章学习小结part1


下一篇:使用Jquery做分页效果