题解：P16225 [蓝桥杯 2026 省 A] 量子 2048

· · 题解

题目传送门

这居然是道数学题......

以下是我刚看到题的思路。

拿到题目，我们发现数据范围很小，O(n^2) 的做法时间绰绰有余。可以考虑像过河卒一样 dp 求解。
设 dp_{i,j} 为长为 i，宽为 j 的矩阵全部填满的方案数。

然后就出现了一个问题：只有 1 行或者 1 列时，方案数是多少呢？对此，我的解决方法是将这种情况的方案数全设为 0，从有 2 行或 2 列时开始递推。

然后就可以愉快的开始找状态转移方程了！
首先想到，最后一行或者最后一列的数是没有选择的余地的（要保证每行每列有奇数个 Q）；其次在一个 2\times2 的矩阵中，右下角的数也是没有选择余地的（要保证每一个小矩阵里都有奇数个 Q），因此我们只关注行列数就行了。

其实到这里结论已经很明显了，但是我太蒟了没看出来。

我们能得到一个结论：每在后面添加 1 行或者 1 列，可供选择的方案数都要乘上 2。这是因为什么呢？我们来证明一下。

假设当前一共有 n 行（列），则这一行（列）有选择余地的方格一共有 n-1 个。若行（列）数增加 1，则有选择余地的方格增加一个。又因为每一个方格有两种取值，所以答案要乘以 2。

由此推出状态转移方程：

dp_{i,j}=dp_{i-1,j}\times2 dp_{i,j}=dp_{i,j-1}\times2

此时我还没意识到自己绕了个大圈子。

#include<iostream>
using namespace std;
const int  N = 2050, mod = 998244353;
int dp[N][N];
int main(){
    dp[2][2] = 2;
    for (int i = 2 ; i <= 2048 ; ++i){
        for (int j = 2 ; j <= 2048 ; ++j) {
            dp[i + 1][j] = dp[i][j] * 2 % mod;
            dp[i][j + 1] = dp[i][j] * 2 % mod;
        }   
    }
    cout << dp[2048][2048];
    return 0;
}

AC

os：这不是 dp 板子么。

看完题解直接炸了。

我们根本没有必要挨个枚举，我们完全可以直接算出答案......

更简单的 AcCode：

#include<iostream>
using namespace std;
int main(){
    int ans = 1;    
    for (int i = 1 ; i <= 4093 ; ++i) 
    ans = ans * 2 % 998244353;
    cout << ans;
    return 0;
}