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

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

【递推+矩阵快速幂】

Solution 1:

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