0000

用户名：dafei0710

访问量：5712

签　名：

等　　级
排　　名	2484
经　　验	2285
参赛次数	1
文章发表	6
年　　龄	0
在职情况	学生
学　　校	湖北汽车工业学院
专　　业

　　自我简介：

TA的其他文章

[编程入门]数字的处理与判断-题解(C语言代码)
浏览：65

[STL训练]sort练习-题解(C++代码)
浏览：1070

蓝桥杯2015年第六届真题-垒骰子-题解(C++代码)
浏览：784

你可能喜欢

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C++代码）（手动优化一下计算）

蓝桥杯2015年第六届真题-垒骰子-题解(C++代码)

　　作者: 0000　　　　发表时间：2020-03-11 15:08:50 浏览：784　|　评论：0　

原题链接：蓝桥杯2015年第六届真题-垒骰子

直接搜索可以得基础分。

令 f_{i, j} 表示用 i 个骰子，最后一层正面朝上的为 j 的方案数。
由于已知每个面相对的面是哪个面，所以原题的限制相当于：i 和 j 不能相邻 等价于 i 和 j 的对面 不能是相邻两个正面朝上的面。例如，1 和 2 不能相邻表示不能存在相邻两个骰子的正面朝上分别为 1 和 5 ，也不能是 2 和 4 。
这样我们可以写出 f 的转移公式： f_{i + 1, j} = sum_{all possible k} f_{i, k} 。利用这个转移可以写出一个 O(n) 的 dp 。

观察这个转移，我们发现可以用一个矩阵来描述 f_i 到 f_j 。要求 f_n ，我们可以使用矩阵乘法。时间复杂度为 O(log n * 6^3)

####  #include <cstdio>
####  #include <cstring>
using namespace std;

const int D = 6, MOD = 1e9 + 7;

typedef long long int64;
typedef int64 mat[D][D];

mat U, V, I;

void matmul(mat a, mat b, mat c) {
    mat t = {{0}};
    for (int i = 0; i < D; ++i)
        for (int j = 0; j < D; ++j)
            for (int k = 0; k < D; ++k)
                (t[i][j] += a[i][k] * b[k][j]) %= MOD;
    memcpy(c, t, sizeof(t));
}

int main() {
//    freopen("dice.in" , "r", stdin);
//    freopen("dice.out", "w", stdout);

int n, m;
    scanf("%d%d", &n, &m), --n;
    for (int i = 0; i < D; ++i)
        for (int j = 0; j < D; ++j)
            U[i][j] = 4;
    for (int i = 1, a, b; i <= m; ++i) {
        scanf("%d%d", &a, &b), --a, --b;
        U[a][b < 3 ? (b + 3) : (b - 3)] = 0;
        U[b][a < 3 ? (a + 3) : (a - 3)] = 0;
    }
    for (int i = 0; i < D; ++i)
        V[i][i] = 4;

for (; n; n >>= 1, matmul(U, U, U))
        n & 1 ? matmul(V, U, V), 0 : 0;
    int64 ans = 0;
    for (int i = 0; i < D; ++i)
        for (int j = 0; j < D; ++j)
            ans += V[i][j];
    printf("%d\n", (int)(ans % MOD));
    return 0;
}

0.0分

4 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

0000

TA的其他文章

你可能喜欢

字符逆序（C语言代码）

三进制小数（C语言代码）

点我有惊喜！你懂得！

简单的a+b （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C++代码）（手动优化一下计算）

蓝桥杯2015年第六届真题-垒骰子-题解(C++代码)

评论区

精彩推荐

【出圈】（C语言代码）

Pascal三角（C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

关于C语言变量位置的问题

1012题解

A+B for Input-Output Practice (IV) （C语言代码）

输入输出格式练习（C语言代码）

A+B for Input-Output Practice (I) （C语言代码）

素数的个数一直是超时

C语言程序设计教程（第三版）课后习题11.1 （C++代码）

0000

TA的其他文章

你可能喜欢

字符逆序 （C语言代码）

三进制小数 （C语言代码）

点我有惊喜！你懂得！

简单的a+b （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C++代码）（手动优化一下计算）

蓝桥杯2015年第六届真题-垒骰子-题解(C++代码)

评论区

精彩推荐

【出圈】 （C语言代码）

Pascal三角 （C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

关于C语言变量位置的问题

1012题解

A+B for Input-Output Practice (IV) （C语言代码）

输入输出格式练习 （C语言代码）

A+B for Input-Output Practice (I) （C语言代码）

素数的个数 一直是超时

C语言程序设计教程（第三版）课后习题11.1 （C++代码）

字符逆序（C语言代码）

三进制小数（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C++代码）（手动优化一下计算）

　　评论区

【出圈】（C语言代码）

Pascal三角（C语言代码）

输入输出格式练习（C语言代码）

素数的个数一直是超时