wrpwrpのBlog

好久以前的笔记拿过来存一下。 保序回归问题参考2018年集训队论文《浅谈保序回归问题》 问题描述注意这里的偏序关系是非严格偏序关系。给定正整数 $p$, 一张有向无环图 $G$, 以及代价函数 $(y_i, w_i) (\forall i, w_i > 0)$。如果在 $G$ 中有 $v_i \rightarrow v_j$ 的有向路径， 那么存在偏序关系 $v_i \leq v_j$ 。求点值序列 $f$, 满足 $\forall v_i \leq v_j (i, j \in [1, n])$ , 有 $f_i \leq f_j$, 最小化下列回归代价。$$\sum_{i = 1}w_i|f_i - y_i|^p, 1 \leq p < \infty$$$$\max_{i = 1}w_i|f_i - y_i|, p = \infty$$对于相同的 $p$, 称作 $L_p$ 问题。 一些约定 将序列 $z$ 中不超过 $a$ 的元素变为 $a$ ，不小于 $b$ 的元素变为 $b$ 称为序列 $z$ 向集合$S = {a, b}$ ...

用途 求积性函数前缀和。 要求该积性函数在质数点的取值为关于$p$的多项式或者可以用完全积性函数模拟出来。 简介$\text{Min25}$筛还有一个本质上等价的筛法叫洲阁筛， 其本质来源于扩展的线性筛法。不妨考虑一下线性筛法的复杂度瓶颈， 其统计答案利用的是枚举每个质因子去贡献其倍数的答案， 然后利用每个数被最小质因子筛去一次的性质进行答案计算。但是事实上在线性筛的过程中在大于$\sqrt{n}$的质因子的贡献方式相当劣， 实际上只贡献了自己的答案， 考虑根号分治优化这个过程， 然后就有了$\text{Min25}$和洲阁筛两个基于根号分治的筛法。 求解大体分三个步骤。 筛出$1\dots\sqrt{n}$中的质数。 求解质数处函数的取值。 求解合数处函数的取值。 不妨设答案为：$$\sum_{i = 1}^nf(i)$$ 求质数点为了后文的推导， 使用多个完全积性函数代替原来的$f$函数。不妨将这个函数记作$f_0$。考虑设数组$g$， 其意义为：$$g(n, j) = \sum_{i = 1} ^ nf_0(i)[i是质数或者i的最小质因子大于 ...

[TOC] 常用快读快写1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677class Input { #define MX 1000000 private : char buf[MX], *p1 = buf, *p2 = buf; inline char gc() { if(p1 == p2) p2 = (p1 = buf) + fread(buf, 1, MX, stdin); return p1 == p2 ? EOF : *(p1 ++); } public : Input() { #ifdef Open_File freopen("a.in", "r", stdin); freopen("a.out", &quo ...