AcWing 1217. 垒骰子
原题链接
中等
作者:
geats兔
,
2024-04-05 22:26:11
,
所有人可见
,
阅读 2
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const int N=6;
int A[N][N];
int n,m;
int get_op(int a){
if(a>2) return a-3;
else return a+3;
}
void mul(int c[][N],int a[][N],int b[][N]){
static int temp[N][N];
memset(temp,0,sizeof temp);
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])%MOD;
memcpy(c,temp,sizeof temp);
}
int main(){
cin>>n>>m;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
A[i][j]=4;
while(m--){
int a,b;
cin>>a>>b;
a--,b--;
A[a][get_op(b)]=0;
A[b][get_op(a)]=0;
}
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;
}
ll res=0;
for(int i=0;i<N;i++)
res=(res+f[0][i])%MOD;
cout<<res<<endl;
return 0;
}