杂题分享
CF1548E Gregor and the Two Painters
计数。
一个很棒的思想找代表元。
一个联通块由多个格子组成不好计数，因此我们给每个连通块找一个代表元，就找 \((a_i+b_j,i,j)\) 的最小的吧。
我们考虑一个格子 \((x,y)\) 何时成为代表元：
- \(a_x+b_y\leq k\)。
- \(a_x\) 是 \([la,ra]\) 中最小的，\(b_y\) 是 \([lb,rb]\) 中最小的。
设 \(A_x=\min(\max_{i=la}^{x-1}a_i,\max_{i=x+1}^{ra}a_i)\)，\(B_y=\min(\max_{i=lb}^{y-1}b_i,\max_{i=y+1}^{rb}b_i)\)
- \(b_y+A_x>k\)。
- \(a_x+B_y>k\)。
后两条是因为不能让这个点与其他更小的黑块联通。
固定 \(x\)，\(k-A_x<b_y\leq k-a_x\)，\(B_y>k-a_x\)，统计 \(y\) 的个数，扫描线 + 树状数组。
[ARC124E] Pass to Next
solution
虽然感觉组合意义的做法更有启发性，但是我不会。
SP3734 PERIODNI - Periodni
凹凸不平的不好做，我们考虑将它分成若干完整的矩形，\(a\times b\) 的矩形中填 \(k\) 个字符的方案数为 \(\tbinom{a}{k}b^{\underline{k}}\)。
能比较优雅刻画完整矩形，大概是能想到笛卡尔树的吧
以 \((i,h_i)\) 为关键字建出笛卡尔树，\(h_i\) 为小根堆。
设 \(f_{i,j}\) 表示笛卡尔树上 \(i\) 号点的子树内，填了 \(j\) 个字符的方案数。做一个树形背包。
\[f_{x,i}=\sum\limits_j f_{x,i-j}\times f_{son,j}
\]
再补上 \(x\) 点凸出的部分，
\[f_{x,i}=\sum\limits_j f_{x,i-j}\times \tbinom{h_x-h_{fa}}{j}\times (siz_x-(i-j))^{\underline{j}}
\]
奇怪数学思考题
给出 \(n,m,S=\{xy | 1\leq x\leq n,1\leq y\leq m\}\)，求 \(|S|\)，\(n=64,m=10^{16}\)。
有人会的话教教我。