题解：P12891 [蓝桥杯 2025 国 Java B] 瓷砖填充

HZY1618yzh · 2025-06-19 17:47:06 · 题解

~最近~学了 DP，刷一条题练练。
建议大家跟着下面《深进》的图片的做法一起做，实在不会才跟着题解一起想。

题意

给出一个 2\times n 的长方形，每个格子填入 1,5,6 中的一个数字，要求上下左右互质，求一共有多少种填法。

思路

动态规划题，首先应该先确定状态。很明显，该题是求出填完第 n 列一共有多少种填法。可以尝试定义 dp_i，表示填完第 i 列一共有多少种填法。

接着就是转移，可是我们却发现了一个问题，就是题目要求相邻两数互质，转态之间无法直接转移，所以需要重新定义状态。

由于需要保证相邻两数互质，所以需要精确知道当前选的是哪两个数，所以需要多加两维。定义 dp_{z,i,j} 表示正在确定第 z 列、这一列的上面填数 i、下面填数 j，的情况下一共有几种填法。

转移是根据状态确定的。因为 dp 表示当前状态下一共有几种填法，所以转移方程是所有可以与 dp_{z,i,j} 拼接的 dp_{z-1,k,l} 的和。动态转移方程：

dp_{z,i,j}=\sum_{\gcd(i,j)=1\land\gcd(k,l)=1\land\gcd(k,i)=1\land\gcd(l,j)=1\land(i,j,k,l\in {1,5,6})}dp_{z-1,k,l}

不过第二三维最大是 6，达到了 6\times6=36 的空间，所以可以用类似离散化的方法，让 i,j,k,l\in {1,2,3}，表示选第几个数（甚至用 dp_{z,i}(i\in7) 表示 7 种状态。不过为了讲解方便，我们使用刚才的状态）。既然使用了离散化的状态，就需要用 f_{i,j} 数组记录第 i 个数和第 j 个数是否互质。

核心代码

inline bool chek(int x,int y){//检查
    return f[x][y];
}

if(n==1){//加速，提前输出不比计算的东西
    cout<<7;
    return 0;
}
//记录是否互质和初始值
dp[1][1][1]=dp[1][1][2]=dp[1][1][3]=dp[1][2][1]=dp[1][2][3]=dp[1][3][1]=dp[1][3][2]=f[1][1]=f[1][2]=f[1][3]=f[2][1]=f[2][3]=f[3][1]=f[3][2]=1;
for(int z=2;z<=n;z++)//第z列
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)//当前列的选择
            for(int k=1;k<=3;k++)
                for(int l=1;l<=3;l++)//上一列的选择
                    if(chek(k,l)&&chek(k,i)&&chek(l,j)&&chek(i,j))
                        dp[z][i][j]=(dp[z][i][j]+dp[z-1][k][l])%mod;
                        //如果互质则增加答案
for(int i=1;i<=3;i++)
    for(int j=1;j<=3;j++)
        if(chek(i,j))//这行判断其实可以不用，因为不满足 chek(i,j) 的 dp[n][i][j] 是 0
            ans=(ans+dp[n][i][j])%mod;
cout<<ans;//输出

永无止尽的优化

可以发现，dp_1 和 f 的存储内容是一样的可以合并；当 i 和 j 代表的数不互质的情况下，k 和 l 的枚举已经没有意义，可以特判优化掉；这样定义的状态下可以使用矩阵快速幂加速，~不过我不会~……

AC 代码

c++

#include<bits/stdc++.h>
using namespace std;
int n,dp[100001][4][4],ans;
const int mod=1e9+7;
inline bool chek(int x,int y){//检查
return dp[1][x][y];//优化成 dp[1]
}
int main(){
cin>>n;//输入
if(n==1){//加速，提前输出不比计算的东西
    cout<<7;
    return 0;
}
//记录是否互质
dp[1][1][1]=dp[1][1][2]=dp[1][1][3]=dp[1][2][1]=dp[1][2][3]=dp[1][3][1]=dp[1][3][2]=1;
for(int z=2;z<=n;z++)
//第z列，要从 2 开始，不然初始值都会变成 0
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++){//当前列的选择
            if(!chek(i,j)) continue;
            //若当前选择不合法，则后面循环是不是互质
            for(int k=1;k<=3;k++)
                for(int l=1;l<=3;l++){//上一列的选择
                    if(!chek(k,l)) continue;
                    //上一列竖着是不是互质
                    if(!chek(k,i)||!chek(l,j)) continue;
                    //这两行有是不是互质
                    dp[z][i][j]=(dp[z][i][j]+dp[z-1][k][l])%mod;
                    //更新答案
                }
        }
for(int i=1;i<=3;i++)
    for(int j=1;j<=3;j++)
        if(chek(i,j))//检查此状态是否合法（互质）
            ans=(ans+dp[n][i][j])%mod;//增加总答案数量
cout<<ans;//输出
return 0;
}

java

import java.util.Scanner;
public class Main {
    static int n, ans;
    static int[][][] dp = new int[100001][4][4];
    static final int mod = (int)1e9 + 7;
    // 检查
    static boolean chek(int x, int y) {
        return dp[1][x][y] == 1; // 优化成 dp[1]
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt(); // 输入
        if (n == 1) { // 加速，提前输出不比计算的东西
            System.out.println(7);
            return;
        }
        // 记录是否互质
        dp[1][1][1] = dp[1][1][2] = dp[1][1][3] = dp[1][2][1] = dp[1][2][3] = dp[1][3][1] = dp[1][3][2] = 1;
        for (int z = 2; z <= n; z++) {
            // 第z列，要从 2 开始，不然初始值都会变成 0
            for (int i = 1; i <= 3; i++) {
                for (int j = 1; j <= 3; j++) { // 当前列的选择
                    if (!chek(i, j)) continue;
                    // 若当前选择不合法，则后面循环是不是互质
                    for (int k = 1; k <= 3; k++) {
                        for (int l = 1; l <= 3; l++) { // 上一列的选择
                            if (!chek(k, l)) continue;
                            // 上一列竖着是不是互质
                            if (!chek(k, i) || !chek(l, j)) continue;
                            // 这两行有是不是互质
                            dp[z][i][j] = (dp[z][i][j] + dp[z - 1][k][l]) % mod;
                            // 更新答案
                        }
                    }
                }
            }
        }
        for (int i = 1; i <= 3; i++) {
            for (int j = 1; j <= 3; j++) {
                if (chek(i, j)) // 检查此状态是否合法（互质）
                    ans = (ans + dp[n][i][j]) % mod; // 增加总答案数量
            }
        }
        System.out.println(ans); // 输出
    }
}

代码来之不易，点个赞再走也不迟~