描述
已知 \(1 \leq n \leq 15\)，令 \({A} = [{a}_{i, j} ]_{n \times n}\)。若 \({a}_{i, j} = 0\)，表第 \(i\) 件連衣裙與第 \(j\) 雙鞋子不搭；若為 \({a}_{i, j} = 1\)，表搭；若為 \({a}_{i, j} = 2\)，表超搭。一個可接受的選擇，必須是在所有連衣裙和鞋子都選中的情況下，所有裙鞋搭配都搭，或者是其中一個裙鞋搭配超搭。以 \({A}\) 表 \(n\) 件連衣裙和 \(n\) 雙鞋子彼此間的搭配程度，問共有多少可接受的選擇。
思路
以下以「搭配」表示某件連衣裙與某雙鞋子構成的配對，並且每種「選擇」都由 \(n\) 個「搭配」構成。
第一層
考慮共有 \(n\) 件連衣裙與 \(n\) 雙鞋子，共有 \(n^2\) 個搭配，可以看出最暴力的解法為檢查所有可能的選擇，共有 \((n^2)^n\) 種，考慮到 \((15^2)^{15} = 1917,5105,9232,8840,8666,8491,3635,2539,0625\)，我們還是另尋它路，給暴力法一點尊重。
第二層
暴力法會如此暴力的原因，是一個選擇中會出現重複的搭配，例如選 n 次第一件連衣裙和第一雙鞋子，如此不講武德的選法，必須改進，現在將 \(n^2\) 個搭配，以不重複的方式，每次取 \(n\) 個出來檢查，因此有 \({C}^{n^2}_{n}\) 種選擇，當 \(n = 15\)，要檢查的選擇高達 \(910,0556,7811,1774,7809,5440\) 種，雖然比暴力法少，但還是太多了。
第三層
上面我們排除同搭配被重複選取的問題，但沒有處理同連衣裙或同鞋子被重複選取的問題，例如選 n 次與第一件連衣裙相關的搭配，這種選擇方式顯然不符合可接受的條件。現在在每種選擇中，必定按順序取連衣裙，也就是第一個搭配與第一件連衣裙相關，第二個搭配與第二件連衣裙相關，接著考慮鞋子，在第一種選擇中，我們可以按順序取鞋子，構成第一種搭配，在第二種選擇中，先取第二雙鞋，再取第一雙鞋，剩下的取鞋順序與第一種選擇相同，剩下的依此類推，可以發現按此方法得到的選擇，必定不會遇到同裙配多鞋或同鞋配多裙的情況，此處將 \({C}^{n^2}_{n}\) 降低至鞋子的全部排列方法，也就是 \({P}^{n}_{n} = n!\)，不過當 \(n = 15\)，選擇數為 \(1,3076,7436,8000\)，還是會 LTE，需要一些方法來優化。
第四層
根據第三層提到的取法，我們可以用樹狀方式展開所有可能的選擇。設 \(n = 5\)，令兩序列（一個序列代表一種鞋子的選取順序，也代表一種選擇）分別為 \(\{1, 2, 3, 4, 5\}\) 和 \(\{2, 1, 3, 4, 5\}\)，在前者已檢查過的情況下，後者在檢查完 \({a}_{1, 2}\) 和 \({a}_{2, 1}\)，剩下的 \({a}_{3, 3}\)、\({a}_{4, 4}\) 和 \({a}_{5, 5}\) 可能是不需檢查的。為何說是可能呢？因為在判斷之前，必須考慮 \({a}_{1, 2}\) 和 \({a}_{2, 1}\) 的狀態，若相同則不需繼續檢查，直接套用前者即可，若不同，則結果是不能確定的，假設 \({A}\) 為： \[ \begin{bmatrix} 1 & 2 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix} \] 依問題描述，可以發現 \(\{1, 2, 3, 4, 5\}\) 不是可接受的選擇，但 \(\{2, 1, 3, 4, 5\}\) 卻是可以接受的選擇，與上面的推斷吻合。
接下來再進一步，設 \({S}\) 為不定數量，由 \(1\) 起算的正整數集合，令 \(Permu({S})\) 表示所有由 \({S}\) 中元素組合成的全排列數列。考慮 \(\{1, 2, Permu(\{3, 4, 5\})\}\) 和 \(\{2, 1, Permu(\{3, 4, 5\})\}\)，在檢查完前者形成的 \(6\) 個選擇後，我們可以在已知 \(\{1, 2\}\) 的狀態下，把 \(Permu(\{3, 4, 5\})\) 可以得到多少可接受的搭配數紀錄下來，這樣使得當 \(\{2, 1\}\) 的狀態與 \(\{1, 2\}\) 一致時，可以直接得到答案，設 \({A}\) 為： \[ \begin{bmatrix} 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \end{bmatrix} \] 當知道 \(\{1, 2, Permu(\{3, 4, 5\})\}\) 的可接受選擇總數為 6 後，自然可以知道 \(\{2, 1, Permu(\{3, 4, 5\})\}\) 的可接受選擇總數為 6，這是因為 \(\{1, 2\}\) 的狀態為全部都搭（\({a}_{1, 2} = 1\) 且 \({a}_{2, 1} = 1\)），而 \(\{2, 1\}\) 的狀態也為全部都搭。
經過推論，現在令狀態 \(0\) 為之前出現過不搭的搭配，狀態 \(1\) 為之前只出現過搭的搭配，狀態 \(2\) 為之前出現過超搭的搭配，使用狀態壓縮（state compression）來表達已經檢查過的搭配，例如 \(3 = b'00011\) 代表 \(\{1, 2\}\) 或 \(\{2, 1\}\) 已經檢查過，這等價於 \(\{Permu(\{3, 4, 5\})\}\) 尚未檢查；\(14 = b'11010\) 代表 \(\{Permu(\{2, 4, 5\})\}\) 中的至少一個序列已經檢查過，等價於 \(\{1, 3\}\) 和 \(\{3, 1\}\) 尚未檢查。
有了以上設定，可以定義尋找表（lookup table），使其第一個索引為檢查過的搭配（或沒檢查過的，反正這兩種表述互補），第二個索引為狀態，儲存的值為在特定狀態下，尚未檢查過的搭配可以構成多少的可接受選擇，初始設置為 \(-1\)（或某個可表達的負整數，開心就好），表示不存在，藉由尋找表的幫助，這個方法可以解決 TLE 的問題。
第五層
實際上這個方法還能再優化，因為只要其中一個搭配超搭，整個選擇就是可接受的，依此特性，我們可以在第一次遇到超搭的搭配後，直接將可接受的選擇總數算出來，考慮 \(\{1, Permu(\{2, \dots, 15\})\}\)，若 \({a}_{1, 1} = 2\)，可以直接得知 \(\{1, Permu(\{2, \dots, 15\})\}\) 都是可接受的，共有 \(P^{14}_{14} = 14! = 871,7829,1200\) 種可接受選擇，不用進行後續檢查。由此可知對於某一選擇，在檢查 \(k - 1\) 件連衣裙對應的搭配後，第一次發現其與相應鞋子超搭時，直接得出 \((n - k)!\) 為與該序列前 \(k\) 個數字相同的搭配的總和，當作有效的可接受選擇總數，最後加上提前算好 \(n!\) 的具體數值，可以有效減少運算時間，並且如此一來，狀態 \(2\) 可以移除，降低 \({1 \over 3}\) 尋找表需要的記憶體。
結論
本問題看似複雜，實際上能用自頂向下，帶尋找表和剪枝（遇 \(2\) 直接算，其實查表也可算做剪枝）的遞迴解法解決，如果能夠改寫出自底向上的動態規劃解法，除去遞迴的開銷，運算的時間應該還能夠更少。
備註
- 本文的連衣裙和鞋子由 \(1\) 起算，請注意。
- long long 是你的好朋友。