—— Summon, Light!
0%

2015年蓝桥杯省赛C/C++ A组 垒骰子

发表于 更新于 Valine：

9. 垒骰子

赌圣atm晚年迷恋上了垒骰子，就是把骰子一个垒在另一个上边，不能歪歪扭扭，要垒成方柱体。
经过长期观察，atm发现了稳定骰子的奥秘：有些数字的面贴着会互相排斥！
我们先来规范一下骰子：1 的对面是 4，2 的对面是 5，3 的对面是 6。
假设有 m 组互斥现象，每组中的那两个数字的面紧贴在一起，骰子就不能稳定的垒起来。
atm想计算一下有多少种不同的可能的垒骰子方式。
两种垒骰子方式相同，当且仅当这两种方式中对应高度的骰子的对应数字的朝向都相同。
由于方案数可能过多，请输出模 10^9 + 7 的结果。
不要小看了 atm 的骰子数量哦～

「输入格式」
第一行两个整数 n m
n表示骰子数目
接下来 m 行，每行两个整数 a b ，表示 a 和 b 数字不能紧贴在一起。

「输出格式」
一行一个数，表示答案模 10^9 + 7 的结果。

「样例输入」
2 1
1 2

「样例输出」
544

「数据范围」
对于 30% 的数据：n <= 5
对于 60% 的数据：n <= 100
对于 100% 的数据：0 < n <= 10^9, m <= 36

资源约定：
峰值内存消耗 < 256M
CPU消耗 < 2000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include ， 不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。

这道题首先要会递推的做法。
很自然的，我们可以用$f[i][j]$表示垒了$i$个骰子，并且最上面的骰子$j$面朝上。
那么递推式就是$$f[i][j]=\sum_{k=1}^{6} f[i-1][k]\quad coop[op[j]][k]$$
其中$op[j]$表示$j$的背面，$coop[op[j]][k]$就表示$j$的背面是可以跟$k$放在一起的。
这样每次没有讨论侧面的朝向，所以最后乘以$4^n$。
如果想要实现的好的话还要使用滚动数组 滚动数组资料

放一个搜到的代码吧。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
using namespace std;

// ...冲突记录: Compact[i][j]=false代表点数为i的面与点数为j的面存在冲突
bool Compact[7][7];

// ...Parner[i]=j代表 点数为i的面 的对立面点数为j
const int Parner[7]={ 0,4,5,6,1,2,3 };
const long long MOD = 1000000007;

int main(int argc, char** argv)
{
    long long  N; // 骰子高度
    int M; // 冲突组数
    int s1,s2;
    cin >> N >> M;
    for( int i = 0; i < 7; ++i)
        for( int j = 0; j < 7;++j)
            Compact[i][j]=true;

    for( int i = 0; i < M; ++i ) {
        cin >> s1 >> s2;
        // ...点数为s1的面与点数为s2的面存在冲突
        Compact[s1][s2] = Compact[s2][s1] = false;
    }
    long long dp[2][7]; // 滚动数组
    long long C = 4;
    int e = 0;          // 滚动标志
    for( int i = 1; i < 7; ++i )
        dp[e][i] = 1;

    // dp[i][j]代表高度为i的,顶面点数为j的叠骰子方案数
    // 在这里忽略每个骰子可以四面转向的情况, 把该情况留到最后乘上去就可以了
    int j,k;
    for( long long i = 2; i <= N; ++i ){
        e = 1-e;    // ...滚动处理
        C = (C*4)%MOD;
        for( j = 1; j < 7; ++j ){
            dp[e][j] = 0;
            for( k = 1; k < 7; ++k)
                if( Compact[ Parner[j] ][k] )
                    dp[e][j] += dp[1-e][k];
            dp[e][j]%=MOD;
        }

    }
    int sum=0;
    for( int i = 1; i < 7; ++i)
        sum = (sum+dp[e][i])%MOD;
    sum = (sum*C)%MOD;
    cout << sum;
    return 0;
}

核心代码的复杂度$T(n)=36n$，就算给了2s肯定也是不能全通过的，我们需要一个更快的方法。
分析可以发现其实每一步递推对应的关系都是一样的，就是最开始给出的那些关系。
所以我们可以用矩阵来进行递推，再使用快速幂即可 矩阵递推资料

代码用了模板技术，大家凭感觉吧。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MO=1e9+7;
const int opps[]={0,4,5,6,1,2,3};

struct Mat {
    int r,c;
    ll el[10][10];
    Mat() {}
    Mat(ll x) {
        r=c=6;
        memset(el,0,sizeof(el));
        for (int i=1;i<=r;i++) {
            el[i][i]=x;
        }
    }
    Mat(int _r,int _c,ll x) {
        r=_r;c=_c;
        for (int i=1;i<=r;i++) {
            for (int j=1;j<=c;j++) {
                el[i][j]=x;
            }
        }
    }
    Mat operator *(const Mat &b) {
        Mat res(r,b.c,0);
        for (int i=1;i<=r;i++) {
            for (int j=1;j<=b.c;j++) {
                for (int k=1;k<=c;k++) {
                    res.el[i][j]+=el[i][k]*b.el[k][j];
                }
            }
        }
        return res;
    }
    Mat operator %(const int Mo) {
        for (int i=1;i<=r;i++) {
            for (int j=1;j<=c;j++) {
                el[i][j]=el[i][j]%Mo;
            }
        }
        return (*this);
    }
    void print() {
        for (int i=1;i<=r;i++) {
            for (int j=1;j<=c;j++) {
                printf("%I64d ",el[i][j]);
            }
            puts("");
        }
    }
};

template <class DataType>
DataType fpow(DataType x,int n)
{
    DataType res(1);
    while (n) {
        if (n&1) {
            res=x*res%MO;
        }
        x=x*x%MO;
        n>>=1;
    }
    return res;
}

int main()
{
    int n,m;
    Mat coop(6,6,1);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++) {
        int x,y;
        scanf("%d%d",&x,&y);
        coop.el[x][opps[y]]=0;
        coop.el[y][opps[x]]=0;
    }
    coop=fpow(coop,n-1);
    Mat cnt(6,1,1);
    cnt=coop*cnt%MO;
    ll ans=0,fo=4;
    for (int i=1;i<=6;i++) {
        ans=(ans+cnt.el[i][1])%MO;
    }
    ans=ans*fpow(fo,n)%MO;
    printf("%I64d\n",ans);
    return 0;
}
咖啡，亦我所需也