Todolist:118e 的形式化理解方法,做一下 abc426,感觉有点难度,abc425f 的 poly 做法,149d 的 universal 做法,有交合并的复杂度证明,1554e 更快的做法。
[ARC121E] Directed Tree
考虑容斥转化为 \(a_u\) 是 \(u\) 的祖先,这个还是不好算。\(a_u\) 是 \(u\) 的祖先也就是 \(u\) 在 \(a_u\) 的子树内,也就是逆排列的限制是子树。
钦定一个 \(S\),方案数是 \((-1)^|S| (n-|S|)! \prod_{i \in S}siz_i\),其中被钦定的点大小为 \(0\) 否则为 \(1\),也就是别的说的 \(siz-t\)。正确道理就是向上合并的过程中各个子树独立了,同时选自己符合题目中的限制,因此钦定不合法时不能选自己要 \(-1\),同时钦定了这个点因此子树内的点数就是钦定数 \(-1\),符号反过来就是 \(+1\) 恰好抵消。
改成树形 dp,设 \(f_{x,i}\) 表示 \(x\) 子树内 \(|S|=i\) 的容斥系数方案数和,先背包转移,再考虑钦定点就是 \(f_{x,i}=f_{x,i}-f_{x,i-1} \times (siz_x-i)\),这里 \(siz\) 是普通 \(siz\),防止重复更新要倒着算。
[ARC149D] Simultaneous Sugoroku
直接上大暴力,那就是分成 \(<0,>0\) 的部分加一个数,发现是值域有交平衡树合并。注意相同数要合并(但他们仍然存在,因此要用并查集表示指向了哪个数)否则复杂度会错,我也不知道为什么。
CF1554E.You
先来一遍莫反转化为计算倍数的形式。
实际上这样可能并不好做。首先在点上这个限制会非常麻烦,尝试用边描述限制,发现每条边只能给两侧的某一个端点做贡献,大概是一个给边定向的过程,指向的点就是这条边贡献到的 \(a\)。
由于我们考虑的是 \(a\) 而不是删除点的序列,所以只需要考虑定向是否和 \(a\) 构成双射即可,每次根据 \(a=0/1\) 给叶子定向后剥叶子即可得到唯一的定向因此是双射,答案总数是 \(2^{n-1}\)。
现在考虑 \(\gcd\) 的事,我们喜欢剥叶子,知道叶子的 \(a\) 值只能是 \(0/1\),如果 \(k>1\) 至少要求所有的点都是 \(k\) 的倍数,那么叶子必须是 \(0\),定好这些边的向后剥去她们,考虑新的叶子,因为是 \(k\) 的倍数所以大概也能定出向,但是不能保证是 \(k\) 的倍数了,也就是,父亲边怎么定向都不对,那这个 \(k\) 就达不到,否则也是唯一的方案。
剥叶子表现为拓扑排序,这样总复杂度是 \(\mathcal{O}(n^2)\),有 \(\gcd(a,b)=\gcd(a,a+b)\),所以原式的 \(\gcd\) 可以再添上一个 \(\sum a\) 项,这项一定是 \(n-1\),因此 \(k\) 必须是 \(n-1\) 的因数,这就是 \(\mathcal{O}(n \sqrt n)\) 的了。
还有判素因子的优化,但无人在意啊!