簡化版題意：

有一個 n 行 m 列的矩陣， (i, j) 位置有 a_{i,j} 的物品，所有物品互不相同。

現從矩陣中選物品，規定每行隻能選 0/1 個物品，

且若共選瞭 k 個物品，則每列選的物品數 le lfloor frac{k}{2} rfloor ，且一共最少選 1 個物品。

問方案數

數據范圍:

n in [1,100], m in [1,2000]

解法：

發現直接做不太好求，於是從反面考慮，即：所求方案數 = 每行最多選 1 個，且可能有列上所選物品個數大於總個數的一半 的方案數 - 每行最多選 1 個，且一定有某列上所選物品個數大於總個數的一半 的方案數（容斥原理）

先考慮每行最多選一個物品的方案數，發現這是一個經典的分步計數問題，令第 i 行總物品數為 s_i ，則在第 i 行的方案數為 (s_i + 1) （+1是考慮瞭不選的情況），於是總方案數為 [quad prod _{i=1}^n (s_i+1) quad] - 1 （不能選 0 個物品，所以 -1 ）

再考慮每行最多選一個物品，且存在一列上所選物品嚴格大於所選物品總數一半的方案數 ，易見這樣的列最多隻有 1 列，於是考慮枚舉，問題變成 求每行最多選一個物品，且第 j 列所選物品數超過總所選物品數一半 的方案數。

考慮 dp ，若當前枚舉到第 col 列上所選物品超過一半，定義 f_{i,j} 表示考慮前 i 行，且第 col 列上選擇的物品比其他列所選物品多 j 個的方案數，轉移方程:

f_{i,j} = f_{i-1,j} + f_{i-1,j-1} times a_{i,col} + f_{i-1,j+1} times (s_i-a[i][col])

解釋：考慮第 i 行選則的物品，若不選，則問題變成 f_{i-1, j} (參考定義)，若選的是第 col 列的物品，則問題變成前 i-1 行，第 j 列所選物品比其他列多 j-1 個的方案數，由乘法原理，求得貢獻，若選不是第 col 列的物品，分析過程類似。

於是對於第 col 列，他會使得答案減去 sum_{j=1}^n f_{n,j}

考慮所有列後即可求得答案

Code: