10.9

标签：hvy 10.9 sum lit cdot 连续 区间

不会数学真是抱歉了！
不会 dp 真是抱歉了！

说好的 \(NOIP\) 模拟赛呢，开幕给我端上来这么一坨。

明天有体育课。

A.树上独立集

贪心，设 \(f_i\) 代表 \(i\) 子树内有多少个未匹配点，若 \(\sum\limits_{v\in son_u}f_v>0\) 则 \(f_i=\sum\limits_{v\in son_u}f_v-1\) ，否则 \(f_i=1\) ，若当前添加了 \(n\) 个点，那么答案为 \(f_1+\frac{n-f_1}{2}\) 。

动态加点怎么办呢怎么办呢？

离线下来，先把最后的树建出来进行一个树剖，然后类似动态 $dp $ 的思想，线段树维护重链，同时用数组记录轻儿子贡献。
设 \(hvy_i\) 代表 \(i\) 向下的重链上的未匹配点数，\(lit_i\) 代表 \(i\) 子树内非重链上点的未匹配点数，那么合并线段树左右区间时，由于线段树维护 \(dfn\) 序，所以左区间是右区间的父亲，设 \(a\) 为左区间，\(b\) 为右区间，则：

node operator+(node a,node b)
{
	if (a.hvy >= b.lit) a.hvy -= b.lit;
	else a.lit += b.lit-a.hvy,a.hvy = 0;
	a.hvy += b.hvy;
	return a;
}

动态加点，我们就跳重链同时更新链上节点信息即可，复杂度 \(O(n\log^2n)\) 。
由于重链上的点可以两两匹配，所以 \(f_i = hvy_i\bmod2+lit_i\) 。

B.排列计数

赛时读错题了 \(30\rightarrow 5\)。
无所谓，题解百分百！

记 \(k=r-l+1\)。
考虑置换环，排列 \(p\) 做一次置换相当于每个位置变为置换环上的下一个位置。如果排列 \(p\) 在区间 \([l,r]\) 上是值域连续段，那么该区间做一次置换后也是一个区间。因为 \(p\) 做任意次置换后 \([l,r]\) 都是值域连续段，所以如果从 \([l,r]\) 开始不断在置换环上向后跳，则每次跳到的都是一个区间，且最终会回到 \([l,r]\)。我们考察从 \([l,r]\) 向后跳到的区间。
如果这些区间互不相交，则在置换环上，这些区间构成一个圆排列。每一段区间都是值域连续段，在确定该区间跳到的区间后，它的值域也确定了，并且内部可以任意排列。因此这部分对答案的贡献是：

\[\sum_{i=1}^{\left\lfloor \frac{n}{k}\right\rfloor} (k!)^i\cdot (i-1)!\cdot (n - ik)! \cdot F_{i,l-1,n-r,k} \]

其中

\[F_{i,x,y,k}=\sum_{j = 0}^{i-1} \binom{x-j(k-1)}{j}\binom{y-(i-j-1)(k-1)}{i-j-1} \]

对于相交的情况，有结论：如果将所有相交的区间合并成一个连续段，则每一个连续段有且仅有两个区间，且所有连续段长度相同。在通过置换环向后跳的过程中，会首先依次经过每个连续段中的一个区间，再按相同的顺序经过每个连续段中的另一个区间，最后回到初始区间。
若一个连续段是区间 \([l_1,r_1]\) 与区间 \([l_2,r_2]\) 构成的，设 \(l_1<l_2\)，若区间 \([l_1,r_1]\) 中的最小值小于区间 \([l_2,r_2]\) 中的最小值，则称该连续段是上升的，否则是下降的。
假设一共形成了 \(m\) 个连续段，这些连续段的指向关系会构成一个圆排列，并且其中一定有奇数个下降的连续段。类似于不交的情况，不妨设 \([l,r]\) 所在的连续段是上升的，该部分的贡献是：

\[\sum_{d=1}^{k-1} \sum_{i=1}^{\left\lfloor \frac{n}{k}\right\rfloor} 2^{i-1}\cdot \left((k-d)!^2\cdot d!\right)^i\cdot (i-1)! \cdot \left(n-i(2k-d)\right)!\cdot F_{i,l-1,n-r-k+d,2k-d} \]

\(F\) 可以用 NTT 计算。时间复杂度 \(\mathcal{O}\left(n\log n\right)\)。

C.猜数游戏

题面还没看过。

标签：hvy,10.9,sum,lit,cdot,连续,区间
From： https://www.cnblogs.com/ZepX-D/p/18454954