UVa 269 Counting Patterns

题目分析本题要求计算nnn-kkk谜题的模式pattern\texttt{pattern}pattern数量。一个配置configuration\texttt{configuration}configuration是一个长度为nnn的nnn元组每个元素取值于[−k,k][-k, k][−k,k]范围内的整数且所有元素之和为000。两个配置被认为是等价的如果可以通过以下操作的任意组合相互得到循环置换将元组循环移动一个或多个位置反转将元组顺序完全反转符号反转将所有元素的符号取反这些等价类被称为模式pattern\texttt{pattern}pattern。题目要求对于每组输入(n,k)(n, k)(n,k)输出模式总数并按照字典序输出每个模式的代表元即该等价类中字典序最大的那个配置。约束条件nk≤11n k \leq 11nk≤11这意味着搜索空间是有限的可以使用深度优先搜索DFS\texttt{DFS}DFS枚举所有可能的配置。解题思路核心问题问题的核心在于如何高效地枚举所有配置并判断一个配置是否是它所在等价类中字典序最大的代表元由于nk≤11n k \leq 11nk≤11nnn的最大值为111111kkk的最大值也为111111。每个位置有2k12k12k1种可能的取值总配置数最多约为(2×111)112311≈9.5×1014(2 \times 11 1)^{11} 23^{11} \approx 9.5 \times 10^{14}(2×111)112311≈9.5×1014直接枚举所有配置并判断等价是不可行的。因此需要有效的剪枝策略。关键观察字典序最大代表元题目要求输出的代表元是等价类中字典序最大的配置。因此我们只需要生成那些作为等价类最大元的配置跳过那些不是最大元的配置。对称性约简等价关系由循环置换、反转、符号反转生成。这意味着一个配置的等价类最多包含2×2×n4n2 \times 2 \times n 4n2×2×n4n个不同的配置当配置没有对称性时。首元素约束由于配置可以整体符号反转且我们只取字典序最大的配置作为代表元代表元的第一个元素a0a_0a0​必须非负。如果a0a_0a0​是负数取反后得到的配置字典序更大因为负数非负数。循环等价性判断对于给定的配置A(a0,a1,…,an−1)A (a_0, a_1, \dots, a_{n-1})A(a0​,a1​,…,an−1​)要判断它是否是等价类中字典序最大的需要检查所有循环移位后的配置是否字典序不大于AAA所有循环移位后再反转的配置是否字典序不大于AAA以上两种操作再配合符号反转后的配置是否字典序不大于AAA搜索策略采用深度优先搜索DFS\texttt{DFS}DFS生成所有候选配置按字典序降序枚举搜索时第一位a0a_0a0​从kkk向下枚举到000因为代表元的首位必须非负且为了得到字典序最大的代表元我们需要从大到小尝试。实际上代码中是从000到kkk枚举然后通过剪枝保证生成的是最大元。剪枝条件前缀和剪枝设当前已确定前ddd个元素和为sumsumsum。剩余n−dn-dn−d个元素的最大可能绝对值和为(n−d)×k(n-d) \times k(n−d)×k。如果∣sum∣(n−d)×k|sum| (n-d) \times k∣sum∣(n−d)×k则剩余元素无论怎么取都无法使总和为000可以剪枝。字典序剪枝为了确保最终生成的配置是等价类中的最大元在构造过程中就施加约束如果前一个元素等于a0a_0a0​且当前尝试的元素大于a1a_1a1​则后续任何配置都会产生一个比当前候选更大的循环移位因此可以提前终止该分支的搜索因为a1a_1a1​已经固定更大值会导致更大的字典序。如果当前尝试的元素等于a0a_0a0​且前一个元素大于a1a_1a1​同样可以剪枝。判断是否为最大元当完整生成一个配置且总和为000后调用isLexicographicallyLargest()函数验证它是否确实是等价类中的字典序最大元。该函数通过生成所有循环移位、反转以及符号反转后的配置逐一比较字典序。isLexicographicallyLargest()函数详解该函数检查当前配置digits[0..n−1]digits[0..n-1]digits[0..n−1]是否是等价类中的字典序最大元。具体步骤将配置复制两份到permutation数组长度为2n2n2n方便进行循环移位的比较。检查所有循环移位对于每个起始位置iii1≤in1 \leq i n1≤in如果permutation[i] digits[0]即循环移位的首元素等于原配置的首元素则比较该移位后的序列与原始配置的字典序。如果移位后的序列更大则当前配置不是最大元。取反后检查循环移位将permutation中所有元素取反重复步骤222。反转后检查将原配置反转同样复制两份重复步骤222和333。如果以上所有检查都通过说明没有比当前配置更大的等价配置当前配置即为代表元。复杂度分析由于nk≤11n k \leq 11nk≤11且剪枝条件非常有效实际搜索的节点数远小于理论最大值。每个候选配置需要O(n2)O(n^2)O(n2)时间进行等价性检查实际上n≤11n \leq 11n≤11常数很小可以接受。实现细节使用全局数组digits[16]存储当前正在构造的配置。使用configuration[100000][16]存储所有找到的代表元实际数量远小于此。搜索时首位digits[0]从000到kkk枚举因为代表元首位非负。注意输出格式两组输出之间有一个空行最后一行后不能有多余空行。代码实现// Counting Patterns// UVa ID: 269// Verdict: Accepted// Submission Date: 2016-06-04// UVa Run Time: 0.240s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intn,k,digits[16],permutation[32],configuration[100000][16],solutions;// 比较数组 p 和全局数组 digits 的字典序大小// 如果 p 的字典序大于 digits返回 trueboolisLarger(intp[]){inti;for(i0;p[i]digits[i]in;i);returninp[i]digits[i];}// 确保当前配置是等价类中字典序最大的// 通过检查所有循环移位、反转及符号反转后的配置boolisLexicographicallyLargest(){// 将 digits 复制两份到 permutation便于处理循环移位for(inti0;in;i)permutation[i]digits[i],permutation[in]digits[i];// 检查所有循环移位不取反for(inti1;in;i)if(permutation[i]digits[0]isLarger(permutationi))returnfalse;// 取反后检查所有循环移位for(inti0;i2*n;i)permutation[i]-permutation[i];for(inti1;in;i)if(permutation[i]digits[0]isLarger(permutationi))returnfalse;// 反转原配置然后检查循环移位for(intin-1;i0;i--)permutation[n-i-1]digits[i],permutation[2*n-i-1]digits[i];for(inti0;in;i)if(permutation[i]digits[0]isLarger(permutationi))returnfalse;// 反转后再取反检查循环移位for(inti0;i2*n;i)permutation[i]-permutation[i];for(inti0;in;i)if(permutation[i]digits[0]isLarger(permutationi))returnfalse;returntrue;}// 深度优先搜索// depth: 当前已确定元素个数下一个要填充的位置索引// sumCurrent: 当前已确定元素的和voiddfs(intdepth,intsumCurrent){// 已完整生成一个配置if(depthn){// 总和为零且是等价类中字典序最大元if(sumCurrent0isLexicographicallyLargest()){// 保存该代表元for(inti0;in;i)configuration[solutions][i]digits[i];solutions;}}// 剪枝当前和的绝对值不能超过剩余元素可能的最大绝对值和elseif(abs(sumCurrent)(n-depth)*digits[0]){// 枚举当前位置的可能取值for(intd-digits[0];ddigits[0];d){digits[depth]d;// 剪枝如果前一个元素等于首位且当前元素大于第二位// 则后续生成的配置一定不是最大元因为会产生更大的循环移位if(digits[depth-1]digits[0]digits[depth]digits[1])break;// 剪枝如果当前元素等于首位且前一个元素大于第二位// 同样可以剪枝if(digits[depth]digits[0]digits[depth-1]digits[1])break;// 递归搜索sumCurrentd;dfs(depth1,sumCurrent);sumCurrent-d;}}}intmain(){intcases0;while(cinnk){// 两组输出之间用空行分隔if(cases)coutendl;solutions0;// 枚举首位从 0 到 k代表元首位必须非负for(intstart0;startk;start){digits[0]start;dfs(1,start);}// 输出结果coutsolutionsendl;for(inti0;isolutions;i){for(intj0;jn;j)cout(j?,:()configuration[i][j];cout)endl;}}return0;}总结本题的关键在于利用等价关系的对称性进行剪枝只生成等价类中的字典序最大元。通过前缀和剪枝和字典序剪枝在nk≤11n k \leq 11nk≤11的约束下能够高效求解。代码实现中需要注意枚举顺序和边界条件的处理确保输出的代表元符合题目要求的字典序顺序。