[蓝桥杯 2020 国 B] 质数行者 题解

发布于 2023-03-15  466 次阅读

[蓝桥杯 2020 国 B] 质数行者

题目背景

小蓝在玩一个叫质数行者的游戏。

题目描述

游戏在一个 $n \times m \times w$ 的立体方格图上进行, 从北到南依次标号为第 $1$ 行到 第 $n$ 行, 从西到东依次标号为第 $1$ 列到第 $m$ 列, 从下到上依次标号为第 $1$ 层到 第 $w$ 层。

小蓝要控制自己的角色从第 $1$ 行第 $1$ 列第 $1$ 层移动到第 $n$ 行第 $m$ 列第 $w$ 层。每一步, 他可以向东走质数格、向南走质数格或者向上走质数格。每走到 一个位置, 小蓝的角色要稍作停留。

在游戏中有两个陷阱, 分别为第 $r{1}$ 行第 $c{1}$ 列第 $h{1}$ 层和第 $r{2}$ 行第 $c{2}$ 列第 $h{2}$ 层。这两个陷阱的位置可以跨过, 但不能停留。也就是说, 小蓝不能控制角 色某一步正好走到陷阱上，但是某一步中间跨过了陷阱是允许的。

小蓝最近比较清闲, 因此他想用不同的走法来完成这个游戏。所谓两个走法不同, 是指小蓝稍作停留的位置集合不同。

请帮小蓝计算一下，他总共有多少种不同的走法。

提示：请注意内存限制, 如果你的程序运行时超过内存限制将不得分。

输入格式

输入第一行包含两个整数 $n, m, w$, 表示方格图的大小。

第二行包含 $6$ 个整数, $r{1}, c{1}, h{1}, r{2}, c{2}, h{2}$ ，表示陷阱的位置。

输出格式

输出一行, 包含一个整数, 表示走法的数量。答案可能非常大, 请输出答 案除以 $1000000007$（即 $10^9+7$） 的余数。

样例 #1

样例输入 #1

5 6 1
3 4 1 1 2 1

样例输出 #1

11

提示

【样例说明】

用 $(r, c, h)$ 表示第 $r$ 行第 $c$ 列第 $h$ 层, 可能的走法有以下几种:

  1. $(1,1,1)-(1,3,1)-(1,6,1)-(3,6,1)-(5,6,1)$ 。

  2. $(1,1,1)-(1,3,1)-(3,3,1)-(3,6,1)-(5,6,1)$ 。

  3. $(1,1,1)-(1,3,1)-(3,3,1)-(5,3,1)-(5,6,1)$ 。

  4. $(1,1,1)-(3,1,1)-(3,3,1)-(3,6,1)-(5,6,1)$ 。

  5. $(1,1,1)-(3,1,1)-(3,3,1)-(5,3,1)-(5,6,1)$ 。

  6. $(1,1,1)-(3,1,1)-(5,1,1)-(5,3,1)-(5,6,1)$ 。

  7. $(1,1,1)-(3,1,1)-(5,1,1)-(5,4,1)-(5,6,1)$ 。

  8. $(1,1,1)-(1,4,1)-(1,6,1)-(3,6,1)-(5,6,1)$ 。

  9. $(1,1,1)-(1,6,1)-(3,6,1)-(5,6,1)$ 。

  10. $(1,1,1)-(3,1,1)-(3,6,1)-(5,6,1)$ 。

  11. $(1,1,1)-(3,1,1)-(5,1,1)-(5,6,1)$ 。

【评测用例规模与约定】

对于 $30 \%$ 的评测用例 $1 \leq n, m, w \leq 50$ 。

对于 $60 \%$ 的评测用例 $1 \leq n, m, w \leq 300$ 。

对于所有评测用例, $1 \leq n, m, w \leq 1000,1 \leq r{1}, r{2} \leq n, 1 \leq c{1}, c{2} \leq m$, $1 \leq h{1}, h{2} \leq w$, 陷阱不在起点或终点, 两个陷阱不同。

蓝桥杯 2020 年国赛 B 组 J 题。

题解

30 pts

这是我惟一能想出来的解法了，开一个三维数组f[x][y][z]表示走到x列，y行，z层时的方法数，数组开不了太大，最多300，但是luogu上60%的数据会TLE，我们使用埃氏筛，筛出300之内的所有质数，然后我们枚举质数k，方程式如下

$$f[x][y][z] = f[x][y][z] + f[x-k][y][z] + f[x][y-k][z]+f[x][y][z-k]$$

#include <iostream>
#include <vector>
using namespace std;

const int maxn = 301, mod = 1000000007;
int f[maxn][maxn][maxn] = {}, n, m, w, r1, c1, h1, r2, c2, h2;

vector<int> num; // 存储质数
int c[maxn] = {1, 1};
void seive()
{
    for (int i = 2; i <= maxn; i++)
        for (int j = i + i; j <= maxn; j += i)
            c[j] = 1;

    for (int i = 2; i <= maxn; i++) // 生成质数数组
        if (!c[i])
            num.push_back(i);
}

