HDU4990 Reading comprehension

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 <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
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<<b[0][0]<<endl;
	}
	return 0;
}