【2017ACM-ICPC广西邀请赛】Covering

【2017ACM-ICPC广西邀请赛】Covering

【递推+矩阵快速幂】

问题链接:https://vjudge.net/problem/HDU-6185

Solution 1:

这个是需要的思考较少的办法。暴力dfs算出\(n = 1 … 10\)时的answer,之后根据这个找到递推关系式,之后写出变换矩阵,采用矩阵快速幂来解决。

首先是暴力找前10个答案:

#include <iostream>
#include <cstring>
using namespace std;

const int LIM = 10;
bool vis[4][LIM];
int n;
int cnt = 0;

bool find(int & r, int & c) {
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < n; j++) {
            if (!vis[i][j]) {
                r = i;
                c = j;
                return true;
            }
        }
    }
    return false;
}

void bruteDfs() {
    int r, c;
    if (!find(r, c)) {
        cnt++;
        return;
    }
    if (r < 3 && !vis[r + 1][c]) {
        vis[r][c] = vis[r + 1][c] = true;
        bruteDfs();
        vis[r][c] = vis[r + 1][c] = false;
    }
    if (c < n - 1 && !vis[r][c + 1]) {
        vis[r][c] = vis[r][c + 1] = true;
        bruteDfs();
        vis[r][c] = vis[r][c + 1] = false;
    }
}

int main(void) {
    for (n = 1; n <= 10; n++) {
        memset(vis, false, sizeof vis);
        cnt = 0;
        bruteDfs();
        printf("4*%d : %d\n", n, cnt);
    }
    return 0;
}

得到前十组答案:

4*1 : 1
4*2 : 5
4*3 : 11
4*4 : 36
4*5 : 95
4*6 : 281
4*7 : 781
4*8 : 2245
4*9 : 6336
4*10 : 18061

接着就可以使用这几组数据推出递推式,假设每一项与前一项、前两项…前多项有关,手动高斯消元法逐个尝试求解,可以求出递推关系式,还有一种就是继续写程序暴力,发现递推关系式:

暴力求项数代码:

#include <iostream>

using namespace std;

int main(void) {
    for (int a1 = -10; a1 <= 10; a1++) {
        for (int a2 = -10; a2 <= 10; a2++) {
            for (int a3 = -10; a3 <= 10; a3++) {
                for (int a4 = -10; a4 <= 10; a4++) {
                    if (a1 * 1 + a2 * 5 + a3 * 11 + a4 * 36 == 95 &&
                            a1 * 5 + a2 * 11 + a3 * 36 + a4 * 95 == 281 &&
                            a1 * 11 + a2 * 36 + a3 * 95 + a4 * 281 == 781 &&
                            a1 * 36 + a2 * 95 + a3 * 281 + a4 * 781 == 2245) {
                        printf("f(n) = %df(n - 1) + %df(n - 2) + %df(n - 3) + %df(n - 4)\n", a4, a3, a2, a1);
                    }
                }
            }
        }
    }
    return 0;
}

输出:

f(n) = 1f(n - 1) + 5f(n - 2) + 1f(n - 3) + -1f(n - 4)

写成矩阵变换式:

接下来就可以正式编码了。

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;

const LL MOD = 1000000007;
struct Matrix {
    LL v[4][4];
    Matrix operator * (const Matrix & m) const {
        Matrix ret = {{0}};
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                for (int k = 0; k < 4; k++) {
                    ret.v[i][j] += (v[i][k] * m.v[k][j] + MOD) % MOD;       //注意v[i][k] * m.v[k][j]可能会变成负数,需要加上MOD
                    ret.v[i][j] %= MOD;
                }
            }
        }
        return ret;
    }
    void operator *= (const Matrix & m) {
        *this = *this * m;
    }
};
const Matrix base = {{{1, 5, 1, -1}, {1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}}};
LL start[] = {1, 5, 11, 36};

Matrix fastPow(Matrix x, LL pow) {
    Matrix ans = {{{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}}};
    while (pow) {
        if (pow & 1) ans *= x;
        x *= x;
        pow >>= 1;
    }
    return ans;
}

int main(void) {
    ios::sync_with_stdio(false);
    LL n;
    while (cin >> n) {
        if (n <= 4) cout << start[n - 1] << endl;
        else {
            Matrix fac = fastPow(base, n - 4);
            cout << (fac.v[0][0] * start[3]
                    + fac.v[0][1] * start[2]
                    + fac.v[0][2] * start[1]
                    + fac.v[0][3] * start[0]) % MOD << endl;
        }
    }
    return 0;
}

上边那里不加上MOD话,一个出错的例子是,对于输入1000000000,输出会是一个负数。