int main()
{
    seive();
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> w >>
        r1 >> c1 >> h1 >>
        r2 >> c2 >> h2;

    f[1][1][1] = 1;
    for (register int y = 1; y <= n; y++)
    {
        for (register int x = 1; x <= m; x++)
        {
            for (register int z = 1; z <= w; z++)
            {
                if ((x == c1 and y == r1 and z == h1) or (x == c2 and y == r2 and z == h2))
                    continue;
                for (auto i : num)
                {
                    if (x - i > 0)
                        f[x][y][z] = f[x][y][z] % mod + f[x - i][y][z] % mod;
                    if (y - i > 0)
                        f[x][y][z] = f[x][y][z] % mod + f[x][y - i][z] % mod;
                    if (z - i > 0)
                        f[x][y][z] = f[x][y][z] % mod + f[x][y][z - i] % mod;
                    f[x][y][z] = f[x][y][z] % mod;
                }
            }
        }
    }
    cout << f[m][n][w] % mod;
    return 0;
}

100 pts

因为直接开三维数组不太现实，我们可以忽略陷阱，直接考虑一维的情况，我们开一个数组$dp[i][k]$表示走到第i个位置，已经走了k步的方法数，我们枚举质数$j$则有

$$dp[i][k] = dp[i][k] + d[i-j][k-1]$$

因为我们只要求方法数即可，不要求输出路径，在忽略陷阱的情况下，这个数组在三个维度下是通用的。

之后我们只要将两个维度的方法数相乘，就可以把一维化成二维的情况。

例如我们在x轴上走到n位置的方法数为A，y轴上走到m位置的方法数为B，总共是$dp[n][A] \times dp[m][B] \times C_{A+B}^{A} $种方法，因此为了加快速度，我们还要预处理组合数数组$c[i][j]$。

我们再开一个数组$f[i+j]$，表示x轴走了i步，y轴走了j步时的方法数。

$$f[i + j] = f[i + j] + dp[n][i] \times dp[m][j] \times c[i + j][j]$$

有了二维的方程式，三维的情况我们直接统计答案就行。

$$ans = ans + f[i] \times dp[w][j] \times c[i + j][j]$$

我们还要考虑陷阱，这里使用容斥原理，我们只需要终点的方案数减去起点到陷阱的方案数和陷阱到终点的方法数即可。

此外，还会有一种情况是同时经过两个陷阱，这种情况只存在于一个陷阱的坐标全大于另一个陷阱的坐标，这样的话就减多了，我们在加回来就行。

因为在进行减法和取模的时候，答案可能为负，所以最后输出的时候加上模数再取模就行

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1505, mod = 1000000007;
long long f[maxn] = {}, dp[maxn][maxn] = {};
int n, m, w, r1, c1, h1, r2, c2, h2;

vector<long long> num; // 存储质数
int a[maxn] = {1, 1}, c[maxn][maxn] = {};
void init()
{
    for (int i = 2; i <= maxn; i++)
        for (int j = i + i; j <= maxn; j += i)
            a[j] = 1;

    for (int i = 2; i <= maxn; i++) // 生成质数数组
        if (!a[i])
            num.push_back(i);

    // 预处理组合数数组
    for (int i = 0; i <= 1500; i++)
        for (int j = 0; j <= 1000; j++)
        {
            if (!j)
                c[i][j] = 1;
            else
                c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
        }
}

long long DP(int n, int m, int w)
{
    int nn = n >> 1, mm = m >> 1, ww = w >> 1;
    long long ans = 0;
    memset(f, 0, sizeof(f));
    for (int i = 0; i <= nn; i++)
        for (int j = 0; j <= mm; j++)
            f[i + j] = (f[i + j] % mod + (dp[n][i] % mod * dp[m][j] % mod * c[i + j][j] % mod) % mod) % mod;
    // 将一维合并成二维

    for (int i = 0; i <= nn + mm; i++)
        for (int j = 0; j <= ww; j++)
            ans = (ans % mod + (f[i] % mod * dp[w][j] % mod * c[i + j][j] % mod) % mod) % mod;
    // 将二维合并成三维
    return ans;
}

int main()
{
    init();
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> w >>
        r1 >> c1 >> h1 >>
        r2 >> c2 >> h2;

    // 计算单个维度中所有可能的状态
    int max_n = max(n, max(m, w));
    dp[1][0] = 1;
    for (int i = 2; i <= max_n; i++)
    {
        for (auto j : num)
        {
            if (j >= i)
                break;
            for (int k = 1; k <= i >> 1; k++)
                dp[i][k] = (dp[i][k] % mod + dp[i - j][k - 1] % mod) % mod;
        }
    }

    long long ans = DP(n, m, w) % mod;
    // 容斥原理
    ans = (ans - DP(r1, c1, h1) % mod * DP(n - r1 + 1, m - c1 + 1, w - h1 + 1) % mod) % mod;
    ans = (ans - DP(r2, c2, h2) % mod * DP(n - r2 + 1, m - c2 + 1, w - h2 + 1) % mod) % mod;

    // 减多了
    if (r1 >= r2 && c1 >= c2 && h1 >= h2)
        ans += DP(r2, c2, h2) * DP(r1 - r2 + 1, c1 - c2 + 1, h1 - h2 + 1) % mod * DP(n - r1 + 1, m - c1 + 1, w - h1 + 1) % mod;
    else if (r1 <= r2 && c1 <= c2 && h1 <= h2)
        ans += DP(r1, c1, h1) * DP(r2 - r1 + 1, c2 - c1 + 1, h2 - h1 + 1) % mod * DP(n - r2 + 1, m - c2 + 1, w - h2 + 1) % mod;
    cout << (ans % mod + mod) % mod;
    return 0;
}

$end$