1687 - 战场的数目
在上题中，假设战场的图形周长为p，一共有多少种可能的战场？
例如，p<8时没有符合要求的战场，p=8时有2种战场：
p=10有9种战场：
要求输出方案总数模987654321的值。
输入
输入文件最多包含25组测试数据，每个数据仅包含一行，有一个整数p（1<=p<=109），表示战场的图形周长。p=0表示输入结束，你的程序不应当处理这一行。
输出
对于每组数据，输出仅一行，即满足条件的战场总数除以987654321的余数。
Input
Output
Examples
Input
7 8 9 10 0
Output
0 2 0 9
Solution C++
#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; }