BZOJ2476 战场的数目

2015.01.08 23:20 Thu| 0 visits oi_2015| 2015_刷题日常| Text

Solution

对于一个周长为偶数 n (n > 4)的战场,可分为以下情况分类讨论:

  • 在一侧存在一个高为 1 的小正方形 去掉这一个小正方形,其余部分和周长为 n - 2 的战场一一对应。
  • 在两侧均存在一个高为 1 的小正方形 去掉这两个小正方形,其余部分和周长为 n - 4 的战场一一对应。
  • 在两侧均不存在高为 1 的小正方形 去掉最底部一排正方形,其余部分和周长为 n - 2 的战场一一对应。

这样,可以得到递推式 f[n] = 3*f[n-2] - f[n-4] 。可由矩阵乘法解决。

Code

#include <bits/stdc++.h>
#define N 2
#define mod 987654321

using namespace std;

struct matrix
{
    int s; long long t[N][N];

    matrix(int _s = 0) : s(_s)
    { memset(t, 0, sizeof t); }

    friend matrix operator *(const matrix &a, const matrix &b)
    {
        matrix re(a.s);
        for (int i = 0; i < re.s; ++i)
            for (int j = 0; j < re.s; ++j)
                for (int k = 0; k < re.s; ++k)
                    re.t[i][j] = (re.t[i][j] + a.t[i][k] * b.t[k][j]) % mod;
        return re;
    }

    matrix &operator *=(const matrix &x){ return *this = *this * x; }

    friend matrix pow(matrix m, int t)
    {
        matrix re(m.s);
        for (int i = 0; i < re.s; ++i)
            re.t[i][i] = 1;
        while (t)
        {
            if (t & 1) re *= m;
            t >>= 1; m *= m;
        }
        return re;
    }

    friend ostream &operator <<(ostream &out, const matrix &x)
    {
        for (int i = 0; i < x.s; ++i)
            for (int j = 0; j < x.s; ++j)
                out << x.t[i][j] << " \n"[j == x.s - 1];
        return out;
    }
};

int main()
{
    int n = 0;
    long long p[2][2] = {{3, 1}, {-1, 0}}, q[2][2] = {{2, 1}, {0, 0}};
    matrix ans(2);
    memcpy(ans.t, q, sizeof ans.t);
    while (cin >> n, n)
    {
        if (n & 1 || n < 8)
        {
            puts("0"); continue;
        }
        matrix mat(2);
        memcpy(mat.t, p, sizeof mat.t);
        mat = ans * pow(mat, n / 2 - 3);
        cout << (mat.t[0][0] - (n / 2) + 1 + mod) % mod << '\n';
    }
}