朴素写法
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#define endl '\n'
#define int long long
using namespace std;
const int M = 40;
const int MOD = 1e9 + 7;
int f[2][10];
int st[10][10];
int n, m;
int op(int x)
{
if (x <= 3)
{
return x + 3;
}
else
{
return x - 3;
}
}
signed main(void)
{
std::ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int a, b;
cin >> a >> b;
st[a][b] = st[b][a] = true;
}
for (int i = 1; i <= 6; i++)
{
f[1][i] = 4;
}
for (int i = 2; i <= n; i++)
{
for (int j = 1; j <= 6; j++)
{
f[i & 1][j] = 0;
int u = op(j);
for (int k = 1; k <= 6; k++)
{
if (!st[k][u])
{
f[i & 1][j] = (f[i & 1][j] + 4 * f[(i - 1) & 1][k]) % MOD;
}
}
}
}
int res = 0;
for (int i = 1; i <= 6; i++)
{
res = (res + f[n & 1][i]) % MOD;
}
cout << res << endl;
return 0;
}
矩阵快速幂
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#define endl '\n'
#define int long long
using namespace std;
const int N = 6;
const int MOD = 1e9 + 7;
int st[N][N];
int a[N][N];
int n, m;
int op(int x)
{
if (x <= 2)
{
return x + 3;
}
else
{
return x - 3;
}
}
void mul(int c[N][N], int a[N][N], int b[N][N])
{
int t[N][N] = {0};
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
for (int k = 0; k < N; k++)
{
t[i][j] = (t[i][j] + a[i][k] * b[k][j]) % MOD;
}
}
}
memcpy(c, t, sizeof(t));
}
signed main(void)
{
std::ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int x, y;
cin >> x >> y;
x--, y--;
st[x][op(y)] = st[y][op(x)] = true;
}
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (!st[i][j])
{
a[i][j] = 4;
}
}
}
int f[N][N] = {4, 4, 4, 4, 4, 4};
n--;
while (n)
{
if (n & 1)
{
mul(f, f, a);
}
mul(a, a, a);
n >>= 1;
}
int ans = 0;
for (int i = 0; i < N; i++)
{
ans = (ans + f[0][i]) % MOD;
}
cout << ans << endl;
return 0;
}