铺砖块

题目

给你一个 $N\times M$ 的地板，你需要用 $1\times 2$和$2\times 1$ 的砖块密铺它，问：有多少种方案（答案 $bmod998,244,353$。）。

$N,M(N\le 1000,M\le 15)$

填表 100 分

总耗时：3863ms

如果每次加法后直接取模会退化成超时 70 分

如果每次加法后用 if 判断以及减法，总耗时 5626ms

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1000;
const int MAXM = 15;
const int MOD = 998244353;
int n, m;
// g[sta] 存所有可以达成 sta 状态的 pre
vector<int> g[(1 << MAXM)];
// dfs 预处理 g 数组
// 当前行状态为 sta(0~m-1)，当前看第 pos 个位置，目前下一行被变成了 nxt
void dfs(int sta, int pos, int nxt)
{
    // 0~m-1 这些位置都安置好了，说明 sta 铺满可以达成 nxt
    if (pos == m)
    {
        g[nxt].push_back(sta);
        return;
    }
    // 当前位置有东西就直接看下一个位置
    if (sta & (1 << pos))
    {
        dfs(sta, pos + 1, nxt);
        return;
    }
    // 现在当前位置肯定没东西，先竖着放一个
    dfs(sta, pos + 1, nxt + (1 << pos));
    // 下一个位置如果也是空的，那么可以横着放一个
    if (pos + 1 < m &&
        !(sta & (1 << (pos + 1))))
        dfs(sta, pos + 2, nxt);
}
int f[MAXN + 5][1 << MAXM];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int sta = 0; sta <= (1 << m) - 1; sta++)
        dfs(sta, 0, 0);
    f[1][0] = 1;
    for (int i = 2; i <= n + 1; i++)
        for (int sta = 0; sta <= (1 << m) - 1; sta++)
        {
            for (int pre : g[sta])
                f[i][sta] += f[i - 1][pre];
            f[i][sta] %= MOD;
        }
    // 注意 f[n][(1<<m)-1] 不是正确答案
    // 比如第 n 行有连续两个的空位也是对的
    cout << f[n + 1][0];
    return 0;
}

刷表 100 分

总耗时：1467ms

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1000;
const int MAXM = 15;
const int MOD = 998244353;
int n, m;
// g[sta] 存所有 sta 可以达成状态的 nxt
vector<int> g[(1 << MAXM)];
// dfs 预处理 g 数组
// 当前行状态为 sta(0~m-1)，当前看第 pos 个位置，目前下一行被变成了 nxt
void dfs(int sta, int pos, int nxt)
{
    // 0~m-1 这些位置都安置好了，说明 sta 铺满可以达成 nxt
    if (pos == m)
    {
        g[sta].push_back(nxt);
        return;
    }
    // 当前位置有东西就直接看下一个位置
    if (sta & (1 << pos))
    {
        dfs(sta, pos + 1, nxt);
        return;
    }
    // 现在当前位置肯定没东西，先竖着放一个
    dfs(sta, pos + 1, nxt + (1 << pos));
    // 下一个位置如果也是空的，那么可以横着放一个
    if (pos + 1 < m &&
        !(sta & (1 << (pos + 1))))
        dfs(sta, pos + 2, nxt);
}
int f[MAXN + 5][1 << MAXM];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int sta = 0; sta <= (1 << m) - 1; sta++)
        dfs(sta, 0, 0);
    f[1][0] = 1;
    for (int i = 1; i <= n; i++)
        for (int sta = 0; sta <= (1 << m) - 1; sta++)
        {
            if (!f[i][sta])
                continue;
            f[i][sta] %= MOD;
            for (int nxt : g[sta])
                f[i + 1][nxt] += f[i][sta];
        }
    // 注意 f[n][(1<<m)-1] 不是正确答案
    // 比如第 n 行有连续两个的空位也是对的
    cout << f[n + 1][0] % MOD;
    return 0;
}