hdu 4291 矩阵幂 循环节

http://acm.hdu.edu.cn/showproblem.php?pid=4291

凡是取模的都有循环节-----常数有,矩阵也有,并且矩阵的更奇妙:

g(g(g(n))) mod 109 + 7  最外层MOD=1e9+7  能够算出g(g(n))的循环节222222224。进而算出g(n)的循环节183120LL。然后由内而外计算就可以

凝视掉的是求循环节的代码

//#pragma comment(linker, "/STACK:102400000,102400000")
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std; #define ls(rt) rt*2
#define rs(rt) rt*2+1
#define ll long long
#define ull unsigned long long
#define rep(i,s,e) for(int i=s;i<e;i++)
#define repe(i,s,e) for(int i=s;i<=e;i++)
#define CL(a,b) memset(a,b,sizeof(a))
#define IN(s) freopen(s,"r",stdin)
#define OUT(s) freopen(s,"w",stdout)
const ll ll_INF = ((ull)(-1))>>1;
const double EPS = 1e-8;
const double pi = acos(-1.0);
const int INF = 100000000;
const ll MOD[3] = {183120LL,222222224LL,1000000007LL};
const int N = 2; struct Matrix{
ll m[N][N];
//int sz;//矩阵的大小
}; Matrix I= {3LL,1LL,//要幂乘的矩阵
1LL,0LL,
};
Matrix unin={1LL,0LL,//单位矩阵
0LL,1LL,
};
Matrix matrixmul(Matrix a,Matrix b,long long mod)//矩阵a乘矩阵b
{
Matrix c;
for(int i=0; i<N; i++)
for(int j=0; j<N; j++)
{
c.m[i][j]=0LL;
for(int k=0; k<N; k++)
c.m[i][j]+=(a.m[i][k]*b.m[k][j])%mod;
c.m[i][j]%=mod;
}
return c;
}
Matrix quickpow(long long n,long long mod)
{
Matrix m=I,b=unin;//求矩阵I的n阶矩阵
while(n>=1)
{
if(n&1)
b=matrixmul(b,m,mod);
n=n>>1;
m=matrixmul(m,m,mod);
}
return b;
} ll solve(ll n)
{
ll ans;
Matrix ret;
ret.m[0][0]=n;
for(int i=0;i<3;i++)
{
if(ret.m[0][0]!=0 && ret.m[0][0]!=1)ret=quickpow(ret.m[0][0]-1,MOD[i]);
} return ret.m[0][0];
} int main()
{
//precal();
ll n;
while(~scanf("%I64d",&n))
{
if(n==0){puts("0");continue;}
if(n==1){puts("1");continue;}
//printf("%I64d\n",solve(n));
cout << solve(n)%1000000007LL << endl;
}
return 0;
}

hdu 4291 矩阵幂  循环节

上一篇:HDU 1757 A Simple Math Problem(矩阵高速幂)


下一篇:IOS 学习笔记 2015-03-24 OC-API-网络访问-案例一