联合省选2022

标签：le 2022 省选 sum sqrt 复杂度 联合 pi 质数

预处理器(1)

按照题目内容模拟即可，时间复杂度为\(O(n^{2}L)\)

---

填树(2)

当确定修改路径的端点后，假设区间构成序列\(\{[l_{m},r_{m}]\}\)​，则答案即

\[\sum_{x}\prod_{i=1}^{m}|[x,x+K]\cap [l_{i},r_{i}]|-\prod_{i=1}^{m}|(x,x+K]\cap [l_{i},r_{i}]| \]

显然两式是类似的，不妨仅考虑前者

注意到这是一个关于\(x\)的分\(O(n)\)段的\(O(n)\)次函数，求和后次数仅\(+1\)，进而仅需插出\(O(n^{2})\)个值

当确定\(x\)后，即求所有路径权值乘积和，容易用树形dp求得，时间复杂度为\(O(n^{3})\)

---

学术社区(4)

参考这里

---

卡牌(2)

记给定质数集合为\(P\)（去重），则答案即\(\sum_{S\subseteq P}(-1)^{|S|}2^{\sum_{i=1}^{n}[\forall p\in S,p\not\mid s_{i}]}\)

记\(V=\max s_{i}\)，则将质数按\(\le \sqrt{V}\)和\(>\sqrt{V}\)分类：

• 对于\(\le \sqrt{V}\)的质数，仅\(\pi(\sqrt{V})\)个（本题中\(\le 14\)），可以暴力枚举
• 对于\(>\sqrt{V}\)的质数，在确定前者后影响独立，即带来\(1+\frac{1}{2^{\alpha}}\)的贡献系数

预处理出\(\alpha\)，时间复杂度为\(O(n+V2^{\pi(\sqrt{V})}+2^{\pi(\sqrt{V})}\sum c_{i})\)

---

序列变换(4)

参考这里

---

最大权独立集问题(4)

参考这里

标签：le,2022,省选,sum,sqrt,复杂度,联合,pi,质数
From： https://www.cnblogs.com/PYWBKTDA/p/17226224.html