题目描述

赌圣atm晚年迷恋上了垒骰子，就是把骰子一个垒在另一个上边，不能歪歪扭扭，要垒成方柱体。
经过长期观察，atm 发现了稳定骰子的奥秘：有些数字的面贴着会互相排斥！
我们先来规范一下骰子：1的对面是 4，2的对面是 5，3的对面是6。
假设有 m组互斥现象，每组中的那两个数字的面紧贴在一起，骰子就不能稳定的垒起来。
atm想计算一下有多少种不同的可能的垒骰子方式。
两种垒骰子方式相同，当且仅当这两种方式中对应高度的骰子的对应数字的朝向都相同。
由于方案数可能过多，请输出模 1e9+7的结果。
不要小看了 atm 的骰子数量哦～

「输入格式」
第一行两个整数 n m
n表示骰子数目
接下来 m 行，每行两个整数 a b ，表示 a 和 b 数字不能紧贴在一起。

「输出格式」
一行一个数，表示答案模 10^9 + 7 的结果。

样例

「样例输入」
2 1
1 2


「样例输出」
544

算法1

(dp + 矩阵乘法)

一个骰子的摆放方式是24种 (任意一面朝上侧面都可以旋转四次 4 * 6 = 24)
f[i][j] 表示前i个骰子且第i个骰子数字j朝上

状态转移 f[i][j] = f[i - 1][k] * 4 (侧面可旋转四次) (k从1到6 前i-1个骰子数字k朝上且k不与j的对面互斥)
可用op[j]表示 j 对面的数字, st[k][j]表示两数字是否互斥
应该是下面这样(我没试过......)

for (int j = 1; j <= 6; j ++ )
{
    for (int k = 1; k <= 6; k ++ )
    {
        if (st[k][op[j]]) continue;
        f[i][j] = (f[i][j] + f[i - 1][k] * 4) % mod;
    }
}

数据范围n是1e9铁定超时了......

矩阵乘法
Fn[] = {f[n][1], f[n][2], f[n][3], f[n][4], f[n][5], f[n][6]}
Fn+1[] = {f[n+1][1], f[n+1][2], f[n+1][3], f[n+1][4], f[n+1][5], f[n+1][6]}
目的是找到一个矩阵A 使得Fn+1[] = A * Fn[] 如下

A矩阵构造代码如下, st[]数组作用同上

int a[N][N];
for (int i = 0; i < N; i ++ )
{
    for (int j = 0; j < N; j ++ )
    {
        if (st[j][op[i]]) a[j][i] = 0;
        else a[j][i] = 4;
    }
}

则Fn[] = F1[] * A ^ (n - 1);
结果就是Fn[] 里六个数的和
利用快速幂求出结果

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 6, P = 1e9 + 7;

int n, m;
int op[] = {3, 4, 5, 0, 1, 2};
bool st[N][N];

void mul(int c[], int a[], int b[][N])
{
    int temp[N] = {0};
    for (int i = 0; i < N; i ++ )
    {
        for (int j = 0; j < N; j ++ )
        {
            temp[i] = (temp[i] + (LL)a[j] * b[j][i]) % P;
        }
    }
    memcpy(c, temp, sizeof(temp));
}

void mul(int c[][N], int a[][N], int b[][N])
{
    int temp[N][N] = {0};
    for (int i = 0; i < N; i ++ )
    {
        for (int j = 0; j < N; j ++ )
        {
            for (int k = 0; k < N; k ++ )
            {
                temp[i][j] = (temp[i][j] + (LL)a[i][k] * b[k][j]) % P;
            }
        }
    }

    memcpy(c, temp, sizeof(temp));
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i ++ )
    {
        int a, b;
        cin >> a >> b;
        st[a - 1][b - 1] = st[b - 1][a - 1] = true;
    }

    int f1[N] = {4, 4, 4, 4, 4, 4};
    int a[N][N];
    for (int i = 0; i < N; i ++ )
    {
        for (int j = 0; j < N; j ++ )
        {
            if (st[j][op[i]]) a[j][i] = 0;
            else a[j][i] = 4;
        }
    }

    n -- ;
    while(n)
    {
        if (n & 1) mul(f1, f1, a);
        mul(a, a, a);
        n >>= 1;
    }

    int res = 0;
    for (int i = 0; i < N; i ++ )
    {
        res = (res + f1[i]) % P;
    }
    cout << res;

    return 0;
}