题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
-
不优化的情况
设状态dp[i][j]:表示前i-1个骰子已经摆好,第i个骰子的下边为j的总数量
在状态转移的时候只需将骰子的上边和下边转换一下就行了
f[i][j] += f[i-1][k>3 ? k-3 : k+3];
最后可以过掉70%的数据,如果是比赛最好这样写,不容易出错。
-
考虑矩阵优化
我们可以发现每次转移的方式是固定的
即 f[i-1][j] += f[i-1][j], k:与1没有冲突的点。
所以我们就可以将他们写成一个矩阵表达
f[i][1] = {a11 a12 a13 a14 a15 a16} f[i-1][1]
f[i][2] = {a21 a22 a23 a24 a15 a26} f[i-1][2]
....
f[i][6] = {a61 a62 a63 a64 a65 a66} f[i-1][6]
aij: 表示i,j有无冲突
之后我们用矩阵快速幂求解n-1次方即可
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
const int mod = 1e9 + 7;
typedef long long LL;
bool vis[10][10];
struct tmp
{
LL x[7][7];
tmp operator *(const tmp &a)
{
tmp t;
for(int i = 1; i <= 6; i++)
{
for(int j = 1; j <= 6; j++)
{
t.x[i][j] = 0;
for(int k = 1; k <= 6; k++)
{
t.x[i][j] = (t.x[i][j] + x[i][k] * a.x[k][j] % mod)%mod;
}
}
}
return t;
}
};
LL qmi(int n)
{
long long a = 4, res = 1;
while(n)
{
if(n&1) res = res*a%mod;
n >>= 1;
a = a * a%mod;
}
return res;
}
tmp qmi1(int m)
{
tmp a,res;
for(int i = 1; i <= 6; i++)
{ for(int j = 1; j <= 6; j++)
{
int t = j;
if(t > 3) t-=3;
else t+=3;
if(vis[i][j]) a.x[i][t] = 1;
else a.x[i][t] = 0;
if(i==j)res.x[i][j] = 1;
else res.x[i][j] = 0;
// cout<<a.x[i][j]<<" ";
}
}
while(m)
{
if(m&1) res = res * a;
m >>= 1;
a = a * a;
}
return res;
}
int main()
{
memset(vis,1,sizeof vis);
int n,m;
cin>>n>>m;
for(int i = 1; i <= m; i++)
{
int a,b;
cin>>a>>b;
vis[a][b] = vis[b][a] = 0;
}
tmp res = qmi1(n-1);
long long ans = 0;
for(int i = 1; i <= 6; i++)
for(int j = 1; j <= 6; j++)
ans = (ans + res.x[i][j])%mod;
cout<<ans*qmi(n)%mod;
return 0;
}