Hdu 4291

这道题，给我的最大的知识点就是对于去模运算，一定可以找到循环节，这题只不过是嵌套了两层，可以分别找到循环节。关于这题如何找循环节的，直接暴力，网上也有很多。

找到循环节之后，另一个知识点就是对于线性关系可以使用矩阵快速幂来加速。

附上代码：

 /*************************************************************************

     > File Name: 4292.cpp

     > Author: Stomach_ache

     > Mail: 1179998621@qq.com

     > Created Time: 2014年04月20日 星期日 22时06分59秒

     > Propose:

  ************************************************************************/

 #include <iostream>

 #include <cmath>

 #include <algorithm>

 #include <cstring>

 #include <string>

 #include <cstdio>

 #include <fstream>

 using namespace std;

 #define MOD1 (1000000007)

 #define MOD2  (222222224)

 #define MOD3 (183120)

 typedef long long LL;

 struct Matrix {

         LL a[][];

         //Matrix(int m):n(m){memset(a, 0, sizeof(a));}

         inline Matrix multiply(Matrix& y, LL mod) {

                 Matrix ret;

                 for (LL i = ; i < ; i++) {

                         for (LL j = ; j < ; j++) {

                                 LL tmp = ;

                                 for (LL k = ; k < ; k++) {

                                         tmp = (tmp+a[i][k]*y.a[k][j])%mod;

                                         //ret.a[i][j] = (ret.a[i][j]+tmp)%mod;

                                 }

                                 ret.a[i][j] = tmp;

                         }

                 }

                 return ret;

         }

 };

 Matrix power_mod(Matrix x, LL y, LL mod) {

         Matrix ans;

         ans.a[][] = ans.a[][] = ;

         ans.a[][] = ans.a[][] = ;

         while (y) {

                 if (y % ) {

                         ans = ans.multiply(x, mod);

                 }

                 x = x.multiply(x, mod);

                 y /= ;

         }

         return ans;

 }

 int main(void) {

         Matrix A;

         A.a[][] = ;

         A.a[][] = ;

         A.a[][] = ;

         A.a[][] = ;

         LL n;

         while (cin >> n) {

                 if (n ==  || n == ) {

                         cout << n << endl;

                         continue;

                 }

                 Matrix tmp1 = power_mod(A, n-, MOD3);

                 n = tmp1.a[][];

                 if (n !=  && n != ) {

                     tmp1 = power_mod(A, n-, MOD2);

                     n = tmp1.a[][];

                 }

                 if (n !=  && n != ) {

                     tmp1 = power_mod(A, n-, MOD1);

                     n = tmp1.a[][];

                 }

                 cout << n << endl;

         }

         return ;

 }

巴特西

Hdu 4291

最新文章

热门文章