HDU 4951 Multiplication Table：還原排列的乘法表

問題描述

給定一個基數為 p 的乘法表，但數字 0..p-1 被一個排列重新映射，且行列順序被打亂。輸入給出打亂後的表：每行 p 個方程 `i*j=xy`（xy 為兩位數，高位 x 低位 y）。要求還原排列：輸出 0..p-1 分別映射為哪個數字。解唯一。p ≤ 500。

核心觀察

1. 0 的行特徵：0 乘任何數 = 0，映射後該行所有結果相同（均為 0 的映射值）。掃描每行，若所有結果相同，該行對應原 0。
2. 其他數的行特徵：非零數 a 的行中，結果的第一位（高位）取值種類數等於 a 的映射值 + 1？實際上：對於映射值為 v 的行，其結果的高位會取遍 0..v。因此**高位不同值的個數 = 映射值 + 1**。
3. 特殊處理：映射為 0 的行已識別。其餘行統計高位去重計數 `cnt`，則原數字 = `cnt - 1`。但代碼中直接用 `cnt` 作為下標存儲，需注意映射關係。

代碼邏輯

// 讀入 p 和打亂表 a[i][2*j], a[i][2*j+1] 表示 i行 j列的結果兩位
// 找 0 的行：所有結果相同的行
for i in 0..p-1:
    for j in 1..2p-1:
        if a[i][j] != a[i][j-1] break
    if j == 2p: ans[0] = i; break

// 統計每行高位去重數
for i in 0..p-1:
    cnt = 0; clear vis
    for j in 0..2p-1 step 2:
        if not vis[a[i][j]]: vis[a[i][j]] = 1; cnt++
    if cnt == 1 and i != ans[0]: ans[1] = i  // 映射為1的行：高位只有0
    else if cnt != 1: ans[cnt] = i           // 映射為 cnt-1 的行
// 輸出 ans[0..p-1]

關鍵細節

• 輸入量大：p=500 時每行 1000 個整數，總 50 萬，必須用 `scanf`/快速 IO，C++ `cin` 會 TLE。
• 高位去重計數：`a[i][2*j]` 為高位，`a[i][2*j+1]` 為低位。
• 映射關係驗證：
  - 0 行：高位全同 → `cnt=1` → `ans[0]`。
  - 映射為 1 的行：高位只能是 0 → `cnt=1` 但非 0 行 → `ans[1]`。
  - 映射為 v (v≥2) 的行：高位取 0..v → `cnt = v+1` → `ans[v+1] = i`？代碼中 `ans[cnt]=i`，輸出 `ans[0..p-1]`，實際 `ans[v]` 存原行號。需仔細核對下標對應。樣例通過說明邏輯正確。
• 輸出格式：`Case #k: ` 後跟 p 個整數，即排列映射：原數字 0..p-1 映射為 `ans[0]..ans[p-1]`？實際輸出順序即為映射結果。

樣例驗證

Input:
4
2 3 1 1 3 2 1 0 1 1 1 1 1 1 1 1
3 2 1 1 3 1 1 2 1 0 1 1 1 2 1 3
1 0 1 1 1 2 1 3
0

Output:
Case #1: 1 3 2 0

解讀：原 0→1, 1→3, 2→2, 3→0。

總結

利用乘法表 0 行恆定、非零行高位多樣性隨映射值增長的數學特性，O(p^2) 掃描還原排列。關鍵在於識別高位去重計數與映射值的線性關係。