20231006 NOIP#16（33daiOJ）总结
时间安排
7:40~8:00
看题，\(A\) 一眼切了，\(B\) 会两档，\(C,D\) 没想法。
8:00~8:20
写 \(A\) 的正解。
8：20~8:40
写 \(B\) 的 \(30pts\) 。
8:40~8:50
原来算错了 \(C\) 的爆搜复杂度，现在写了 \(C\) 的第一档。
8:50~9:20
会了 \(D\) 链的特殊性质写了 \(10pts\) 。
9:20~11:40
罚坐中……
总结反思
- 做不出来题时可以尝试打表并推式子。
题解
A.脑洞题
这题很简单且做法极其多样，后缀和应该是最简单好写的吧。
B.区间DP
设 \(f[l][r]\) 表示区间 \(l\sim r\) 所有可能的答案的和。 转移时枚举断点 \(k\)：
对于加法 \(f[l][r]=\sum_{k=l}^{r-1}(f[l][k]\times (r-k-1)! + f[k+1][r]\times (k-l)! )\times \binom{r-l-1}{k-l}\)
对于减法 \(f[l][r]=\sum_{k=l}^{r-1}(f[l][k]\times (r-k-1)! - f[k+1][r]\times (k-l)! )\times \binom{r-l-1}{k-l}\)
对于乘法 \(f[l][r]=\sum_{k=l}^{r-1}f[l][k]\times f[k+1][r]\times \binom{r-l-1}{k-l}\)
C.打表题
打表结论：要么每一列黑白交替，要么每一行黑白交替。
把整个棋盘黑白染色，然后翻转所有 \((i+j)\) 是偶数的坐标的棋子颜色。对于合法的方案来说，就变成了：要么每一列都同色，要么每一行都同色。
那么答案就是用每一列都同色的方案，加上每一行都同色的方案，减去所有行所有列都同色的方案。