P5664 [CSP-S2019] 伊原家今天的飯

這道題非常優雅！

首先我們發現考慮這個 $j \le \left \lfloor \frac{k}{2} \right \rfloor$ 這個條件直接算比較困難，所以我們考慮正反則難！

因為僅可能有一個 $col$ 滿足 $col \ge \left \lfloor \frac{k}{2} \right \rfloor$ 所以我們考慮枚舉這一個 $col$

那我們算這個東西顯然直接組合數是算不了的了，我們使用dp，設 $dp_{i,j,k}$ 表示前 $i$ 行在第 $col$ 列選了 $k$ 個，然後在其餘列選了 $j$ 個的方案數

那我們轉移的時候有三種情況：

1. 不選第 $i$ 行
2. 選擇第 $i$ 行第 $col$ 列的數字
3. 選取第 $i$ 行不在第 $col$ 列的數字

則有dp轉移：

$$dp_{i,j,k}=dp_{i-1,j,k}$$ $$dp_{i,j,k}=dp_{i-1,j-1,k} \times (sum_i-a_{i,col}) $$$$dp_{i,j,k}=dp_{i-1,j,k-1} \times a_{i,col}$$

初始值：$dp_{0,0,0}=1$

答案：$ans-dp_{n,j,k} (j<k)$

這樣時間複雜度是 $O(m \times n^3)$ 的，過不了 那我們就考慮，類似存兩個變量，我們發現對於這兩個變量的具體值是沒有必要記錄的，僅僅需要記錄滿足 $k>j$ 的情況，因為僅僅有這樣，才可以不滿足題目條件

那我們完全可以只記錄這個東西的差值，把dp狀態改成：$dp_{i,j}$ 表示前 $i$ 行選完之後，第 $col$ 行列選的比其他列選的多 $j$ 個（當然 $j$ 可能是負數，所以我們需要加上一個偏移量 $n$ ）

還是剛剛那幾種情況，則有轉移：

$$dp_{i,j}=dp_{i-1,j}$$ $$dp_{i,j}=dp_{i-1,j-1} \times a_{i,col}$$ $$dp_{i,j}=dp_{i-1,j+1} \times (sum_i-a_{i,col})$$

初值：$dp_{0,0}=1$

答案：$ans-dp_{n，j}（j>0）$

那我們總的答案如何算呢？ 還是可以使用dp，也可以不用

我設$g_{i，0/1}$表示前$i$行，並且第$i$行選/不選的方案數

顯然有轉移：

$$g_{i,0}=g_{i-1,0}+g_{i-1,1}$$ $$g_{i,1}=(g_{i-1,0}+g_{i-1,1}) \times sum_i$$

初值：$g_{0,0}=1$

答案：$ans=g_{n，0}+g_ {n,1}-1$

P5664 [CSP-S2019] Emiya 家今天的饭

这道题非常优雅！

首先我们发现考虑这个 $j \le \left \lfloor \frac{k}{2} \right \rfloor$ 这个条件直接算比较困难，所以我们考虑正反则难！

因为仅仅可能有一个 $col$ 满足 $col \ge \left \lfloor \frac{k}{2} \right \rfloor$ 所以我们考虑枚举这一个 $col$

那我们算这个东西显然直接组合数是算不了的了，我们使用dp，设 $dp_{i,j,k}$ 表示前 $i$ 行在第 $col$ 列选了 $k$ 个，然后在其余列选了 $j$ 个的方案数

那我们转移的时候有三种情况：

1. 不选第 $i$ 行
2. 选第 $i$ 行第 $col$ 列的数字
3. 选第 $i$ 行不在第 $col$ 列的数字

则有dp转移：

$$dp_{i,j,k}=dp_{i-1,j,k}$$ $$dp_{i,j,k}=dp_{i-1,j-1,k} \times (sum_i-a_{i,col}) $$$$dp_{i,j,k}=dp_{i-1,j,k-1} \times a_{i,col}$$

初值：$dp_{0,0,0}=1$

答案：$ans-dp_{n,j,k} (j<k)$

这样时间复杂度是 $O(m \times n^3)$ 的，过不了

那我们就考虑，类似存两个变量，我们发现对于这两个变量的具体值是没有必要记录的，仅仅需要记录满足 $k>j$ 的情况，因为仅仅有这样，才可以不满足题目条件

那我们完全可以仅仅记录这个东西的差值，把dp状态改为：$dp_{i,j}$ 表示前 $i$ 行选完之后，第 $col$ 行列选的比其他列选的多 $j$ 个（当然 $j$ 可能是负数，所以我们需要加上一个偏移量 $n$ ）

还是刚刚那几种情况，则有转移：

$$dp_{i,j}=dp_{i-1,j}$$ $$dp_{i,j}=dp_{i-1,j-1} \times a_{i,col}$$ $$dp_{i,j}=dp_{i-1,j+1} \times (sum_i-a_{i,col})$$

初值：$dp_{0,0}=1$

答案：$ans-dp_{n,j}(j>0)$

那我们总的答案如何算呢？还是可以使用dp，也可以不用

我设 $g_{i,0/1}$ 表示前 $i$ 行，并且第 $i$ 行选/不选的方案数

显然有转移：

$$g_{i,0}=g_{i-1,0}+g_{i-1,1}$$ $$g_{i,1}=(g_{i-1,0}+g_{i-1,1}) \times sum_i$$

初值：$g_{0,0}=1$

答案：$ans=g_{n,0}+g_{n,1}-1$