题目描述
dp:
状态表示:
f[i][j]
集合:使用i个骰子,且顶上那一面是数字j的所有方案数
属性:有多少种方案
状态计算:
以第i-1个骰子最上面的数字是1,2,3,4,5,6分类
如果不考虑会排斥,第i个骰子最上面是k,f[i][k]=4f[i-1][1]+4f[i-1][2]+…+4*f[i-1][6]
然而会有排斥,就不乘以4,乘以0
f[i][1,2,3,4,5,6]==F[i],f[i-1][1,2,3,4,5,6]==F[i-1]
F[i]=F[i-1]*a[][]//构造矩阵
如果最上面一层数字i朝上,倒数第二层数字j朝上,j对面是op[j],如果j和op[i]不排斥,st[j][op[i]]!=true
则a[j][i]就是4,如果st[j][op[i]]==true,那么a[j][i]就是0
f[i]=f[1]*a[][]的n-1次方,用快速幂运算计算出a[][]的n-1次方
f1[6]=[f[1][1],f[1][2],f[1][3],f[1][4],f[1][5],f[1][6]]={4,4,4,4,4,4}
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m;
int op[7]={0,4,5,6,1,2,3};//每个数对面值,1->4,2->5,3->6
const int N = 7,mod = 1e9+7;
bool st[N][N];//st[i][j]=true,表示i和j相互排斥
typedef long long LL;
void mul(int c[],int a[],int b[][N])
{
int temp[N]={0};
for(int i=1;i<=6;i++)
{
for(int j=1;j<=6;j++)
{
temp[i]=(temp[i]+(LL)a[j]*b[j][i])%mod;
}
}
memcpy(c,temp,sizeof temp);
}
void mul(int c[][N],int a[][N],int b[][N])
{
int temp[N][N]={0};
for(int i=1;i<=6;i++)
{
for(int j=1;j<=6;j++)
{
for(int k=1;k<=6;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<m;i++)
{
int a,b;
cin>>a>>b;
st[a][b]=st[b][a]=true;
}
int a[N][N];//存矩阵
for(int i=1;i<=6;i++)//i代表f[I][i],第I个骰子最上一面是数字i
{
for(int j=1;j<=6;j++)//j代表f[I][j],第I-1个骰子最上一面是j
{
if(st[j][op[i]]) a[j][i]=0;
else a[j][i]=4;
}
}
int f1[N]={0,4,4,4,4,4,4};
int k=n-1;
while(k)
{
if(k&1) mul(f1,f1,a);//f1=f1*a
mul(a,a,a);
k>>=1;
}
int res=0;
for(int i=1;i<=6;i++)
{
res=(res+f1[i])%mod;
}
cout<<res<<endl;
return 0;
}