【Ynoi#32】【Ynoi2014】等这场战争结束之后
首先把操作树建出来，然后值域分块。
用可撤销并查集维护连通块，记录每个连通块在每个块中的出现次数。
查询先定位整块，散块只需要在离散化的时候不去重，暴力找即可。
感觉远远没有达到黑的水平。
\(O(m\sqrt{n\log n})\)
1 |
|
【Ynoi#31】【Ynoi2019 模拟赛】 Yuno loves sqrt technology III
2023年第一道洛谷
一句话题意就是静态区间众数出现次数。
分块，先预处理出 \(l\) 到 \(r\) 块内出现的众数出现次数。
然后考虑散块的部分，对于新添加的一个数，我们查询他在区间里出现的次数即可，但是这样二分带 log。
解决方法对于当前的 \(ans\)，对于（以右边部分散块为例）一个新的数 \(a_k\)，找 \(a_k\) 前面第 \(ans\) 个位置，判断他是否在这个区间内，如果是，\(ans:=ans+1\)，然后一步一步往前跳。
这样均摊下来每个散块里的位置只会被跳一遍，复杂度 \(O((n+m)\sqrt n)\)。
应当说是 Ynoi 里面相当简单的一道题，也不卡常。
1 | #include <bits/stdc++.h> |
《近似算法设计》第三章习题
Posted on
Edited on
3.1
对于一个最优解 \(O\)，我们把他分成两部分，第一部分是按照 \(v_k/s_k\) 从大到小排序之后选出来的一个前缀，记这部分的价值为 \(\nu_1\)，大小记为 \(\sigma_1\)，剩下的部分是第二部分，代价记为 \(\nu_2\)，大小记为 \(\sigma_2\)
若 \(\nu_1\) 大于 \(\nu_2\)，则按照第一种选法选出来的价值 \(\geq \nu_1\geq (1/2)OPT\)
若 \(\nu_1\) 小于 \(\nu_2\)，设第一部分的下一个为 \(k\)，则 \(s_k>\sigma_2\)，因为 \(v_k/s_k\geq \nu_2/\sigma_2\)，\(v_k\geq \nu_2\geq (1/2)OPT\)
3.2
设 3.1 得到的结果为 \(M\)，将所有的 \(v_i\) 变为 \(\lfloor nv_i/\epsilon M\rfloor\)，则
\[\sum_{k\in O}v^\prime _k\leq \frac{n}{\epsilon M}\sum_{k\in O} v_k=\frac{2n}{\epsilon}\]
因此可以将 dp 的上限设为 \(n/\epsilon\)，最终复杂度为 \(O(n^2/\epsilon)\)
3.3
\(O(nW)\) 的做法就是一个很显然的 dp，维护最小值即可。
考虑我们要求一个 \((1-\epsilon)\) 近似，设 \(\mu=\epsilon W/n\)，设 \(w_i^\prime=\lfloor w_i/\mu\rfloor\)，对于 \(w^\prime_i\) 做上面的 dp，设我们得到的对应选出的集合为 \(S\)，真实最优解为 \(O\)
\[ \begin{aligned} \sum_{i\in S}w_i&\geq \mu\sum_{i\in S}w^\prime_i \\ &\geq \mu \sum_{i\in O}w^\prime_i \\ &\geq \sum_{i\in O}w_i-\mu|O| \\ &\geq OPT-\mu n \\ &\geq OPT-\epsilon W \\ &\geq (1-\epsilon)OPT \end{aligned} \]
即解决。
3.4
不会。
原论文是俄语的看不懂（
3.5
dp 还是好搞的，用 \(f(i,t_1,t_2,\cdots,t_m)(t_1\geq t_2\geq \cdots \geq t_m)\) 表示前 \(i\) 个任务安排好了，各个处理器用时是多少 最后的代价最小是多少。
下面考虑怎么确定 \(OPT_m\) 的范围，一个比较显然的界是 \(OPT_m\geq \dfrac{1}{m}OPT_1\)，其中 \(OPT_1\) 表示只有一个处理器的最优值，这个可以直接 \(O(n)\) 算出来。（实际上似乎有更优的界 \(OPT_m\geq \dfrac{n+m}{(n+1)m}OPT_1\)，但是 \(1/m\) 已经足够）
为了实现近似算法，我们需要换一种 dp 的形式，感觉在 OI 里也见到过。
设 \(G(i,T)\) 表示满足 \(f(i,t_1,\cdots,t_m)=T\) 的 \((t_1,\cdots,t_m)\) 的集合。
一个引理是对于相同的 \(T\) ，最多只有 \(n^{m-2}\) (感觉可以 generalize，但是似乎 \(m>2\) 会有一些 casework)个不同的 \((t_1,\cdots,t_m)\) 是有用的，其他的一些是显然不优的。（如对于 \(m=2\) 我们只需要保留一个）
设 \(\mu=\dfrac{\epsilon}{nm}OPT_1\)，对于 \(G(i,T)\) 的每一个 \(T\)，我们用 \(\lfloor T/\mu \rfloor\) 来替代他，维护 \(G(i,T^\prime)\) 中的 \(n^{m-2}\) 个元素一一进行转移。
这样的话，每一步 \(T\) 上的误差不超过 \(\mu\)，最终的总误差不超过 \(\dfrac{\epsilon OPT_1}{m}\leq \epsilon OPT_m\)。
复杂度为 \(O(n^m/\epsilon)\)，实现了 FTAS。
【P#2】游磐越
常期时来行古道，征程今朝把景收。
若松三月吹樱雪，江城半日悬海楼。
千年孤烟道尚在，一朝风雨路未休。
人生海海多惆怅，且行宇内纵神游。
【M#2】 Cesaro 和, Abel 和
Cesaro Sum
在考虑一个级数的和的收敛的时候，我们可能会遇到一些问题，比如对于这样一个级数：
\[1,-1,1,-1,1,-1,1,\cdots \tag{1}\]
他的部分和 \(s_n=[n \text{ is odd}]\)，在常规的意义下他是不可和的，但是他的部分和又表现出了一些收敛的性质。
比如对于这个数列，他的部分和在一半的情况下是 \(1\)，一半的情况下是 \(0\)，那么我们把这个和的极限定义为 \(1/2\) 是在一定程度上合理的。
所以我们可能需要一些更强的收敛性质。
\(\color{red}{定义1}\): 定义
\[\sigma_n=\frac{\sum_{k=0}^{n-1} s_k}{n}\]
为级数 \(\{z_n\}\) 的第 \(n\) 个 Cesaro 和，其中 \(s_n\) 为 \(z_n\) 的部分和。
如果 \(\sigma_n\) 收敛，则称 \(\{z_n\}\) 是 Cesaro 可和的。
在这个定义下，不难验证 \((1)\) 中的 Cesaro 和收敛于 \(1/2\)。
Dirichlet Kernal & Fejer Kernel
回忆 Dirichlet Kernel 定义为
\[D_n(x)=\sum_{k=-n}^n e^{inx}=\frac{\sin(n+\dfrac{1}{2})x}{\sin \dfrac{x}{2}}\]
且满足
\[S_n(f)(x)=(f*D_n)(x)\]
我们对于 \(f\) 求 Cesaro 和，得到
\[\sigma_n(f)(x)=\frac{S_0(f)(x)+S_1(f)(x)+\cdots+S_{n-1}(f)(x)}{n}=(f*K_n)(f)(x)\]
其中 \(K_n\) 为 Fejer Kernel，定义为
\[K_n(x)=\sigma_n(D_n)(x)=\frac{\sin^2 \dfrac{nx}{2}}{n\sin^2\dfrac{x}{2}}\]
注意到 \(K_n\) 满足 Good Kernel 的所有性质，这直接得到了 Fejer 定理：
\(\color{red}{定理1}\): 如果 \(f\) 可积，则 \(f\) 的傅里叶级数在每一个 \(f\) 的连续点处 Cesaro 可和；进一步的，如果 \(f\) 连续，则 \(f\) 的傅里叶展开的 Cesaro 和一致收敛与 \(f\)
Abel Sum
\(\color{red}定义2\): 对于级数 \(\{z_n\}\)，对于 \(0\leq r<1\)，定义
\[A(r)=\sum_{k=0}^\infty z_kr^k\]
若 \(A(r)\) 收敛，且
\[\lim_{r\to 1}A(r)=s\]
则称 \(\{z_n\}\) Abel 可和于 \(s\), \(s\) 被成为 Abel 均值。
Abel 可和强于 Cesaro 可和，如对于级数
\[1,-2,3,-4,\cdots \tag{2}\]
\[A(r)=\sum_{k=0}^\infty (-1)^k(k+1)r^k=\frac{1}{(1+r)^2}\]
是 Abel 可和的。
但是他不是 Cesaro 可和的，因为
\(s_k=\lceil k/2\rceil (-1)^{k+1}\)，\(s_k\) 的前缀和要么是 \(0\) 要么是 \(n/2\)，他的 Cesaro 部分和要么是 \(0\) ，要么是 \(1/2\)，并不收敛。
Poisson Kernel
Abel 和对应的 Kernel 是 Poisson Kernel。
对于一个函数 \(f(\theta) \sim \sum_n a_ne^{in\theta}\)，定义这个函数的 Abel 均值
\[A_r(f)(\theta)=\sum_{n}a_nr^{|n|}e^{in\theta}\]
定义 Poisson Kernel \(P_r(\theta)\)满足 \(A_r(f)(\theta)=(f*P_r)(\theta)\)
则
\[P_r(\theta)=\sum_n r^{|n|}e^{in\theta}\]
进一步展开得到
\[P_r(\theta)=\frac{1-r^2}{1-2r\cos\theta+r^2}\]
\(P_r(\theta)\) 同样是 Good Kernel，因此将定理1中的 Cesaro 可和结论替换为 Abel 可和结论同样成立。
Summable & Cesaro Summable & Abel Summable
在本节中，我们将证明三种可和是有强弱关系的，具体来说
\[\text{Summable} \Longrightarrow \text{Cesaro Summable} \Longrightarrow \text{Abel Summable}\]
\(\color{red}{定理2}\): 若 \(\sum_{k=1}^{\infty} z_k=s\)，则 \(\{z_n\}\) Cesaro 可和，且 \(\sigma=s\)
证明是基本的。
在前面已经提到过，存在数列是 Cesaro 可和但不是可和的。
\(\color{red}{定理3}\)：若 \(\{z_n\}\) Cesaro 可和，则 \(\{z_n\}\) Abel 可和，且 \(\lim_{r\to 1} A(r)=\sigma\)
证明：
假设 \(\sigma=0\)，否则可以调整 \(z_1\)。
\[A(r)=\sum_{n=0}^{\infty}z_nr^n = (1-r)^2\sum_{n=0}^{\infty}n\sigma_nr^n\]
两边在 \(r\to 1\) 时取极限，得到 \(A(r)\to 0\)。
前面同样举出了是 Abel 可和但是不 Cesaro 可和的例子，这完成了单向关系的构建。
Tauber's Theorem
当然，在对于 \(z_n\) 加以额外的限制的情况下，上面三个不同的可和性可以变为等价的。
\(\color{red}{定理4}\)：若 \(z_n\) Cesaro 可和于 \(\sigma\)，且 \(c_n=o(1/n)\)，则 \(z_n\) 可和于 \(\sigma\)
证明：
\[s_n-\sigma_n=\frac{(n-1)z_n+(n-2)z_{n-1}+\cdots +z_2}{n}\]
两边对 \(n\) 取极限。
\(\color{red}{定理5}\)：若 \(z_n\) Abel 可和于 \(A\)，且 \(c_n=o(1/n)\)，则 \(z_n\) 可和于 \(A\)
取 \(r=1-1/n\)
\[ \begin{aligned} |s_n-\sum_{k=1}^n z_kr^k| &=|\sum_{k=1}^n z_k-\sum_{k=1}^n z_k(1-\frac{1}{n})^k| \\ &\leq |\sum_{k=1}^n z_k(1-(1-\frac{1}{n}))^k| \\ &\leq |\sum_{k=1}^n \frac{kz_k}{n}| +o(1/n) \\ \end{aligned} \]
对 \(n\) 取极限，即证。
Steins 傅里叶分析 第二章部分习题解答
Exercise
9
定义
\[\chi_{[a,b]}(x)=[x\in[a,b]]\]
求其在 \([-\pi,pi]\) 上的傅里叶展开
证明该展开在 \(a,b\neq \pi\) 且 \(a\neq b\) 时不绝对收敛
证明该展开在任意一点收敛
(1)，易得
\[f(x)\sim \frac{b-a}{2\pi}+\sum_{n\neq 0}\frac{e^{-ina}-e^{-inb}}{2\pi in}e^{inx}\]
取 \(x=\dfrac{a+b}{2}\)，注意到最后是 \(\sum \dfrac{\sin n\frac{b-a}{2}}{\pi n}\) 的形式，而 \(|\sin \dfrac{b-a}{2}|\) 在大部分地方 \(\geq \epsilon >0\)，因此不绝对收敛。
\(a=b\) 和 \(a=-\pi,b=\pi\) 的情况易证。
\[\hat f(n)e^{inx}+\hat f(-n)e^{-inx}=\frac{\sin n(x-a)-\sin n(x-b)}{\pi n} \]
考虑级数 \(\sum \sin n(x-a)-\sin n(x-b)\) 的部分和
\[ \begin{aligned} \sum_{n=1}^N \sin n(x-a)-\sin n(a-b)&=\frac{\sin \dfrac{N(x-a)}{2}\sin \dfrac{(N+1)(x-a)}{2}}{\sin \dfrac{x-a}{2}}[x\neq a] \\ &- \frac{\sin \dfrac{N(x-b)}{2}\sin \dfrac{(N+1)(x-b)}{2}}{\sin \dfrac{x-b}{2}}[x\neq b] \\ & \leq \frac{1}{\sin \dfrac{x-a}{2}}[x\neq a] + \frac{1}{\sin \dfrac{x-b}{2}}[x\neq b] = O(1) \end{aligned} \]
由 A-D 判别法，\(\{\dfrac{1}{n\pi}\}_n\) 单调收敛于 0， \(\sum \sin n(x-a)+\sin n(x-b)\) 有界，因此 \(\sum \hat f(n)e^{inx}+\hat f(-n)e^{-inx}\) 收敛。
MIT Integration Bee 2023 - Final 题目解答
1
\[\int_0^{\pi/2}\frac{\sqrt[3]{\tan x}}{(\cos x+\sin x)^2}\mathrm dx\]
\[ \begin{aligned} I &= \int_0^{\pi/2}\frac{\sqrt[3]{\tan x}}{(1+\tan x)^2}\mathrm d\tan x \\ &=\int_0^{\infty}\frac{t^{1/3}}{(1+t)^2}\mathrm dt \\ &=\mathcal B(\frac{4}{3},\frac{2}{3}) \\ &=\Gamma(\frac{4}{3})\Gamma(\frac{2}{3}) \\ &=\frac{\Gamma(\dfrac{1}{3})\Gamma(\dfrac{2}{3})}{3} \\ &=\frac{2\pi}{3\sin\dfrac{\pi}{3}} \\ &= \frac{2\sqrt 3}{9}\pi \end{aligned} \]
2
\[\int_0^\pi \Big(\frac{\sin 2x\sin 3x\sin 5x\sin 30x}{\sin x\sin 6x\sin 10x\sin 15x}\Big)^2\mathrm dx\]
先用二倍角公式上下抵消一下，得到
\[I=\int_0^\pi \Big(\frac{\cos x\cos 15x}{\cos 3x\cos 5x}\Big)^2\mathrm dx\]
然后用三倍角公式展开，得到
\[I=\int_0^\pi\Big(\frac{4\cos^2 5x-3}{4\cos^2 x-3}\Big)\mathrm dx=\int_0^\pi\Big(\frac{2\cos 10x-1}{2\cos 2x-1}\Big)^2\mathrm dx\]
然后做变换 \(t=2x\)，得到
\[I=\frac{1}{2}\int_0^{2\pi} \Big(\frac{2\cos 5x-1}{2\cos x-1})^2\mathrm dx\]
对这个东西傅里叶展开，得到
\[-1-2\cos x+2\cos 3x+2\cos 4x\]
这个的平方在 \(0\) 到 \(2\pi\) 积分，因为 \(\sin kx\) 是正交的，所以只需要考虑平方的积分，除了常数项是 \(2\pi\) 其他的都是 \(\pi\)，因此
\[I=\frac{1}{2}(2\pi+4\pi+4\pi+4\pi)=7\pi\]
3
\[\int_{-1/2}^{1/2}\sqrt{x^2+1+\sqrt{x^4+x^2+1}}\mathrm dx\]
\[ \begin{aligned} I&=2\int_0^{1/2}\sqrt{\Big(\sqrt{\frac{x^2+x+1}{2}}+\sqrt{\frac{x^2-x+1}{2}}\Big)^2}\mathrm dx \\ &= \sqrt 2\int_0^{1/2}\sqrt{x^2+x+1}\mathrm dx+\sqrt 2\int_0^{1/2}\sqrt {x^2-x+1}\mathrm dx \end{aligned}\]
后面就是基本的套公式了。
\[I=\frac{\sqrt 7}{2\sqrt 8}+\frac{3}{4\sqrt 2}\ln |\frac{\sqrt 7+2}{\sqrt 3}|\]
4
感觉做法挺一眼的，就是可能如果不让用计算器的话最后计算数值解会有些困难？
5
\[\int_0^1 \Big(\sum_{n=1}^\infty\frac{\lfloor 2^nx\rfloor}{3^n}\Big)^2\mathrm dx\]
神仙题呜呜呜
stackexchange 上抄的初等做法。
\[I_a:=\int_0^a \Big(\sum_{n=1}^\infty\frac{\lfloor 2^nx\rfloor}{3^n}\Big)^2\mathrm dx\]
则对于 \(I_1\)，我们有两种处理方法，一种是做变换 \(t=x/2\)，一种是做变换 \(t=x-1/2\)，这两种都可以得到一个 \(I_1\) 和 \(I_{1/2}\) 的关系、
首先做变换 \(t=x/2\)
\[ \begin{aligned} I_1 &= 2\int_0^{1/2}\Big(\sum_{n=1}^\infty\frac{\lfloor 2^{n+1}x\rfloor}{3^n}\Big)^2 \mathrm dx \\ &= 2\int_0^{1/2}\Big(3\sum_{n=\color{red}1}^\infty\frac{\lfloor 2^nx\rfloor}{3^n}\Big)^2 \mathrm dx \\ &= 18 I_1 \end{aligned} \]
注意红色的地方，本来是没有这一项的，但是因为 \(\lfloor 2x\rfloor\) 对于 \(x\in (0,1/2)\) 都是 \(0\)，所以可以添上这一项。
接下来做变换 \(t=x-1/2\)
\[ \begin{aligned} I_1 &= \int_0^{1/2}\Big(\sum_{n=1}^\infty\frac{\lfloor 2^nx\rfloor}{3^n}\Big)^2\mathrm dx+\int_{1/2}^1 \Big(\sum_{n=1}^\infty\frac{\lfloor 2^nx\rfloor}{3^n}\Big)^2 \mathrm dx \\ &= I_{1/2}+\int_0^{1/2}\Big(\sum_{n=1}^\infty\frac{\lfloor 2^nx\rfloor}{3^n}-\sum_{n=1}^{\infty}\frac{2^{n-1}}{3^n}\Big)^2 \mathrm dx \\ &= I_{1/2}+\int_0^{1/2}\Big(\sum_{n=1}^\infty\frac{\lfloor 2^nx\rfloor}{3^n}-1\Big)^2\mathrm dx \\ &= 2I_{1/2}+2\int_0^{1/2}\sum_{n=1}^\infty \frac{\lfloor 2^n x\rfloor}{3^n}\mathrm dx+\frac{1}{2} \end{aligned} \]
这个一次项的积分是好做的。
\[ \begin{aligned} \int_0^{1/2}\frac{\lfloor 2^n x\rfloor}{3^n}\mathrm dx &= \frac{1}{6^n}\int_0^{2^{n-1}}\lfloor x \rfloor \mathrm dx \\ &= \frac{1}{6^n}\frac{1}{2}2^{n-1}(2^{n-1}-1) \\ &= \frac{2^{n-1}-1}{4\times 3^n} \end{aligned} \]
等比数列求和得到
\[\int_0^{1/2}\sum_{n=1}^\infty \frac{\lfloor 2^n x\rfloor}{3^n}\mathrm dx=\frac{1}{8}\]
带入 \(I_{1/2}=I_1/18\)，有
\[I_1=\frac{I_1}{9}+\frac{3}{4}\]
整理即得
\[I_1=\frac{27}{32}\]
【鲜花#5】Aizu Glimpse - 新雪
Posted on
In
生活记录
天空是绯色的，就像沙尘暴。
早上进学校的时候发现小猫还活着，不知道该为他们感到高兴还是感到悲哀。
雪花白了我的发迹，引得涂洁对我指手画脚。
今天换了羽绒服，于是没戴手套。
课间玩雪，寒冰红润了我的双手。
滚起雪球，为了雪球最终化为水。
出校门，风平浪静，冰冷渐渐刺进我的躯干。
校门口有两个小贩，卖冰糖葫芦。
第一个小贩在校门口的有利位置，还提供了 Extra Service - 卖烤肠。
他的生意相当的好。
第二个小贩在校门口出去走一段路的不利位置，还不会营销，他卖的是糖雪球。
这么说来还挺应景。
小贩在这一学期重新出现了，不知道应当感到高兴还是悲哀。
大概还是高兴的好，因为相当小贩的人本没有消失，只是曾经被强制抹去了。
冰封，等公交车。
小学生们愉快的打着雪仗。
一个小男孩对另一个小女孩说“去年就下了一次雪”。
第一反应想，原来去年就下了一次雪啊。
转念一想，这一次雪是什么时候呢？
大概还记得去年发生了什么的人已经相当的少了吧。
原来去年我在杭州见过雪。
但是去年北京的雪在哪里呢？
原来去年是我从杭州回来的日子。
葡萄牙被淘汰已经一年了。
从五点睡到六点半，起来赶火车的故事也已经快要忘了吧。
果然寒冷的天气是好的。
寒冷的天气让人警醒。
微醺。
上一次喝醉是什么时候？
好像那时候子达哥还在。
喝酒是好的，让人温暖。
也让人麻痹。
小同学们去三亚了。
我的三亚就这样被疫情偷走了。
我的三年就这样被疫情偷走了。
什么都变了。
MIT Integration Bee 2023 - Semifinal 部分题目解答
感觉 Semifinal 除了 1.3 和 2.3 神题以外其他的反而比较常规。
1.1
\[\int e^{\cos x}\cos(2x+\sin x)\mathrm dx\]
\[ \begin{aligned} I &=\int e^{\cos x}\cos(x+(x+\sin x))\mathrm dx \\ &= \int e^{\cos x}\Big((1+\cos x)\cos(x+\sin x)-\sin x\sin (x+\sin x)\Big) \mathrm dx-\int e^{\cos x}\cos(x+\sin x)\mathrm dx \\ &= e^{\cos x}\sin(x+\sin x)-\int e^{\cos x}\Big(\cos x\cos\sin x-\sin x\sin\sin x)\mathrm dx \\ &= e^{\cos x}\sin (x+\sin x)-e^{\cos x}\sin\sin x \end{aligned} \]
1.2
不会。
直接扔个 StackExchange
讲真这题神了（
1.3
\[\int_0^\pi \frac{1\cos x-\cos 2021x-2\cos 2022 x-\cos 2023 x+2}{1-\cos 2x}\mathrm dx\]
\[ \begin{aligned} I &=\int_0^\pi \frac{2\cos x+2-(\cos 2021x+\cos 2022 x)-(\cos2022 x-\cos 2023 x)}{1-\cos 2x}\mathrm dx \\ &=\int_0^\pi \frac{2\cos x+2-2\cos\dfrac{x}{2}\Big(\cos\dfrac{4043}{2}x+\cos\dfrac{4045}{2}x\Big)}{1-\cos 2x}\mathrm dx \\ &= \int_0^\pi \frac{2\cos x+2-4\cos^2\dfrac{x}{2}\cos 2022 x}{1-\cos 2x}\mathrm dx \\ &= \int_0^\pi \frac{4\cos^2\dfrac{x}{2}(1-\cos 2022x)}{2\sin^2 x}\mathrm dx \\ &= \int_0^\pi \frac{1-\cos 2022x}{2\cos^2\dfrac{x}{2}}\mathrm dx \\ &= \int_0^\pi \frac{1-\cos 2022x}{1-\cos x}\mathrm dx \\ &= 2022\pi \end{aligned} \]
最后一步用了 Fejer 积分：
\[\int_0^{\pi/2}\frac{1-\cos nx}{1-\cos x}\mathrm dx=\frac{n\pi}{2}\]
证明实际上不难：
\[ \begin{aligned} \frac{1-\cos nx}{1-\cos x} &= \frac{(1-\cos x)+(\cos x-\cos 2x)+\cdots (\cos(n-1)x-\cos nx)}{1-\cos x} \\ &= \frac{2\sin \dfrac{x}{2}\sum_{k=1}^n \sin(k-\dfrac{1}{2})x}{2\sin^2 \dfrac{x}{2}} \\ &=\sum_{k=1}^n \sin(k-\frac{1}{2})x \end{aligned} \]
因为
\[ \begin{aligned} \sin(n+\frac{1}{2})x&=\sin\frac{x}{2}+(\sin \frac{3}{2}x-\sin x)+\cdots+(\sin(n+\frac{1}{2})x-\sin(n-\frac{1}{2})x) \\ &=\sin\frac{x}{2}(1+\sum_{k=1}^n\cos kx) \end{aligned} \]
带入上面的式子，得到
\[\frac{1-\cos nx}{1-\cos x}=n+\sum_{k=1}^n\sum_{j=1}^k\cos jx\]
两边在 \((0,\pi)\) 上积分，\(\cos kx\) 积分值是 \(0\)，因此
\[\int_0^\pi \frac{1-\cos nx}{1-\cos x}\mathrm dx=n\pi\]
2.2
\[\int_{-2}^2 ((((x^2-2)^2-2)^2-2)^2-2)\mathrm dx\]
找规律，
\[\int_{-2}^2 (x^2-2)\mathrm dx=-\frac{8}{3}\]
\[\int_{-2}^2 ((x^2-2)^2-2)\mathrm dx=-\frac{8}{15}\]
因此原积分 \(-\dfrac{8}{255}\)
2.3
不会。
MIT Integration Bee 2023 - Quarterfinal 部分题目解答
2.1
\[\int_{\sqrt e}^\infty x^{-\ln x}\mathrm dx\]
设 \(t=\ln x\)，积分转化为
\[\int_{1/2}^\infty e^{-t^2+t}\mathrm dt=e^{1/4}\int_{1/2}^\infty e^{(t-1/2)^2}\mathrm dt=e^{1/4}\int_0^\infty e^{-u^2}\mathrm du\]
最后一个积分是经典的结论，这里也证一下。
设 \(I=\int_0^\infty e^{-x^2}\mathrm dx\)
则
\[I^2=\int_0^\infty\int_0^\infty e^{-x^2-y^2}\mathrm dx\mathrm dy\]
做极坐标换元，
\[\mathrm dx\mathrm dy=\frac{\partial(x,y)}{\partial(r,\theta)}\mathrm dr\mathrm d\theta\]
得到
\[I^2=\int_0^{\pi/2}\mathrm d\theta\int_0^\infty e^{-r^2}r\mathrm dr=\frac{\pi}{4}\]
故 \(I=\dfrac{\pi^{1/2}}{2}\)，原积分为 \(\dfrac{e^{1/4}\pi^{1/2}}{2}\)。
2.2
\[\int \frac{1-2x}{(1+x)^2x^{2/3}}\mathrm dx\]
做代换 \(t= x^{1/3}\)，得到
\[I=3\int \frac{1-2t^3}{(1+t^3)^2}\mathrm dt=3\int\frac{1}{1+t^3}-\frac{3t^3}{(1+t^3)^2}\mathrm dt\]
注意到
\[\frac{1}{1+t^3}-\frac{3t^3}{(1+t^3)^2}=\frac{1}{1+t^3}\cdot \frac{\mathrm dt}{\mathrm dt}+t\frac{\mathrm d(\frac{1}{1+t^3})}{\mathrm dt}=\frac{\mathrm d\frac{t}{1+t^3}}{\mathrm dt}\]
故原积分 \(I=\dfrac{3x^{1/3}}{1+x}\)
2.3
\[\lim_{n\to\infty}(\frac{1}{n}\int_0^n \cos^2(\frac{\pi x^2}{\sqrt 2})\mathrm dx)\]
\[I_n=\frac{1}{2}\int_0^n 1+\cos(\sqrt 2\pi x^2)\mathrm dx\]
做代换 \(t=x^2\)
\[I_n=\frac{n}{2}+\frac{1}{2}\int_0^{\sqrt n}\frac{\cos(\sqrt 2\pi t)}{\sqrt t}\mathrm dt=\frac{n}{2}+O(1)\]
故
\[\lim_{n\to\infty} \frac{1}{n}I_n=\frac{1}{2}\]
上上式最后一步利用了 A-D 判别法，反常积分
\[\int_0^\infty \frac{\cos(\sqrt 2\pi t)}{\sqrt t}\mathrm dt\]
收敛。
3.2
\[\int_0^\infty \operatorname{sech}^2(x+\tan x)\mathrm dx\]
对于形如 \(x-a-\sum_{n=1}^N \dfrac{|a_n|}{x-b_n}\) 的 \(u\) 和 \(f(x)\)，有
\[\text{P.V.}\int_{-\infty}^{+\infty}f(u)\mathrm dx=\text{P.V.}\int_{-\infty}^{+\infty}f(x)\mathrm dx\]
而因为
\[\pi\cot x=\frac{1}{x}+\sum_{i=1}^\infty \Big(\frac{1}{x+i\pi}+\frac{1}{x-i\pi}\Big)\]
做代换 \(t=\dfrac{\pi}{2}-x\) 就可以得到 \(\tan t\) 的表达式，因此 \(x+\tan x\) 是上面 \(u\) 的表达形式，所以利用定理，
\[I=\frac{1}{2}\int_{-\infty}^{+\infty}\operatorname{sech}^2x\mathrm dx=\tanh x\Big |_{-\infty}^{+\infty}=1\]