solution.cpp

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

vector<int> can[7]; //存can[i]能和哪些点挨着
int up[7] = {1, 1, 1, 1, 1, 1, 1};
int temp[7] = {1};
int k = 4;

const int MOD = 1000000007;

void init() //初始化都可挨着
{
    for (int i = 1; i <= 6; i++)
        for (int j = 1; j <= 6; j++)
            can[i].push_back(j);
}
void dele(int side1, int side2) //删除不可挨着的点
{
    for (vector<int>::iterator it = can[side1].begin(); it != can[side1].end(); it++)
        if (*it == side2)
        {
            can[side1].erase(it);
            break;
        }

    for (vector<int>::iterator it = can[side2].begin(); it != can[side2].end(); it++)
        if (*it == side1)
        {
            can[side2].erase(it);
            break;
        }
}
void fun(int n)
{
    for (int i = 2; i <= n; i++)
    {
        //计算出第i层骰子每种底面的可能次数
        for (int j = 1; j <= 6; j++)
        {
            temp[j] = 0;
            for (vector<int>::iterator it = can[j].begin(); it != can[j].end(); it++)
                temp[j] += up[*it];
        }
        //转化为第i层骰子顶面的可能次数
        up[1] = temp[4] % MOD;
        up[2] = temp[5] % MOD;
        up[3] = temp[6] % MOD;
        up[4] = temp[1] % MOD;
        up[5] = temp[2] % MOD;
        up[6] = temp[3] % MOD;
        //4^n
        k = k * 4;
        k = k % MOD;
    }
    int ans = 0;
    for (int j = 1; j <= 6; j++)
        ans += up[j];
    cout << (ans * k) % MOD;
}
int main(int argc, char **argv)
{
    init();

    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++)
    {
        int side1, side2;
        cin >> side1 >> side2;
        dele(side1, side2);
    }

    fun(n);

    return 0;
}