【HDU - 4990】 Reading comprehension （构造+矩阵快速幂）

题干：

Read the program below carefully then answer the question. 
#pragma comment(linker, "/STACK:1024000000,1024000000") 
#include <cstdio> 
#include<iostream> 
#include <cstring> 
#include <cmath> 
#include <algorithm> 
#include<vector> 

const int MAX=100000*2; 
const int INF=1e9; 

int main() 
{ 
  int n,m,ans,i; 
  while(scanf("%d%d",&n,&m)!=EOF) 
  { 
    ans=0; 
    for(i=1;i<=n;i++) 
    { 
      if(i&1)ans=(ans*2+1)%m; 
      else ans=ans*2%m; 
    } 
    printf("%d\n",ans); 
  } 
  return 0; 
}

Input

Multi test cases，each line will contain two integers n and m. Process to end of file. 
[Technical Specification] 
1<=n, m <= 1000000000

Output

For each case，output an integer，represents the output of above program.

Sample Input

1 10 3 100

Sample Output

1 5

解题报告：

      根据题干找规律，发现f(n) = f(n-1) + 2 * f(n-2) +1

AC代码：

#pragma comment(linker, "/STACK:1024000000,1024000000") #include <cstdio> #include<iostream> #include <cstring> #include <cmath> #include <algorithm> #define ll long long struct Matrix {ll arr[4][4]; }unit,trans; ll n,m,ans; Matrix mul( Matrix a,Matrix b,ll mod) {Matrix c;for(int i = 1; i<=3; i++) {for(int j = 1; j<=3; j++) {c.arr[i][j] = 0; for(int k = 1; k<=3; k++) { // if(a.arr[i][k] && b.arr[k][j])c.arr[i][j] = (c.arr[i][j] + a.arr[i][k]*b.arr[k][j])%mod;}}}return c; } Matrix q_pow(Matrix a, ll k,ll mod) {Matrix ans;ans = unit;while(k) {if(k&1) {ans=mul(ans,a,m);}k>>=1;a=mul(a,a,m);}return ans; } void init() {memset(unit.arr,0,sizeof(unit.arr) );for(int i = 1; i<=3; i++) {unit.arr[i][i] = 1;trans.arr[i][1] = trans.arr[i][2] = trans.arr[i][3] = 0;}trans.arr[1][1]=trans.arr[1][3] =trans.arr[2][1]=trans.arr[3][3] = 1;trans.arr[1][2] = 2; } int main() { Matrix ans;ll sum=0;while(scanf("%lld%lld",&n,&m)!=EOF) {sum = 0;init();if(n==1) {printf("%lld\n",1%m);continue; }else if(n == 2) {printf("%lld\n",2%m);continue;}ans = q_pow(trans,n-2,m);sum = ans.arr[1][1]*2 + ans.arr[1][2]*1 + ans.arr[1][3];printf("%lld\n",sum%m);}return 0; }

总结：

      这题坑很多啊，总是巧妙的跳了进去。

      1.全局变量ll的n和m，结果输入用%d这个题的Mul函数 不是i<=n了！而是i<=3即可，i<=n就错了！  此题和HDU - 5015不一样，不是矩阵是个不确定的矩阵！所以这里是小于等于3！！即

      2.输出的时候n=1和n=2需要特判一下，因为你传参是n-2。即：这种地方一定要小心！你的函数是有使用条件的，这一点不仅适用于矩阵快速幂，还有很多其他的地方。

     3.输出n==2的时候，别忘了也需要取模！！

    4.最后的输出 也需要取模！

总结

以上是生活随笔为你收集整理的【HDU - 4990】 Reading comprehension （构造+矩阵快速幂）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。