今天摆了！
今天把之前剩了的俩计数写了顺便写了题解?，也算是 OI 生涯圆满了?，要不然如果退役了心里总有那个坎过不去，总会想着自己有想写的题没写完，哎。
由于上午把任务差不多完成了，导致下午没事可干，晚上为了防止无事可做把己巳己学了下?，也算是一个晚上勉强能开完的坑了?。
距离退役还有四天???，这日子真的过一天少一天了?。
下午的时候被盒了???，但是反正盒我也挺简单的，就无所谓了?。
分享之前的一个提交记录：https://www.luogu.com.cn/record/126162589 ，个人感觉写的还好，比较符合人类直觉??，但是被 tibrella D 说傻逼缩进了???
最近又开始看 P 站了?，在 P 站搜刮到好多好多好看的图片??????。
话说 gitcode 好像要更新了，好像我之前博客里面用 gitcode 当图床的图都会看不了???。明天改这玩意估计得累死。
今天闲话又没啥内容??。
明天晚上还有傻逼答辩模拟赛??。
NOIP 游记已经开始写了（确信），但是内容太少就不发了，这两天还是写闲话???。
下限极低且不知收敛
推歌：CYCLES -Masayoshi Minoshima/綾倉盟
好听！
AGC021F
设 \(f_{i, j}\) 为考虑前 \(j\) 列，当前已经有 \(i\) 行中有过黑格子所能生成的序列方案数。那么最终答案即为 \(\sum_{i=0}^{n}\dbinom{n}{i}f_{i,m}\)。
显然初始状态为 \(f_{i, 1}=1\)，因为这时每一行都必须染黑。考虑从 \(f_{k, j-1}\) 转移到 \(f_{i, j}\)，也就是在第 \(j\) 列放入 \(i-k\) 个之前没有放过的位置。
进行一个分类讨论：
- 当 \(i=k\) 时，这些行之前都被放过，那么 \(A\) 数组是不会变的，只需考虑 \(B, C\) 数组即可。因此有三种情况：这一列不放、放一个（\(B_j=C_j\)），以及放大于等于两个（\(B_j<C_j\)），因此转移系数为 \(1+\dbinom{i}{1}+\dbinom{i}{2}\)。
- 当 \(i>k\) 时，这种情况比较复杂。首先新多出来的 \(i-k\) 行是一定要放黑格子的，同时为了让 \(A\) 不相同，可以先把原来 \(k\) 行也都拆出来，然后在 \(i\) 行中选择 \(i-k\) 行在第 \(j\) 列放黑格子，然后剩下的列再按顺序放回去。但这样只解决了 \(A\) 的问题，由于之前放过黑格子的列这一列其实也还可以放，因此 \(B,C\) 可能是由原来的列贡献的。因此还需要再分讨。
- 当最大值和最小值都由这新增的 \(i-k\) 行贡献时，转移系数即为上文中所说的 \(\dbinom{i}{i-k}\)。
- 当最值其中之一为原有的行贡献时，可以考虑构建一个双射：选择出 \(i-k+1\) 行，就钦定最下面（最上面）的一行为原有的一行。可以发现这确实是一个双射，由于有最大值最小值，转移系数为 \(2\dbinom{i}{i-k+1}\)。
- 当最值都为原有的行贡献时，同上构建双射即可，转移系数为 \(\dbinom{i}{i-k+2}\)。
- 因此这种情况的转移系数为 \(\dbinom{i}{i-k}+\dbinom{i}{i-k+1}+\dbinom{i}{i-k+2}\)，用组合数递推式可以化简为 \(\dbinom{i+2}{i-k+2}\)。
因此转移为 \(f_{i,j}=f_{i,j-1}\times \left(1+\dbinom{i}{1}+\dbinom{i}{2}\right)+\sum_{k=0}^{i-1}f_{k,j-1}\times \dbinom{i+2}{i-k+2}\)。
时间复杂度为 \(O(n^2m)\)，把右边的求和用 NTT 优化即可做到 \(O(nm\log n)\)。
根据 tibrella 今天说过的话：
今天放点铜图。
说实话我还真没找到多少恋恋的铜图?，找到的绝大多数都是芙兰的?，确实芙兰更符合这个设定?。
趣事：昨天二多龙看到昨天闲话最后一张图后给我发了铜图???。
记得看 tibrella 闲话！保证涩！