本文共 1615 字，大约阅读时间需要 5 分钟。

Reading comprehension

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 1895    Accepted Submission(s): 753

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

 

 

分析：题目给的程序的意思就是给了一个递推式，但是在奇数和偶数的时候递推式不同。写几个后可以发现规律，找出一个统一的递推式。1，2，5，10，21，42，85......其中的规律是f(n) = f(n-1) + f(n-2)*2 + 1。这样的话可以用矩阵快速幂来计算。如下图：

 

代码：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;typedef long long ll;long long n, m;void f(ll a[][3], ll b[][3]){	ll c[3][3];	for(int i = 0; i < 3; i++){		for(int j = 0; j < 3; j++){			c[i][j] = 0;			for(int k = 0; k < 3; k++){				c[i][j] += a[i][k]*b[k][j] % m;			}			c[i][j] %= m;		}	}	for(int i = 0; i < 3; i++)		for(int j = 0; j < 3; j++)			a[i][j] = c[i][j];}int main(){	while(cin>>n>>m){		ll a[3][3] = {1,1,0, 2,0,0, 1,0,1};		ll b[3][3] = {0,0,1, 0,0,0, 0,0,0};		while(n){			if(n&1)				f(b, a);			f(a, a);			n >>= 1;		}		cout<
       
        <
       
      
     
    
   

转载地址：https://blog.csdn.net/zhj_fly/article/details/75339384 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！