uva 11885 - Number of Battlefields(矩陣快速冪)

題目連接：uva 11885 - Number of Battlefields

題目大意：給出周長p，問多少種形狀的周長為p的，並且該圖形的最小包圍矩陣的周長也是p，不包括矩形。

解題思路：矩陣快速冪，如果包含矩形的話，對應的則是斐波那契數列的偶數項，所以對應減去矩形的個數即可。

#include 
#include 

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;
}