HDU 4990 Reading comprehension（找规律）

Reading comprehension

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2756    Accepted Submission(s): 1092

 

Problem Description

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

 

 

题意：给这样一段代码，让你优化，我们可以不问输入的第二个值，先按第一个值跑一下，可以得到

n = 1 -> 1

n = 2 -> 2

n = 3 -> 5

n = 4 -> 10

n = 5 -> 21

n = 6 -> 42

n = 7 -> 85

............................

通过以上数我们可以得到这样一个递推关系式：

f（n）=2*f（n-2）+f（n-1）+1；

直接推得话肯定TLE,我们需要用矩阵快速幂来优化

好了就是上图所示

代码：

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#define ll long long
#define mod 1000000007
#define mem(a) memset(a,0,sizeof(a))

using namespace std;

typedef pair <int,int> pii;
const int maxn = 1000 + 5 , inf = 0x3f3f3f3f;

ll n,m;
struct Matrix{
    ll a[5][5];
    Matrix(){
        mem(a);
    }
    Matrix operator * (const Matrix &b){
        Matrix ans;
        for(ll i=0;i<3;i++){
            for(ll j=0;j<3;j++){
                for(ll k=0;k<3;k++){
                    ans.a[i][j]+=(a[i][k]*b.a[k][j])%m;
                }
            }
        }
        return ans;
    }
};
Matrix base;
Matrix MyPow(Matrix A,int n){
    Matrix res = base;
    while(n){
        if(n&1) res = res*A;
        A = A*A;
        n>>=1;
    }
    return res;
}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    while(cin>>n>>m){
        for(ll i=0;i<3;i++){
            for(ll j=0;j<3;j++){
                if(i==j) base.a[i][j] = 1;
            }
        }
        if(n==1){
            cout<<1%m<<endl;
        }
        else if(n==2){
            cout<<2%m<<endl;
        }
        else{
            Matrix A,B;
            memset(A.a,0,sizeof(A.a));
            memset(B.a,0,sizeof(B.a));
            B.a[0][0]=1;
            B.a[0][1]=2;
            B.a[0][2]=A.a[1][0]=A.a[1][1]=A.a[2][1]=A.a[2][2]=1;
            A.a[0][1]=2;
            Matrix tmp;
            tmp=MyPow(A,n-2);
            B=B*tmp;
            cout << B.a[0][1]%m << endl;
        }
    }
}