当前位置: 首页 > news >正文

30 ACwing 291 蒙德里安的梦想 题解

蒙德里安的梦想

题面

求把 \(N \times M\) 的棋盘分割成若干个 \(1 \times 2\) 的长方形,有多少种方案

例如当 \(N = 2, M = 4\) 时,共有 5 中方案。当 \(N = 2, M = 3\) 时,共有 3 种方案

2411_1.jpg|

\(1 \le N, M \le 11\)

题解

可以先转化一下题意,其实可以转化为放横着方块的合法方案数,如果横着的方块已经放好了,那么要将整个棋盘填满,放竖着的方块也只有一种方案

那么考虑两个问题

怎么判断一个已经放好横块的棋盘是否合法,怎么放横块?

我们放好横块后,只需要对于每一列看连续空格的个数是否都是偶数即可

可以这样放横块,设 \(f(i,j)\) 表示已经放好了前 \(i - 1\) 列,从 \(i - 1\) 列到第 \(i\) 列的横块的集合为 \(j\) 的方案数

因为只有 \(1 \times 2\) 的横块,所以我们只需要考虑 \(i - 2 \to i - 1\) 是如何放的,会不会影响到当前这列的状态

设当前状态为 \(j\) ,前面的状态为 \(k\) ,两个状态一定不能有交集,也就是 \(j \& k = 0\)

另外,如果 \(k, j\) 的状态都确定了,那么第 \(i - 1\) 列的状态也就确定了,又因为我们要保证每一列的连续空格数是否为偶数,所以我们还需要判断一下 \(j \mid k\) 这个状态

朴素写法是 \(O(n^24^n)\) 的,会TLE

所以我们加些预处理,具体的时间复杂度多少我也不知道,会很低

code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>using namespace std;typedef long long ll;const int N = 13, M = (1 << 11) + 7;int n, m;
ll f[N][M];
bool st[M];
vector <int> fac[M];void solve () {memset (st, 0, sizeof st);for (int i = 0; i < (1 << n); i ++) {while (fac[i].size ()) fac[i].pop_back ();}//预处理出合法的匹配状态for (int i = 0; i < (1 << n); i ++) {int cnt = 0, ok = 1;for (int k = 0; k < n; k ++) {if ((i >> k) & 1) {if (cnt & 1) ok = 0;cnt = 0;} else {cnt ++;}}if (cnt & 1) ok = 0;st[i] = ok;}for (int i = 0; i < (1 << n); i ++) {for (int j = 0; j < (1 << n); j ++) {if (i & j) continue;if (st[i | j]) {fac[i].push_back (j);}}}//dp转移memset (f, 0, sizeof f);f[0][0] = 1;for (int i = 1; i <= m; i ++) {for (int j = 0; j < (1 << n); j ++) {for (auto k : fac[j]) {f[i][j] += f[i - 1][k];}}}cout << f[m][0] << endl;
}int main () {while ((cin >> n >> m) && (n || m)) {solve ();}return 0;
}
http://www.hskmm.com/?act=detail&tid=25027

相关文章:

  • 21 ACwing 289 环路运输 题解
  • 26 UVA1630 串折叠 Folding 题解
  • 13 ACwing 283 Polygon 题解
  • 12 ACwing 282 石子合并 题解
  • 11 ACwing 281 Coins 题解
  • 某中心科学家荣获多项计算机技术大奖
  • FFT
  • 4 ACwing 274 Mobile Service 题解
  • 3 ACwing 273 Making the Grade 题解
  • 1 ACwing 271 Mr
  • 2 ACwing 272 LCIS 最长公共上升子序列 题解
  • 用 Haxe 实现英文数字验证码识别
  • 出题四
  • 7 2025 07 15 模拟赛题解
  • 使用 OCaml 实现验证码识别
  • 私有云大数据部署:从开发到生产(Docker、K8s、HDFS/Flink on K8s) - 详解
  • 差分约束模板
  • 17 LCA模拟赛1T2 剧院始于演员 题解
  • 3 2025 04 23 模拟赛总结
  • 14 收心赛3 T1 最长不降子序列 题解
  • 16 LCA模拟赛1T1 密码 题解
  • 吴恩达深度学习课程一:神经网络和深度学习 第二周:神经网络基础(一)
  • 阿里开源规则引擎QLExpress
  • QOJ7411 Bitwise Xor
  • 完整教程:SOC-ESP32S3部分:25-HTTP请求
  • 为什么要采用“接口 - 抽象类 - 实现类”这种三层结构? - 浪矢
  • 对外提供 AI 服务的风险:合规视角与 AI 安全围栏落地指南
  • VScode C/C++ 汉化 竞赛版 只需下载扩展 (超简单)
  • 网络安全工具与社区讨论月报
  • 机器人运动未来与人机交互研究