Garlic counter exercise: base dice

Problem description

In his later years, gambler atm was infatuated with base dice, that is, to base dice on top of each other, not crooked, but into square cylinders.
After a long-term observation, atm has discovered the secret of stable Dice: some numbers will repel each other when they are pasted together! Let's normalize the dice: 1 is facing 4, 2 is facing 5, 3 is facing 6. Suppose there are m groups of mutually exclusive phenomenon, the two numbers in each group are close together, the dice can not be stable. atm wants to figure out how many different possible ways to base dice. The two base dice methods are the same, if and only if the corresponding numbers of the dice corresponding to the height in the two methods have the same orientation. Because there may be too many schemes, please output the result of module 10 ^ 9 + 7.
Don't underestimate the number of dice in atm
Input format
In the first line, two integers n(1 ≤ n ≤ 10^9),m(0 ≤ m ≤ 36), n represents the number of dice,
The next m lines, two integers a and b for each line, indicate that a and b numbers cannot stick together.
Output format
A number in a row indicates the result of answer module 10 ^ 9 + 7.
sample input
3 4
1 1
2 2
3 3
4 4
sample output
10880

AC code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <string>
#include <vector>
#include <stack>
#define CLR(a, b) memset(a, (b), sizeof(a))
#define ll o<<1
#define rr o<<1|1
#define fi first
#define se second
using namespace std;
typedef long long LL;
const int MOD = 1e9+7;
void add(LL &x, LL y) {x += y; x %= MOD;}
int a[7] = {0, 4, 5, 6, 1, 2, 3};
struct Matrix {
    LL a[7][7];
};
Matrix multi(Matrix x, Matrix y)
{
    Matrix z; CLR(z.a, 0);
    for(int i = 1; i <= 6; i++)
    {
        for(int k = 1; k <= 6; k++)
        {
            if(x.a[i][k] == 0) continue;
            for(int j = 1; j <= 6; j++)
                add(z.a[i][j], x.a[i][k] * y.a[k][j] % MOD);
        }
    }
    return z;
}
Matrix res, ori;
Matrix Pow(int n)
{
    while(n)
    {
        if(n & 1)
            res = multi(res, ori);
        ori = multi(ori, ori);
        n >>= 1;
    }
}
bool Map[7][7];
LL pow_mod(LL a, int n)
{
    LL ans = 1LL;
    while(n)
    {
        if(n & 1)
            ans = ans * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return ans;
}
int main()
{
    int n, m; scanf("%d%d", &n, &m);
    CLR(Map, false);
    while(m--) {
        int u, v; scanf("%d%d", &u, &v);
        Map[u][v] = Map[v][u] = true;
    }
    CLR(ori.a, 0LL); CLR(res.a, 0LL);
    for(int i = 1; i <= 6; i++) {
        res.a[i][i] = 1LL;
        for(int j = 1; j <= 6; j++) if(!Map[i][a[j]])
            ori.a[i][j]++;
    } Pow(n-1);
    LL ans = 0;
    for(int i = 1; i <= 6; i++)
        for(int j = 1; j <= 6; j++)
            add(ans, res.a[i][j]);
    cout << ans * pow_mod(4, n) % MOD << endl;
    return 0;
}

Posted on Thu, 02 Apr 2020 22:39:05 -0700 by freddyw