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;
}
题目链接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;
}