杨图计数 + 对角线性质 + 轮廓线计数 + 差分：ICPC2025沈阳H
杨图计数 + 对角线性质 + 轮廓线计数 + 差分：ICPC2025沈阳H
Cute Young Diagram Counting - Problem - QOJ.ac
我们首先思考一下，翻转操作中，什么是不变的。
假设一个格子在 ，我们让其贡献到 里。不难证明， 序列是始终不变的。
序列的形式必然是：
接下来我们证明，所有满足此 序列的杨图必然是可以构造出来的。
首先，所有操作都是可逆的，因此我们只需要证明所有 序列相同的杨图可以通过某种方式调整到唯一一种杨图即可。
对于一个固定的 序列，我们贪心使第一行越长越好，然后递归进入第二行，变成归纳了。
对于一个固定的杨图，我们也是逐行贪心，使第一行越长越好。因此两种方法构造出来的最大杨图是唯一的，得证。
接下来就变成计数问题了，对于一个固定的 序列，如何统计有多少种合法的方案。
我们采用一种转化，把此计数问题改成轮廓线计数问题。
我们先把杨图的左边界和上边界无限延长
我们可以得到一些性质：
-
轮廓线必然是每个格子的外围
-
只有 相邻的格子其轮廓线才可能相邻
这个性质非常有用，它启示我们，我们只需要对相邻的轮廓线考虑即可。我
更进一步，我们只需要考虑相邻两种轮廓线之间的排列方式！
-
对于每个 的轮廓线数量，其实就是 。
因此我们可以维护 的差分序列，
接下来我们考虑两个相邻 轮廓线的组合计数，我们取反对角线，如下图所示：
（图中的 理论上要整体+1）
其中5的的外边界是绿色，6的外边界是黄色。我们还能继续瞪出很多性质：
- 最外围的两段肯定是黄色
- 中间肯定是连续两段黄色，连续两段绿色的随便排布。而这种排布必然合法且双射。
如果我们把两段视为一块，那么中间就有 块绿色， 块黄色，它们可以随便乱排，因此方案数为
由于相邻块之间独立，所以答案为
每次加入1行，只会导致4个 发生变化，简单维护一下即可。
时间复杂度
1 |
|
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2021-12-14
二项式定理
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15689044.html (a+b)n=∑k=0nCnkakbn−k\Large(a+b)^n=\sum_{k=0}^n C_n^ka^kb^{n-k} (a+b)n=k=0∑nCnkakbn−k 在化简一些式子时有用 因此，2n2^n2n （也就是当 a=b=1a=b=1a=b=1 ）时也可以表示为： 2n=∑k=0nCnkakbn−k\Large2^n=\sum_{k=0}^n C_n^ka^kb^{n-k} 2n=k=0∑nCnka...
2021-12-03
【CF1110E Magic Stones】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15640116.html 题目链接 我要是在noip前做这道题就好了。 这道题的本质就是noip2021方差中的一个性质，对于每个数进行修改，就是把它左右的差进行交换。 注意的是首项一定要一样。 Code 123456789101112131415161718192021222324252627282930313233343536373839// Problem: CF1110E Magic Stones// Contest: Luogu// U...
2021-12-01
【Loj #10099. 「一本通 3.6 例 2」矿场搭建】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15630249.html 题目链接 我们先对于有向图缩点，变成一棵树。 然后我们对于每个树上且在原图中的分割点节点所对应原图中的连通块考虑。 假设这里没有割点，很明显，只需要放2个出口即可。 如果有一个割点，说明这个点是树上的叶子节点，需要放1个出口。 如果有两个或以上的割点，无论哪个割点被割，都可以往另一个方向逃，所以这个连通块不用放。 Code 1234567891011121314151617181920212223242526272829...
2021-12-07
卢卡斯定理Lucas 定理小结
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15657340.html Lacus 求： Cmn mod p\Large C_m^n~mod ~p Cmn mod p 则： Cmn mod p=Cmpnp×Cm mod pn mod p mod p\Large C_m^n~mod~p=C_{\frac{m}{p}}^{\frac{n}{p}} \times C_{m~mod~p}^{n~mod~p}~mod~p Cmn mod p=Cpmpn×Cm mod pn mod p mo...
2026-07-19
《具体数学》2 Sum Study Note (2)
《具体数学》2 Sum Study Note (2) Repertoire method If we want to calculate : ∑i=1ni2\sum_{i=1}^n i^2∑i=1ni2, we can construct a recursion : {R0=αRn=Rn−1+β+γn+δn2\begin{cases} R_0 = \alpha \\ R_n = R_{n-1} + \beta + \gamma n + \delta n^2 \end{cases} {R0=αRn=Rn−1+β+γn+δn2 And it must satisfy : Rn=A(...
2021-12-21
【USACO2021 Convoluted Intervals 】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15716558.html 题目 The cows are hard at work trying to invent interesting new games to play. One of their current endeavors involves a set of NNN intervals (1≤N≤2⋅1051\le N\le 2\cdot 10^51≤N≤2⋅105), where the iiith interval star...