acwing1217. 垒骰子

题目

题解

• f[i][j]表示前i个骰子中，朝上的骰子数为j的个数
• 由于重叠的骰子上下两个面互斥，需要将这两个面的数量除去。
• 除此之外，每种情况都有四种不同的排列方法

#include<iostream>
#include<cstring>
using namespace std;
const int N=6,mod=1e9+7;
int n,m;
int get_op(int x){
    if(x>=3)return x-3;
    else return x+3;
}
void mul(int c[][N],int a[][N],int b[][N]){
    int t[N][N];
    memset(t,0,sizeof t);
    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]+(long long)a[i][k]*b[k][j])%mod;
            }
        }
    }
    memcpy(c,t,sizeof t);
}
int main(){
    cin>>n>>m;
    int a[N][N];
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            a[i][j]=4;
    while(m--){
        int x,y;
        cin>>x>>y;
        x--,y--;
        a[x][get_op(y)]=0;//x和y的对面互斥
        a[y][get_op(x)]=0;//y和x的对面互斥
    }
    int f[N][N]={4,4,4,4,4,4};
    for(int k=n-1;k;k>>=1){
        if(k&1)mul(f,f,a);
        mul(a,a,a);
    }
    int res=0;
    for(int i=0;i<N;i++)res=(res+f[0][i])%mod;
    cout<<res<<endl;
    
    
    return 0;
}