2014
02-17

# Fibonacci Check-up

Every ALPC has his own alpc-number just like alpc12, alpc55, alpc62 etc.
As more and more fresh man join us. How to number them? And how to avoid their alpc-number conflicted?
Of course, we can number them one by one, but that’s too bored! So ALPCs use another method called Fibonacci Check-up in spite of collision.

First you should multiply all digit of your studying number to get a number n (maybe huge).
Then use Fibonacci Check-up!
Fibonacci sequence is well-known to everyone. People define Fibonacci sequence as follows: F(0) = 0, F(1) = 1. F(n) = F(n-1) + F(n-2), n>=2. It’s easy for us to calculate F(n) mod m.
But in this method we make the problem has more challenge. We calculate the formula , is the combination number. The answer mod m (the total number of alpc team members) is just your alpc-number.

First line is the testcase T.
Following T lines, each line is two integers n, m ( 0<= n <= 10^9, 1 <= m <= 30000 )

First line is the testcase T.
Following T lines, each line is two integers n, m ( 0<= n <= 10^9, 1 <= m <= 30000 )

2
1 30000
2 30000

1
3

1 题目的意思是给定n和m，要求

2 这一题有两种思路，对于这种的题肯定是有递推式的，那么找不到递推式的时候我们尝试去打表

下面我打出了前几十项，发现了n >= 2的时候有f(n) = 3*f(n-1)-f(n-2)，那么我们可以利用矩阵快速幂求f(n)

3 另一种思路是考虑f(n) = f(n-1) + f(n-2)，那么我们可以利用矩阵求出任意的f(n)

1 1 *  f(n-1) = f(n)

1 0    f(n-2)    f(n-1)

那么对于n >= 2的时候，我们假设左边的矩阵为A，那么A^(n-1)即可求出答案

那么A^(n-1)为 f(n) f(n-1)

f(n-1) f(n-2)

那么根据我们知道二项式定理为(a+b)^n=C(n,0)a^n+C(n,1)a^(n-1)*b+C(n,2)a^(n-2)*b^2+…+C(n,n)b^n

那么我们发现所求的式子和上面很像，因为f(n)可以利用上面的A矩阵的n-1次方求出

那么原式所求变成(1+A)^n，这里的1为单位矩阵。因为做了n次方，那么最终的答案就是ans.mat[0][1] 或ans.mat[1][0]

// 方法一
/************************************************
* By: chenguolin                               *
* Date: 2013-08-30                             *
************************************************/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 2;

int n , MOD;
struct Matrix{
int mat[N][N];
Matrix operator*(const Matrix &m)const{
Matrix tmp;
for(int i = 0 ; i < N ; i++){
for(int j = 0 ; j < N ; j++){
tmp.mat[i][j] = 0;
for(int k = 0 ; k < N ; k++)
tmp.mat[i][j] += mat[i][k]*m.mat[k][j]%MOD;
tmp.mat[i][j] %= MOD;
}
}
return tmp;
}
};

int Pow(Matrix m){
if(n <= 1) return n%MOD;
Matrix ans;
ans.mat[0][0] = ans.mat[1][1] = 1;
ans.mat[0][1] = ans.mat[1][0] = 0;
n--;
while(n){
if(n&1)
ans = ans*m;
n >>= 1;
m = m*m;
}
return (ans.mat[0][0]%MOD+MOD)%MOD;
}

int main(){
Matrix m;
m.mat[0][0] = 3 ; m.mat[0][1] = -1;
m.mat[1][0] = 1 ; m.mat[1][1] = 0;
int cas;
scanf("%d" , &cas);
while(cas--){
scanf("%d%d" , &n , &MOD);
printf("%d\n" , Pow(m));
}
return 0;
}
/************************************************
* By: chenguolin                               *
* Date: 2013-08-30                             *
************************************************/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 2;

int n , MOD;
struct Matrix{
int mat[N][N];
Matrix operator*(const Matrix &m)const{
Matrix tmp;
for(int i = 0 ; i < N ; i++){
for(int j = 0 ; j < N ; j++){
tmp.mat[i][j] = 0;
for(int k = 0 ; k < N ; k++)
tmp.mat[i][j] += mat[i][k]*m.mat[k][j]%MOD;
tmp.mat[i][j] %= MOD;
}
}
return tmp;
}
};

int Pow(Matrix m){
if(n <= 1) return n%MOD;
Matrix ans;
ans.mat[0][0] = ans.mat[1][1] = 1;
ans.mat[0][1] = ans.mat[1][0] = 0;
while(n){
if(n&1)
ans = ans*m;
n >>= 1;
m = m*m;
}
return ans.mat[1][0]%MOD;
}

int main(){
Matrix m;
m.mat[0][0] = 2 ; m.mat[0][1] = 1;
m.mat[1][0] = 1 ; m.mat[1][1] = 1;
int cas;
scanf("%d" , &cas);
while(cas--){
scanf("%d%d" , &n , &MOD);
printf("%d\n" , Pow(m));
}
return 0;
}

1. 问题是大部分人看动漫只是图一乐呵，那些真正沉迷二次元的死肥宅既影响不到其他人，我们也已经默认了他们注孤生不是吗？但狂热喜欢掏粪和碧波儿的那些人可是实实在在影响到了其他人的生活，比如逛街从一家店的baby baby oh走到另一家店的左手右手一个慢动作

2. 问题是大部分人看动漫只是图一乐呵，那些真正沉迷二次元的死肥宅既影响不到其他人，我们也已经默认了他们注孤生不是吗？但狂热喜欢掏粪和碧波儿的那些人可是实实在在影响到了其他人的生活，比如逛街从一家店的baby baby oh走到另一家店的左手右手一个慢动作

3. 问题是大部分人看动漫只是图一乐呵，那些真正沉迷二次元的死肥宅既影响不到其他人，我们也已经默认了他们注孤生不是吗？但狂热喜欢掏粪和碧波儿的那些人可是实实在在影响到了其他人的生活，比如逛街从一家店的baby baby oh走到另一家店的左手右手一个慢动作

4. 问题是大部分人看动漫只是图一乐呵，那些真正沉迷二次元的死肥宅既影响不到其他人，我们也已经默认了他们注孤生不是吗？但狂热喜欢掏粪和碧波儿的那些人可是实实在在影响到了其他人的生活，比如逛街从一家店的baby baby oh走到另一家店的左手右手一个慢动作

5. 问题是大部分人看动漫只是图一乐呵，那些真正沉迷二次元的死肥宅既影响不到其他人，我们也已经默认了他们注孤生不是吗？但狂热喜欢掏粪和碧波儿的那些人可是实实在在影响到了其他人的生活，比如逛街从一家店的baby baby oh走到另一家店的左手右手一个慢动作

6. 问题是大部分人看动漫只是图一乐呵，那些真正沉迷二次元的死肥宅既影响不到其他人，我们也已经默认了他们注孤生不是吗？但狂热喜欢掏粪和碧波儿的那些人可是实实在在影响到了其他人的生活，比如逛街从一家店的baby baby oh走到另一家店的左手右手一个慢动作

7. 问题是大部分人看动漫只是图一乐呵，那些真正沉迷二次元的死肥宅既影响不到其他人，我们也已经默认了他们注孤生不是吗？但狂热喜欢掏粪和碧波儿的那些人可是实实在在影响到了其他人的生活，比如逛街从一家店的baby baby oh走到另一家店的左手右手一个慢动作

8. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。