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>
#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
[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
3 100
Sample Output
1
5
5
题意：给出了原程序，显然，看到内涵的递推式明显可以使用矩阵快速幂了。
思路：原递推式是当n为偶数时fn=2*f(n-1)+1 奇数时fn=2*f(n-1) 找规律得到递推式为 f(n) = *f(n-1)+*f(n-2) +*1
（下面是没学过线代的鶸的一点理解）
其实可以把矩阵看做一个储存多数据的容器，例如这题
运算为等式右红框分别乘以左边三个红框得到的三个值
对应的就是等式左侧的f(n),f(n-1),1。
化简
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <string.h>
#define ll __int64
using namespace std; ll mod;
struct matrix
{
ll x[][];
void init()
{
for(int i = ; i < ; i++)
for(int j = ; j < ; j++)
x[i][j] = ;
}
}; matrix mul(matrix a, matrix b)
{
matrix c;
c.init();
for( int i = ; i < ; i++)
for(int j = ; j < ; j++)
{
for(int k = ; k < ; k++)
{
c.x[i][j] += a.x[i][k] * b.x[k][j];
}
c.x[i][j] %= mod;
}
return c;
}
matrix powe(matrix x, ll n)
{
matrix r;
r.init();
r.x[][] = r.x[][] = r.x[][] = ; //初始化 while(n)
{
if(n & )
r = mul(r , x);
x = mul(x , x);
n >>= ;
}
return r;
}
int main()
{ ll x, y, n, ans;
//while(~scanf("%I64d%I64d", &n, &mod))
while(cin >> n >> mod)
{
if(n == )
printf("%I64d\n", %mod);
else if(n == )
printf("%I64d\n", %mod);
else
{
matrix d;
d.init();
d.x[][] = ;
d.x[][] = ;
d.x[][] = ;
d.x[][] = ;
d.x[][] = ; d = powe(d, n - ); ans = d.x[][] * + d.x[][] * + ; //如果使用手动乘，不知为何还要再判断 matrix e;
e.init();
e.x[][] = ;
e.x[][] = ;
e.x[][] = ;
d = mul(e , d);
/*if( n % 2 ) //再判断
ans-=2;
else
ans-=1;*/
cout << d.x[][] % mod << endl;
}
}
}