题目连接：uva 11885 -
Number of Battlefields

题目大意：给出周长p，问多少种形状的周长为p的，而且该图形的最小包围矩阵的周长也是p，不包含矩形。

解题思路：矩阵高速幂。假设包括矩形的话，相应的则是斐波那契数列的偶数项，所以相应减去矩形的个数就可以。

#include <cstdio>

#include <cstring>

using namespace std;

typedef long long ll;

const ll MOD = 987654321;

void mul(ll a[2][2], ll b[2][2], ll c[2][2]) {

    ll ans[2][2];

    memset(ans, 0, sizeof(ans));

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

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

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

                ans[i][j] = (ans[i][j] + a[i][k] * b[k][j]) % MOD;

        }

    }

    memcpy(c, ans, sizeof(ans));

}

void power (ll a[2][2], int n) {

    ll ans[2][2] = {1, 0, 1, 0};

    while (n) {

        if (n&1)

            mul(ans, a, ans);

        mul(a, a, a);

        n /= 2;

    }

    memcpy(a, ans, sizeof(ans));

}

int main () {

    int p;

    while (scanf("%d", &p) == 1 && p) {

        if (p&1 || p < 6) {

            printf("0\n");

            continue;

        }

        p = (p - 4) / 2;

        ll a[2][2] = {1, 1, 1, 0};

        /*

        power(a, 2*p-1);

        printf("%lld\n", (a[0][0] + a[0][1]  - p - 1 + MOD) % MOD);

        */

        power(a, 2*p);

        printf("%lld\n", (a[1][0] - p - 1 + MOD) % MOD);

    }

    return 0;

}