好贷网好贷款

HDU 4291 A Short problem

发布时间:2016-12-4 18:33:25 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"HDU 4291 A Short problem",主要涉及到HDU 4291 A Short problem方面的内容,对于HDU 4291 A Short problem感兴趣的同学可以参考一下。

      通过矩阵快速幂找循环节,注意要每一层都要找一次循环节。。。发个题解仅供大家对拍。。。#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define MAXN 2 #define LL long long LL MOD; struct Matrix { LL data[MAXN][MAXN]; void init() { for(LL i=0; i<MAXN; i++) for(LL j=0; j<MAXN; j++) data[i][j]=0; } }; Matrix Multy(Matrix m1,Matrix m2) { Matrix r; r.init(); for(LL i=0; i<2; i++) for(LL j=0; j<2; j++) for(LL k=0; k<2; k++) r.data[i][j]=(r.data[i][j]+(m1.data[i][k]*m2.data[k][j])%MOD)%MOD; return r; } Matrix Fast_mi(Matrix ma,LL m) { Matrix r; r.init(); for(LL i=0; i<2; i++) r.data[i][i]=1; while(m) { if(m&1)r=Multy(r,ma); ma=Multy(ma,ma); m=m>>1; } return r; } Matrix a; int main() { //freopen("input.txt", "r", stdin); a.data[0][0] = 3; a.data[0][1] = 1; a.data[1][0] = 1; a.data[1][1] = 0; LL n, g, i, f, j; while(cin >> n) { n %= 240; g = n; if(!g) { cout << "0" << endl; continue; } MOD = 183120; g = Fast_mi(a, n - 1).data[0][0]; MOD = 222222224; g = Fast_mi(a, g - 1).data[0][0]; MOD = 1000000007; g = Fast_mi(a, g - 1).data[0][0]; cout << g << endl; } }

上一篇:用Node-Inspector调试NodeJs程序
下一篇:黑马程序员 Java(二)>ArrayTool工具类以及帮助文档的制作<

相关文章

相关评论