交易一中集训Day[4]

虽然今天有测试。。。但是还是不可避免地起晚了
事实证明,这个“先进”的冲水系统一点都不好用。。。。
什么都冲不下去

看到题之后瞬间就懵了。。。。
数论全家桶是什么鬼啊(╯‵□′)╯︵┻━┻
大胆猜一波性质。。。

你的公司有n个妹子,她们要开演唱会,第i个人有一个迷之分数$a_i$,观众对一组妹子的满意度定义为这些妹子迷之分数的平均数减去中位数,你需要选出一些妹子参加比赛,使得观众的满意度最大。
输出保留四位小数
$n \leq 200000 , 0 \leq a_i \leq 10^9$
样例输入
4
1 2 3 12
样例输出
3.0000

手玩了样例猜测选前两个和最后一个,特判N<=2去玩后面。。。。。。
T2奥妙重重的排列数 T3奥妙重重的组合数
xjb打表找规律。。。。T2在OEIS上查到了递推式。。。。
T3根本找不到。。。。。
快结束前又返回去拍了一下T1。。。。。 三下就WA。。。
又观察了一下数据。。。。
大胆猜测两头取相同个数再到较小的一端取中位数。。。。 又拍还WA。。。于是弃疗。。。。
结果下午出成绩发现A了。。。。还莫名其妙成了Rank1。。。。。 瑟瑟发抖

下午是FFT和杂题选讲。。。。

xjk光速过ppt看得我一脸懵逼。。。。不现推一下感觉非常懵逼。。。。
还好有算导。。
大概就是求两个多项式的乘积可以先把这两个系数表达多项式换成等价的点值表达,然后点值表达就可以$O(n)$直接乘过去,乘出来的多项式次数是原来两个多项式次数的和,所以原来两个多项式都需要用$m+n$个点值对表示,乘完之后再把结果插成系数表达。
于是问题来了,怎么快速求点值表达以及插回系数表达

FFT通过恰当地选择x降低求值和插值的复杂度
首先引入单位复数根即满足$\omega^n=1$的复数$\omega$,对于$k=0,1,\dots,n-1$,这些根是$\mathrm{e}^{2\pi\mathrm{i}k/n}$
由复数的指数形式的定义 $$\mathrm{e}^{iu}=\cos(u)+\mathrm{i}\sin(u)$$
得 $$ω_n^k=\cos(2\pi k/n)+\mathrm{i}\sin(2\pi k/n)$$
这个东西有很多非常优雅的性质:

  • (消去引理)对任意整数$n \geq 0,k \geq 0,d \geq 0$,有
    $$\omega^{dk}_{dn}=(\mathrm{e}^{2\pi\mathrm{i}/dn})^{dk}=(\mathrm{e}^{2\pi\mathrm{i}/n})^{k}=\omega^{k}_{n}$$

  • (折半引理)如果$n>0$且$n$为偶数,那么$n$个$n$次单位根的平方的集合就是$n/2$个$n/2$次单位根的集合,且每个元素恰好出现两次。

  • (求和引理)对于任意整数$n\geq1$和不能被$n$整除的整数$k$,有$$\sum_{j=0}^{n-1}(\omega_n^k)^j=0$$

这个折半引理是坠重要的,有了它我们就可以像香港记者一样快了,它保证了递归子问题的规模只有递归调用前的一半。

我们希望计算次数为$n$的多项式 $$A(x)=\sum_{j=0}^{n-1}a_jx^j$$ 在$\omega_n^0,\omega_n^1,\omega_n^2,\dots,\omega_n^{n-1}$处的值,所以对$k=0,1,2,\dots,n-1$
$$y_k=A(\omega_n^k)=\sum_{j=0}^{n-1}a_j\omega_n^kj$$
我们可以把多项式 $$A(x)=\sum_{j=0}^{n-1}a_jx^j$$ 拆成两个$n/2$次的新多项式 $$A^{[0]}=a_0+a_2x+a_4x^2+\dots +a_{n-2}x^{n/2-1}$$ $$A^{[1]}=a_1+a_3x+a_5x^2+\dots +a_{n-1}x^{n/2-1}$$ 则 $$A(x)=A^{[0]}(x^2)+xA^{[1]}(x^2)$$ 于是把问题转化为了求$A^{[0]}(x)$和$A^{[1]}(x)$在$(\omega_n^0)^2,(\omega_n^1)^2,\dots,(\omega_n^{n-1})^2$处的值
由折半引理可知$x^2$的取值只有$n/2$个
所以成功的缩小了子问题的规模,复杂度$O(n \lg n)$ 至于插值有(详见算导)
$$a_j=\frac{1}{n}\sum_{j=0}^{n-1}y_k\omega_n^{-kj}$$
然后再观察找规律法实现迭代计算
cpp

此条目发表在未分类分类目录。将固定链接加入收藏夹。