1040: Count

1040: Count

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 2  Solved: 2
[Submit][Status][Web Board]

Description

Many ACM team name may be very funny,such as "Complier_Error","VVVVV".Oh,wait for a minute here.

Is it "W W"+"V",or "W"+"V V V",or something others we can treat as?There are several ways we can treat this name "VVVVV" (5 'V's),as V V can be treat as a W.

For 5 'V's,our have 8 ways.They are:

1. V V V V V

2. V W W

3. W W V

4. V W V V

5. W V W

6. W V V V

7. V V W V

8. V V V W

The problem here is that for n 'V's,how many ways do we have to treat it?Because the answer may be too large, you should output the answer module by p.(If n is 0,then we have just one way.)

Input

There are multiple test cases. The first line of the input contains an integer M, meaning the number of the test cases.
For each test cases, there are two integers n and p in a single line.
You can assume that 0<=n<=2100000000, 0<p<=2009.

Output

For each test case, output the answer with case number in a single line.

Sample Input

2
5 5
4 7

Sample Output

3
5

HINT

 

Source

解题思路：

这个题目是这次个人赛的题目 不知道该说自己能力不行 还是该说自己发挥不好呢？  两方面的原因都有吧！  现在我也不想管很多  只想好好地充实自己 现在先打基础吧！ 好好努力 

据说大牛都是被虐出来的 呵呵

开始一看到这个题目就知道是斐波那契数 去年暑假个人赛的时候快速求幂 但是因为觉得不怎么重要也没学  所以一直放在那里 所以看懂了这个题自己也动不了

#include <iostream>
using namespace std;

struct SS{int S[2][2];};
int n=2,p;

SS matrix_mult(SS A,SS B)
{
	SS C;
	int i,j,k;
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			C.S[i][j]=0;
			for(k=0;k<n;k++)
			{
				C.S[i][j]+=A.S[i][k]*B.S[k][j];
			}
			C.S[i][j]=C.S[i][j]%p;
		}
	}
	return C;
}

SS matrix_pow_mod(SS A,int n)
{
	if(n==1||n==0) return A;
	SS T;
	T=matrix_pow_mod(A,n/2);
	T=matrix_mult(T,T);
	if(n%2==1) T=matrix_mult(A,T);
	return T;
}

int main()
{
	int n;
	SS A,ans;
	A.S[0][0]=0;A.S[0][1]=1;A.S[1][0]=1;A.S[1][1]=1;
	while(cin>>n>>p)
	{
		ans=matrix_pow_mod(A,n);
		cout<<ans.S[1][1]<<endl;
	}
	return 0;
}