战场的数目
时间： 1ms 内存：128M
描述：
在上题中，假设战场的图形周长为p，一共有多少种可能的战场？
例如，p<8时没有符合要求的战场，p=8时有2种战场：
p=10有9种战场：
要求输出方案总数模987654321的值。
输入
输入文件最多包含25组测试数据，每个数据仅包含一行，有一个整数p（1<=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;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。