【题解】Solution Set - NOIP2024集训Day37 计数 dp

【题解】Solution Set - NOIP2024集训Day37 计数 dp

https://www.becoder.com.cn/contest/5555

T1,2 easier

1,5,(6,3),(2,7),8,4

---

「CQOI2011」放棋子

做过。

考虑容斥。

二维二项式反演？

---

感觉用二项式反演，转化为逆向问题反而不好做，考虑一个 dp 直接做。

\(f_{i,j,k}\)：用前 \(k\) 个颜色，放置在恰好 \(i\) 行，\(j\) 列中。

\[f_{i,j,k}=\sum_{p=0}^{j-1}f_{i,p,k-1}\times ... \]

又死了，显然最后这个颜色 \(k\) 在放置 \((j-p)\) 列的同时，可以再放在若干行上。

（dp 转移还是需要加强啊，想想某一个特定元素的所有情况，并消除她们的贡献之后来划分子问题。

---

\[f_{i,j,k}=\sum_{l\in[0,i],r\in[0,j]}[(i-l)(j-r)\ge a_k]\left(f_{l,r,k-1}{n-l\choose i-l}{m-r\choose j-r}g_{i-l,j-r,a_k} \right) \]

\(g_{i,j,k}\)：将 \(k\) 个同色棋子恰好填满 \(i\) 行，\(j\) 列。

\[g_{i,j,k}=g_{i,j,k-1}+(i+j-1)g_{i-1,j-1,k-1} \]