题目描述给定一个5×55 \times 55×5的部分填充方格其中需填入数字111到252525各一次使得所有行、所有列以及所有“泛对角线”即所有平移后的主对角线和副对角线共202020条线上的555个数字之和均相等即均为656565。这样的方格称为强力幻方Powerful Magic Square\texttt{Powerful Magic Square}Powerful Magic Square。空白格用--表示。对于每个测试用例统计可以补全为强力幻方的方案总数。输入格式第一行一个整数nnn1≤n≤150001 \le n \le 150001≤n≤15000表示测试用例数量。每个测试用例包含555行每行555个字符串字符串由数字或--组成表示对应格子的值或空白。每个测试用例之后跟一个空行最后一个用例除外。输入格式保证正确但不保证填入的数字满足合法性如范围、重复等。输出格式对于每个测试用例输出一行Case X: Y其中XXX为用例编号从111开始YYY为方案数。样例输入2 1 7 13 19 -- 14 20 21 2 -- 22 3 9 15 -- 10 11 17 23 -- -- -- -- -- -- 1 2 3 -- -- 4 5 6 -- -- 7 8 9 -- -- -- -- -- -- -- -- -- -- -- --输出Case 1: 1 Case 2: 0题目分析强力幻方是555阶泛对角线幻方Panmagic Square\texttt{Panmagic Square}Panmagic Square。所有满足条件的幻方总数为288002880028800个且通过循环平移行或列仍然保持幻方性质因此具有平移对称性。若已知一个数字则无论它位于哪个位置能补全的幻方数均为115211521152因为28800/25115228800 / 25 115228800/251152。解题思路预生成全部解由于555阶泛对角线幻方具有明确的代数构造方法移位法可以高效生成全部288002880028800个解。具体地取两个排列a[0..4]a[0..4]a[0..4]和b[0..4]b[0..4]b[0..4]均为0..40..40..4的排列。定义幻方元素v5×a[(c2r) mod 5]b[(c−2r10) mod 5]1 v 5 \times a[(c 2r) \bmod 5] b[(c - 2r 10) \bmod 5] 1v5×a[(c2r)mod5]b[(c−2r10)mod5]1其中r,c∈{0,1,2,3,4}r,c \in \{0,1,2,3,4\}r,c∈{0,1,2,3,4}。遍历5!×5!144005! \times 5! 144005!×5!14400种排列每个生成一个幻方再取其转置得到全部288002880028800个幻方。将生成的幻方按左上角数字v0,0v_{0,0}v0,0​分组存储因为平移对称性允许我们将任意已知数字移动到左上角从而只需搜索对应分组的解。在线查询读入并检查合法性检查数字是否在1..251..251..25范围内是否有重复若有则直接输出000。快速处理若没有已知数字输出288002880028800若只有一个已知数字输出115211521152。平移若左上角没有已知数字则通过循环平移行和列将任意一个已知数字例如第一个移动到左上角。平移不改变方案数因为平移对称性。查表统计取平移后左上角的数字vipvipvip从预生成表中取出所有左上角为vipvipvip的幻方共115211521152个。遍历这些幻方检查是否匹配所有已知数字的位置累加匹配次数即为答案。复杂度预生成O(5!×5!×25)O(5! \times 5! \times 25)O(5!×5!×25)常数小。在线查询查表扫描最多115211521152个解每个解检查kkk个位置总操作约1152×251152 \times 251152×25在150001500015000用例下总时间约为707070毫秒满足要求。代码实现// Powerful Magic Squares// UVa ID: 10538// Verdict: Accepted// Submission Date: 2026-06-29// UVa Run Time: 0.070s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intS[26][1160][5][5],C[32];voidinitialize(){inta[5]{0,1,2,3,4};do{intb[5]{0,1,2,3,4};do{intvip5*a[0]b[0]1;for(intr0;r5;r)for(intc0;c5;c){intv5*a[(c2*r)%5]b[(c-2*r10)%5]1;S[vip][C[vip]][r][c]v;S[vip][C[vip]1][c][r]v;}C[vip]2;}while(next_permutation(b,b5));}while(next_permutation(a,a5));}intpms[5][5]{{1,7,13,19,25},{14,20,21,2,8},{22,3,9,15,16},{10,11,17,23,4},{18,24,5,6,12},};structI{intv,r,c;}D[25];intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);initialize();intn;cinn;for(intcs1;csn;cs){coutCase cs: ;intraw[5][5]{0},g[5][5]{0},seen[32]{0};interror0;intdc0;intfr-1,fc-1;for(intr0;r5;r)for(intc0;c5;c){string s;cins;if(s!--){intvstoi(s);if(v1||v25)error1;if(seen[v])error1;elseseen[v]1;if(fr-1fc-1)frr,fcc;raw[r][c]g[r][c]v;D[dc]{v,r,c};}}if(error){cout0\n;continue;}if(dc0){cout28800\n;continue;}if(dc1){cout1152\n;continue;}if(!raw[0][0]){dc0;for(intr0;r5;r)for(intc0;c5;c){g[r][c]raw[(rfr)%5][(cfc)%5];if(g[r][c])D[dc]{g[r][c],r,c};}}intvipg[0][0],answer0;for(inti0;iC[vip];i){intmatched1;for(intj0;jdcmatched;j)if(D[j].v!S[vip][i][D[j].r][D[j].c])matched0;answermatched;}coutanswer\n;}return0;}总结本题的核心在于利用555阶泛对角线幻方的平移对称性和代数构造法将查询转化为预生成解的分组查表。预生成全部288002880028800个解并按左上角数字分组使得在线查询只需扫描最多115211521152个候选解。平移操作将任意已知数字移至左上角进一步缩小搜索范围。该算法在150001500015000个测试用例下仅需约707070毫秒兼顾了正确性与高效性是解决此类“大量查询、状态空间有限且具有强对称性”问题的典型方法。