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

UVa 12117 ACM Puzzles

news 2026/8/22 15:16:43

题目描述

ACM\texttt{ACM}ACM（儿童机器协会）计划为儿童设计一种新型拼图。所有拼图的尺寸都是3×N3 \times N3×N，并使用222222种特定的拼图块（某些块可以重复使用）。为了防止假冒产品，ACM\texttt{ACM}ACM生产的拼图在出售时只会保留某些特定的解法。给定NNN（0<N<20010 < N < 20010<N<2001），计算使用给定拼图块可以组成多少种不同的解法。不允许旋转拼图块，但每种块可以使用任意多次。有些块只是其他块的旋转版本，但也不能通过旋转使其变成另一种块。

输入格式

输入文件包含多行，每行一个整数NNN（0<N<20010 < N < 20010<N<2001）。输入以一行单独的000结束。

输出格式

对于每个NNN，输出一行，格式为Case k: ans，其中answer=Smod 1012answer = S \mod 10^{12}answer=Smod1012，SSS是3×N3 \times N3×N拼图的解法总数。

样例输入

5 100 0

样例输出

Case 1: 26 Case 2: 584039302899

题目分析

问题本质

这是一个铺砖问题（Tiling Problem\texttt{Tiling Problem}Tiling Problem）的变种：用222222种给定的、不可旋转的拼图块填满3×N3 \times N3×N的矩形区域。由于NNN最大可达200020002000，需要设计一个高效的动态规划算法。

关键难点

块形状复杂：222222种块形状各异，宽度可能是111、222或333列。
不允许旋转：即使某些块看起来是旋转对称的，也被视为不同的块。
大数取模：结果需要对101210^{12}1012取模，说明结果可能非常大。

解题思路分析

1. 状态定义

观察到拼图块的宽度最多为333列，我们可以采用列轮廓线动态规划的思路。定义状态为：

dp[i][p][q][r]dp[i][p][q][r]dp[i][p][q][r]表示：

已经填充到第iii列
第i+1i+1i+1列的三行分别有ppp、qqq、rrr个格子已被占用（从之前的块延伸过来的部分）
其中p,q,r∈{0,1,2}p, q, r \in \{0, 1, 2\}p,q,r∈{0,1,2}，表示第i+1i+1i+1列有多少个格子已被占据

这个状态表示当前填充的前沿位置以及下一列的“欠债”情况（即有多少格子已经被之前的块占用）。

2. 状态转移

对于每个状态(i,p,q,r)(i, p, q, r)(i,p,q,r)，我们尝试放置222222种拼图块中的一种。每个拼图块被定义为一个3×33 \times 33×3的字符数组，其中：

'*'表示该位置被块占用
' '（空格）表示该位置为空

转移时需要检查：

块的左侧三列是否与当前偏移(p,q,r)(p, q, r)(p,q,r)匹配（即对应位置必须是'*'）
块的左侧不能有额外的填充超出边界
计算放置块后新的偏移量

3. 偏移归一化

放置一个块后，可能会产生新的偏移。为了保持状态空间的大小可控，我们进行偏移归一化：计算新的p′,q′,r′p', q', r'p′,q′,r′值后，将它们减去最小值，使至少一个值为000，其他值在000到222之间。这样状态数量被限制在合理的范围内。

4. 算法流程

初始化dp[0][0][0][0]=1dp[0][0][0][0] = 1dp[0][0][0][0]=1（空棋盘一种方案）
对于每个iii从000到200020002000，遍历所有(p,q,r)(p, q, r)(p,q,r)状态
对于每个状态，尝试放置222222种块中的每一种
检查放置是否合法，计算新状态并更新dpdpdp值
对于输入的NNN，答案就是dp[N][0][0][0]dp[N][0][0][0]dp[N][0][0][0]（完全填满NNN列且无偏移）

5. 复杂度分析

时间复杂度：O(N×33×22)≈O(600N)O(N \times 3^3 \times 22) \approx O(600N)O(N×33×22)≈O(600N)，对于N≤2000N \leq 2000N≤2000可以接受
空间复杂度：O(N×33)≈O(27N)O(N \times 3^3) \approx O(27N)O(N×33)≈O(27N)，可以通过滚动数组优化，但本题NNN较小，直接开数组即可

为什么这种方法有效？

状态压缩：通过偏移量表示未完成的部分，避免了记录整个棋盘状态
完全性：枚举所有块和所有可能的位置，不会遗漏任何合法解
高效性：状态数有限，转移代价小，适合NNN较大的情况

参考代码

// ACM Puzzles// UVa ID: 12117// Verdict: Accepted// Submission Date: 2026-01-30// UVa Run Time: 0.000s//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constll MOD=1000000000000LL;// 22种拼图块的定义charpuzzleBlocks[22][3][4]={{"* ","* ","* "},{"* ","** ","* "},{"** "," * ","** "},{" * ","** ","** "},{" * ","***"," * "},{"** ","* ","** "},{" * ","** "," * "},{" *"," **","** "},{"** "," **"," *"},{" * ","** ","* "},{"* ","** "," * "},{"** ","** ","* "},{"** ","** "," * "},{"** ","* ","* "},{"** "," * "," * "},{" **","** ","* "},{"* ","** "," **"},{"* ","* ","** "},{" * "," * ","** "},{"***"," * "," * "},{" * "," * ","***"},{"* ","** ","** "}};ll dp[2005][3][3][3];// dp[i][p][q][r]voidinitialize(){// 初始化dp数组为0memset(dp,0,sizeof(dp));dp[0][0][0][0]=1;// 起始状态for(inti=0;i<=2000;i++){for(intp=0;p<3;p++)for(intq=0;q<3;q++)for(intr=0;r<3;r++){ll currentVal=dp[i][p][q][r];if(currentVal==0)continue;// 尝试放置22种块中的每一种for(intblockIdx=0;blockIdx<22;blockIdx++){// 检查块左侧三列是否与当前偏移匹配if(puzzleBlocks[blockIdx][0][p]!='*'||puzzleBlocks[blockIdx][1][q]!='*'||puzzleBlocks[blockIdx][2][r]!='*')continue;// 检查左侧是否有额外填充（不能超出边界）if(p>0&&puzzleBlocks[blockIdx][0][p-1]!=' ')continue;if(q>0&&puzzleBlocks[blockIdx][1][q-1]!=' ')continue;if(r>0&&puzzleBlocks[blockIdx][2][r-1]!=' ')continue;// 计算放置后的新偏移intnewP=i+p,newQ=i+q,newR=i+r;for(intk=0;k<3;k++){if(puzzleBlocks[blockIdx][0][k]=='*')newP++;if(puzzleBlocks[blockIdx][1][k]=='*')newQ++;if(puzzleBlocks[blockIdx][2][k]=='*')newR++;}// 标准化偏移（减去最小值）intminVal=min({newP,newQ,newR});intoffsetP=newP-minVal;intoffsetQ=newQ-minVal;intoffsetR=newR-minVal;// 更新dp值dp[minVal][offsetP][offsetQ][offsetR]+=currentVal;if(dp[minVal][offsetP][offsetQ][offsetR]>=MOD)dp[minVal][offsetP][offsetQ][offsetR]%=MOD;}}}}intmain(){initialize();intn,caseNo=1;while(cin>>n&&n!=0)cout<<"Case "<<caseNo++<<": "<<dp[n][0][0][0]<<"\n";return0;}