NowCoder数列（矩阵快速幂变式）

时间限制 3000 ms 内存限制 32768 KB 代码长度限制 100 KB

题目描述

NowCoder最近在研究一个数列：

* F(0) = 7

* F(1) = 11

* F(n) = F(n-1) + F(n-2) (n≥2)

他称之为NowCoder数列。请你帮忙确认一下数列中第n个数是否是3的倍数。

输入描述:

输入包含多组数据。

每组数据包含一个整数n，(0≤n≤1000000)。

输出描述:

对应每一组输入有一行输出。

如果F(n)是3的倍数，则输出“Yes”；否则输出“No”。

输入例子:

输出例子:

No

No

Yes

No

No

No

题解：我最初的想法是肯定是矩阵快速幂的变式题，就想用矩阵快速幂，并且可以回顾一下矩阵快速幂，但是发现这题没我想的那么简单，我忽略的点在于取模的时候是对1000000007取得，不是足够大，会出现1000000007*3的倍数的情况，然后改成了0x3f3f3f3f再对3取模就可以了，当然网上有更为简单的方法，是找规律的，但是我觉得可以当作矩阵快速幂的变式练习来做。

PS：最近身体真的每况愈下。。。要加强锻炼了。

附上代码：

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#define MOD 0x3f3f3f3f

using namespace std;

typedef long long int ll;

int flag;

struct mat

{

	ll a[4][4];

}ans,res;

mat Mul(mat x,mat y)

{

	mat t;

    memset(t.a,0,sizeof(t.a));

    for(int i=0;i<2;i++)

    {

    	for(int j=0;j<2;j++)

    	{

    		for(int k=0;k<2;k++)

    		{

    			t.a[i][j]+=(x.a[i][k]*y.a[k][j]);

    			t.a[i][j]%=MOD;

			}

		}

	}

	return t;

}

void quickMod(long long int N)

{

	ans.a[0][0]=11;

	ans.a[0][1]=7;

	ans.a[1][0]=7;

	ans.a[1][0]=0;

	while(N)

	{

		if(N&1)

		{

			ans=Mul(ans,res);

		}

		res=Mul(res,res);

	    N>>=1;

	}

 }

int main()

{

	ll n;

	while(scanf("%lld",&n)!=EOF)

   {

   	flag=0;

	res.a[0][0]=1;

	res.a[0][1]=1;

	res.a[1][0]=1;

	res.a[1][1]=0;

	if(n==0)

	{

		printf("No\n");

	}

	else if(n==1)

	{

		printf("No\n");

	}

	else

   {

	   	quickMod(n-1);

	   	if(ans.a[0][0]%3==0||flag==1)

	   	{

	   	   printf("Yes\n");

		}

		else

		{

			printf("No\n");

		}

   }

   }

	return 0;

 }

巴特西