【NOIP模拟】k-斐波那契

解析：

       其实k-斐波那契数列就是斐波拉契数列的k倍，所以题目首先是求斐波拉契数列第N项，直接用矩阵快速幂即可求得。

       于是问题转化成 f[n]*t≡1(modp)，若f[n]与p不互质则无解，否则答案为t，t可由扩展欧几里得算出。

 

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n,p,x,y,flag;

inline void mul(int a[2],int b[2][2])
{
	int c[2];
	memset(c,0,sizeof(c));
	for(int i=0;i<2;i++)
	    for(int k=0;k<2;k++)
	      c[i] = (c[i] + (long long)b[k][i] * a[k]) % p;
	memcpy(a,c,sizeof(c));
}

void mulself(int b[2][2]) {
	int c[2][2];
	memset(c, 0, sizeof(c));
	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++)
			for (int k = 0; k < 2; k++)
				c[i][j] = (c[i][j] + (long long)b[i][k] * b[k][j]) % p;
	memcpy(b, c, sizeof(c));
}

inline int solve(int n)
{
	int b[2][2]={0,1,1,1},a[2]={0,1};
	while(n)
	{
	  if(n&1)mul(a,b); 
	  n>>=1,mulself(b);
	}
	return a[1];
}

inline int exgcd(int a,int b)
{
	if(!b) return flag=(a!=1) ? 0 : 1,x=1,y=0;
	else
	{
	  exgcd(b,a%b);
	  int t=x;
	  x=y,y=t-a/b*x;
	}
}

signed main()
{
	scanf("%lld%lld",&n,&p);
	int num=solve(n);
	if(!num){cout<<"None";return 0;}
	exgcd(num,p);
	if(!flag){cout<<"None\n";}
	else cout<<(x%p+p)%p<<"\n";
	return 0;
}