战场的数目

战场的数目

时间: 1ms        内存:128M

描述:

在上题中,假设战场的图形周长为p,一共有多少种可能的战场?

 

例如,p<8时没有符合要求的战场,p=8时有2种战场:

p=109种战场:

 

要求输出方案总数模987654321的值。

 

输入

输入文件最多包含25组测试数据,每个数据仅包含一行,有一个整数p1<=p<=109),表示战场的图形周长。p=0表示输入结束,你的程序不应当处理这一行。

 

输出

对于每组数据,输出仅一行,即满足条件的战场总数除以987654321的余数。

输入:

输出:

示例输入:

7
8
9
10
0

示例输出:

0
2
0
9

提示:

参考答案(内存最优[800]):

#include <stdio.h>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll mod=987654321;

ll A[2][2],B[2][2],T[2][2];

void pow(int n)
{
	if(n==0)
	{
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)
				B[i][j]=(i==j);
		return;
	}
	if(n&1)
	{
		pow(n-1);
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)
			{
				T[i][j]=0;
					for(int k=0;k<2;k++)
						T[i][j]=(T[i][j]+A[i][k]*B[k][j])%mod;
			}
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)
			{
				B[i][j]=T[i][j];
			}
		
	}
	else
	{
		pow(n/2);
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)
			{
				T[i][j]=0;
					for(int k=0;k<2;k++)
						T[i][j]=(T[i][j]+B[i][k]*B[k][j])%mod;
			}
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)
			{
				B[i][j]=T[i][j];
			}
		
	}
}

int main()
{
  int n;
  A[0][0]=1;	A[0][1]=1;
  A[1][0]=1;	A[1][1]=0;
  while (scanf("%d", &n) == 1 && n)
  {
	ll ans=0;
	if(n&1) ans=0;
	else if(n<4) ans=0;
	else
	{
		pow(n-4);
		ans=B[0][0]-n/2+1;
		ans%=mod;
		if(ans<0)ans+=mod;
	}
	printf("%lld\n",ans);
  }

  return 0;
}

参考答案(时间最优[0]):

#include <stdio.h>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll mod=987654321;

ll A[2][2],B[2][2],T[2][2];

void pow(int n)
{
	if(n==0)
	{
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)
				B[i][j]=(i==j);
		return;
	}
	if(n&1)
	{
		pow(n-1);
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)
			{
				T[i][j]=0;
					for(int k=0;k<2;k++)
						T[i][j]=(T[i][j]+A[i][k]*B[k][j])%mod;
			}
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)
			{
				B[i][j]=T[i][j];
			}
		
	}
	else
	{
		pow(n/2);
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)
			{
				T[i][j]=0;
					for(int k=0;k<2;k++)
						T[i][j]=(T[i][j]+B[i][k]*B[k][j])%mod;
			}
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)
			{
				B[i][j]=T[i][j];
			}
		
	}
}

int main()
{
  int n;
  A[0][0]=1;	A[0][1]=1;
  A[1][0]=1;	A[1][1]=0;
  while (scanf("%d", &n) == 1 && n)
  {
	ll ans=0;
	if(n&1) ans=0;
	else if(n<4) ans=0;
	else
	{
		pow(n-4);
		ans=B[0][0]-n/2+1;
		ans%=mod;
		if(ans<0)ans+=mod;
	}
	printf("%lld\n",ans);
  }

  return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注