企业官网建设流程全解析

题目描述

给定一个5×55 \times 55×5的部分填充方格，其中需填入数字111到252525各一次，使得所有行、所有列以及所有“泛对角线”（即所有平移后的主对角线和副对角线，共202020条线）上的555个数字之和均相等，即均为656565。这样的方格称为强力幻方（Powerful Magic Square\texttt{Powerful Magic Square}Powerful Magic Square）。
空白格用"--"表示。对于每个测试用例，统计可以补全为强力幻方的方案总数。

输入格式

第一行一个整数nnn（1≤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/25=115228800 / 25 = 115228800/25=1152）。

解题思路

预生成全部解

由于555阶泛对角线幻方具有明确的代数构造方法（移位法），可以高效生成全部288002880028800个解。
具体地，取两个排列a[0..4]a[0..4]a[0..4]和b[0..4]b[0..4]b[0..4]，均为0..40..40..4的排列。定义幻方元素：

v=5×a[(c+2r) mod 5]+b[(c−2r+10) mod 5]+1 v = 5 \times a[(c + 2r) \bmod 5] + b[(c - 2r + 10) \bmod 5] + 1v=5×a[(c+2r)mod5]+b[(c−2r+10)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. 读入并检查合法性：
   检查数字是否在1..251..251..25范围内，是否有重复，若有则直接输出000。

2. 快速处理：
   若没有已知数字，输出288002880028800；若只有一个已知数字，输出115211521152。

3. 平移：
   若左上角没有已知数字，则通过循环平移行和列，将任意一个已知数字（例如第一个）移动到左上角。平移不改变方案数，因为平移对称性。

4. 查表统计：
   取平移后左上角的数字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//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intS[26][1160][5][5],C[32];voidinitialize(){inta[5]={0,1,2,3,4};do{intb[5]={0,1,2,3,4};do{intvip=5*a[0]+b[0]+1;for(intr=0;r<5;++r)for(intc=0;c<5;++c){intv=5*a[(c+2*r)%5]+b[(c-2*r+10)%5]+1;S[vip][C[vip]][r][c]=v;S[vip][C[vip]+1][c][r]=v;}C[vip]+=2;}while(next_permutation(b,b+5));}while(next_permutation(a,a+5));}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;cin>>n;for(intcs=1;cs<=n;++cs){cout<<"Case "<<cs<<": ";intraw[5][5]={0},g[5][5]={0},seen[32]={0};interror=0;intdc=0;intfr=-1,fc=-1;for(intr=0;r<5;r++)for(intc=0;c<5;c++){string s;cin>>s;if(s!="--"){intv=stoi(s);if(v<1||v>25)error=1;if(seen[v])error=1;elseseen[v]=1;if(fr==-1&&fc==-1)fr=r,fc=c;raw[r][c]=g[r][c]=v;D[dc++]={v,r,c};}}if(error){cout<<"0\n";continue;}if(dc==0){cout<<28800<<'\n';continue;}if(dc==1){cout<<1152<<'\n';continue;}if(!raw[0][0]){dc=0;for(intr=0;r<5;r++)for(intc=0;c<5;c++){g[r][c]=raw[(r+fr)%5][(c+fc)%5];if(g[r][c])D[dc++]={g[r][c],r,c};}}intvip=g[0][0],answer=0;for(inti=0;i<C[vip];i++){intmatched=1;for(intj=0;j<dc&&matched;j++)if(D[j].v!=S[vip][i][D[j].r][D[j].c])matched=0;answer+=matched;}cout<<answer<<'\n';}return0;}

总结

本题的核心在于利用555阶泛对角线幻方的平移对称性和代数构造法，将查询转化为预生成解的分组查表。

• 预生成全部288002880028800个解并按左上角数字分组，使得在线查询只需扫描最多115211521152个候选解。
• 平移操作将任意已知数字移至左上角，进一步缩小搜索范围。

该算法在150001500015000个测试用例下仅需约707070毫秒，兼顾了正确性与高效性，是解决此类“大量查询、状态空间有限且具有强对称性”问题的典型方法。