AcWing 1217. 垒骰子
原题链接
中等
作者:
桦_5
,
2024-04-08 22:44:11
,
所有人可见
,
阅读 2
dp过7个数据点
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e7+11,mod=1e9+7;
bool vis[7][7];
int dp[N][7];//dp[i][j]表示已经垒好i个骰子,第i个骰子最上面一面为j的方案数
int n,m;
signed main()
{
cin>>n>>m;
for(int i=1;i<=m;++i)
{
int a,b;cin>>a>>b;
vis[a][b]=vis[b][a]=true;
}
for(int i=1;i<=6;++i)
dp[1][i]=1;
for(int i=1;i<=n;++i)//枚举骰子
for(int j=1;j<=6;++j)//枚举第i个骰子顶面的点数
{
for(int k=1;k<=6;++k)//枚举第i-1个骰子顶面的点数
{
int t=j+3;
if(t!=6)t%=6;
if(vis[t][k])continue;
dp[i][j]=(dp[i][j]+4*dp[i-1][k])%mod;
}
}
int res=0;
for(int i=1;i<=6;++i)
res=(res+dp[n][i])%mod;
cout<<(res*4)%mod;
return 0;
}