P8624 [蓝桥杯 2015 省 AB] 垒骰子

这道题的数据范围比较突出：

1<=N<=1e9

先写一个O(N)算法：

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;

const int mod = 1e9 + 7;

int n, m, g[8][8], f[8], op[8], bf[8];



signed main()
{
    op[1] = 4;
    op[4] = 1;
    op[2] = 5;
    op[5] = 2;
    op[3] = 6;
    op[6] = 3;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        g[x][y] = g[y][x] = 1;
    }
    for(int i = 1; i <= 6; i++)
        f[i] = 4;
    for (int i = 2; i <= n; i++)
    {
        memcpy(bf, f, sizeof(f));
        for (int j = 1; j <= 6; j++)
        {
            int op_j = op[j], tmp = 0;
            for(int k = 1; k <= 6; k++)
            {
                int p = (1 - g[op_j][k]) * 4;
                tmp = (tmp + p * bf[k]) % mod;
                f[j] = tmp;
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= 6; i++)
        ans = (ans + f[i]) % mod;
    cout << ans << endl;
    system("pause");
    return 0;
}

f[i][j]表示：高度为i层，且最顶上的骰子数字j朝上的方案数。

一开始受到ACwing中用spfa算法求右边数限制的最短路那道题的影响，陷入了定势思维，

把dp的转移方程写成了

for (int i = 2; i <= n; i++)
    {
        memcpy(bf, f, sizeof(f));
        for (int j = 1; j <= 6; j++)
        {
            int op_j = op[j];
            int &tmp = f[j];
            for(int k = 1; k <= 6; k++)
            {
                int p = (1 - g[op_j][k]) * 4;
                tmp = (tmp + p * bf[k]) % mod;
            }
        }
    }

仔细观察就能发现，这样子会导致f[j]被多次累加更新，导致计算值远大于实际值。

（如果用的是二维数组这么写没有问题，但这道题因为省掉了一维数组，所以必须要借助一个临时变量）