alan23273850 的刷題筆記
a682: 00861 - Little Bishops
Tags: bitmask, combinatorics, dp, puzzle, self-thinking-solution
出處：https://zerojudge.tw/ShowProblem?problemid=a682
提交：https://zerojudge.tw/Submissions?problemid=a682&account=allllllan123456
問題：給定一個 n*n (n $\in[1,8]$) 的西洋棋盤，請問在盤上放置 $k\in[0,n^2]$ 個主教而能使得這些主教不會互相攻擊的方法數有多少？主教只能攻擊斜對角線上的棋子。
解法：網路上的大眾解法幾乎都是採用 DP，不過其實這題有更聰明的作法，它會需要用到排列組合的基礎知識。首先我們知道西洋棋盤的底色是黑白相間的，這意味著站在不同色塊上的兩個主教無法互相攻擊，因此不同色塊的對角線之間是彼此獨立的，我們可以把整個棋盤拆成兩個不同顏色的獨立子棋盤 A 和 B。假設整個盤面總共需要放 k 個棋子，那麼總數分別就是 A 有 0 個棋子的方法數和 B 有 k 個棋子的方法數的乘積，加上 A 有 1 個棋子的方法數和 B 有 (k-1) 個棋子的方法數的乘積，再加上 A 有 2 個棋子的方法數和 B 有 (k-2) 個棋子的方法數的乘積，持續加到 A 有 k 個棋子的方法數和 B 有 0 個棋子的方法數的乘積，以數學式子來描述的話便是 $\displaystyle\sum_{i=0}^k A(i)\cdot B(k-i)$。那現在剩下的問題便是如何快速地算出 A 和 B 分別放置 i 顆棋子的方法數了。要解決這個問題，我們必須先觀察棋盤的形狀，以 n=8 為例，有一個半組對角線旋轉 45 度之後的子棋盤之每列格數分別為 {1,3,5,7,7,5,3,1}，另外一個半組對角線旋轉 45 度之後的子棋盤之每列格數分別為 {2,4,6,8,6,4,2}，並且它們旋轉過後都是置中對齊。由於棋盤的每一列和每一行都只能放置一顆棋 (否則就會互相攻擊)，因此在決定每一列是否要置放棋子、要置放在哪一格的時候，只要按照由格子數少的列往格子數多的列的順序去作決定，那麼每一步可能的選法 (已經確定要在這個列放置棋子的前提之下) 就是當前列的格子數減去之前已經放置好的棋子數，再隨時與之前累積的方法數相乘就能累加進當下已置放的棋子數所對應到的方法數，要記得累加的動作必須在當時的列有放置棋子的時候才能做，否則會重複計算。詳細可參考程式碼。
1#include <bits/stdc++.h>
2using namespace std;
3
4int n; long long dp[2][9];
5
6void choose(bool even, int index, unsigned config, long long sum) {
7 if (index && ((config>>(index-1)) & 1))
8 dp[even][__builtin_popcount(config)] += sum;
9 if (index == n - even) return;
10 choose(even, index+1, config, sum);
11 if (index/2*2+1+even > __builtin_popcount(config))
12 choose(even, index+1, config | (1<<index), sum * (index/2*2+1+even - __builtin_popcount(config)));
13}
14
15int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
16 int k;
17 while (cin >> n >> k && (n||k)) {
18 long long ans = 0; memset(dp, 0, sizeof dp);
19 dp[0][0] = 1; choose(false, 0, 0, 1);
20 dp[1][0] = 1; choose(true, 0, 0, 1);
21 for (int i=0; i<=k; i++)
22 if (i<9 && k-i<9)
23 ans += dp[0][i] * dp[1][k-i];
24 cout << ans << '\n';
25 }
26 return 0;
27}