devout

想不到吧，你被四个男同包围了。——某同学

此话一出便引发了小范围的轰动。四个男同加上一位男同学都笑了。

说话的这位同学想必是把自己归结为了男同，这自然不是出于自我剖析，而是因为他大概不是男同。

他说的四个人中，除去他的剩下三个里面自然是有男同的，但有几个，我不好说。

首先，大于等于一个是好断言的，因为有一位确确实实的是男同了，甚至还给男同学写了一首小情歌，在新年联欢的时候当众演唱。

其次，男同学后面那位“男同”，我是不熟的，他是不是男同我不清楚，但是他在刚上高一的时候给我写了一封情书，姑且算是男同吧。

最后，虽然我笑的最开心，但是某同学算上的四个男同里面显然有我一个。

我不觉得我是男同，最多也只能算半个，毕竟我喜欢好看的小姐姐。

也许这里面只有 2.5 个男同？

想必不能这么说，因为还没有考虑那位男同学呢。

为什么这位男同学能够吸引 2.5 个男同呢？

其中一个原因大概是他的外貌吧。且看：

一双丹凤三角眼,两弯柳叶吊稍眉;身量苗条,体格风骚;粉面含春威不露,丹唇未启笑先闻。

再有就是不可否认的，他至少曾经是半个男同。也许时间已经到了男同的半衰期，姑且认定 5 个人里有 2.75 个男同吧。

再回头一看，只有某同学坦坦荡荡清清白白。

之前不知道在何处听到了一种说法，说男生在成长过程中同性恋是正常阶段。

于是拉小手拉了四年。

于是不懂，发现女孩子看百合番也能津津乐道，感觉女孩子真的是太好了。

后来思考男同的根本原因。

贴贴是欲望的释放。

很难想象这句话出自一个初三生之口。

说起来当年某同学还怒骂这句话来着，现在已经自诩为男同了。

对于这句话，我是部分认同的，只是似乎仅仅为此而背上男同的骂名有些得不偿失了。——现在物质和精神生活那么发达。

又想起每次被找上贴贴的时候，男同学会说。

你好饥渴啊。

他投怀送抱的时候，自然也会收到相同的答复。

这么一看上面那句话似乎更加的成立了。

口渴了自然要喝水，空虚了自然想要爱。

当年第一次看《灿烂千阳》，被里面的“hs”桥段震碎了三观。

后来读了日本文学，发现卡勒德胡赛尼写出来的东西也就是小菜一碟。

小时候家长提到某些书的时候总会说“你这个年纪还看不懂”

印象中其中有一本被给予这个评价的书是《活着》。

大概小孩子确实是看不懂《活着》的，但是恐怕比起“看不懂”可能问题更大的是给予孩子幼小心灵的震撼吧。

但是同样我想《故乡》对于初中生来说也一定是看不懂的，但是他确确实实存在于初中课本中。

但不对，《故乡》大概怎么说也能看个大概其，《雪国》《山音》这些作品大概大部分人只能不明觉厉，空留遐想。

记得此前 \(y\) 君告诉我，他在初中（还是小学？）的时候就读了《人间失格》，如果我要做家长，恐怕这本书要算作禁书中的禁书。

但是读一本书能够彻彻底底改变一个人吗？轻微的消沉自然会有，大影响恐怕不然。奋发的人读了《且听风吟》一句无病呻吟便一笑带过了，颓丧的人读了《睡美人》也不会更加想死。

难道没有什么适合看的了吗？

《伊豆的舞女》自然是好的，没有所谓hs情节，也没有弥漫着颓丧的气息，用时髦的话说便是“青春伤痛”。

这样的作品我这样空虚的人是爱看的。

就像《夏至未至》，当年还是和曹哥哥一起读的，被调侃为“日本原装进口”，现在想起依旧刻骨铭心的腹痛感。

就像《秒速五厘米》，就像《四月是你的谎言》，就像《可塑性记忆》，故事在最辉煌的时刻凋谢。

瞻顾遗迹，如在昨日，令人长号不自禁。

贪婪的人有无尽的欲望，想要甜甜的恋爱，想要电视剧中梦幻的生活，想溺死在幻想之中。

贪婪归于空虚。

这欲望，恐怕就是那些男同们内心贪婪的外在表现。

Exercise 4

(a): 注意到 \(f^{(n)}(x)\) 可写作 \(P_n(\dfrac{1}{x-a},\dfrac{1}{x-b})e^{-\dfrac{1}{x-a}-\dfrac{1}{x-b}}\)，其中 \(P_n(s,t)\) 是关于 \(s,t\) 的多项式。

我们只需要证明 \(f^{(n)}(x)\) 在 \(x=a\) 和 \(x=b\) 存在即可。

以 \(x=a\) 为例，注意到 \(x<a,f(x)\equiv 0\)，因此 \(f^{(n)}(a^-)=0\)，同时将 \(a^+\) 带入上面那个式子，得到 \(f^{(n)}(a^+)=0\)，故 \(f^{(n)}(a)=0\).

(b): \(F(x)=\dfrac{\int_{-\infty}^xf(t)\mathrm dt}{\int_{\mathbb R}f(t)\mathrm dt}\)

(c):

\[g(x)=\begin{cases} F(\dfrac{(x-a)(b-a)}{\delta}+a) & \text{ if } x\leq \dfrac{a+b}{2} \\ F(\dfrac{(b-x)(b-a)}{\delta}+a) & \text{ if } x>\dfrac{a+b}{2} \end{cases}\]

Van der Corput Difference Theomrem: 对于数列 \(\{f(n)\}_n\)，若 \(\forall h\in \mathbb Z\) ,\(\{f(n+h)-f(n)\}_n\) 在 \([0,1]\) 上等分布，则 \(\{f(n)\}_n\) 在 \([0,1]\) 上等分布。

我们首先证明一个引理：

Lemma(Van der Corput's Fundamental Inequality): 设 \(\{u_n\}_{n=1}^N\in\mathbb C,H\in\mathbb Z,1\leq H\leq N\)，则有

\[H^2\Bigg|\sum_{n=1}^N u_n\Bigg|^2\leq \color{red}{H(N+H-1)\sum_{n=1}^N |u_n|^2}+\color{green}2(N+H-1)\sum_{h=1}^{H-1}(H-h)\Re\sum_{n=1}^{N-h}u_n\overline{u_{n+h}} \tag{1}\]

证明考虑把 \(u_n\) 拓展定义到 \(\{u_n\}_n\)，其中 \(u_k=0,k>N\)，那么有

\[H\Bigg|\sum_{n=1}^N u_n\Bigg|=\sum_{p=1}^{N+H-1}\sum_{h=0}^{H-1}u_{p-h}=\sum_{p=1}^{N+H-1}\Bigg(1\cdot \sum_{h=0}^{H-1}u_{p-h}\Bigg)\]

两边用 Cauchy-Schwartz 不等式

\[ \begin{aligned} H^2\Bigg|\sum_{n=1}^N u_n\Bigg|^2 &\leq (N+H-1)\sum_{p=1}^{N+H-1}\Bigg(\sum_{h=0}^{H-1}u_{p-h}\Bigg)^2 \\ &=(N+H-1)\sum_{p=1}^{N+H-1}\Bigg(\sum_{h_1=0}^{H-1}u_{p-h_1}\Bigg)\Bigg(\sum_{h_2=0}^{H-1}\overline{u_{p-h_2}}\Bigg) \end{aligned} \]

对于 \(h_1=h_2\) 的单独提出来，就得到了 \((1)\) 中红色的部分

对于 \(h_1\neq h_2\) 的部分，考虑 \(|h_1-h_2|=h\) 的 \(u_n\overline{u_{n+h}}\) 一共出现的次数，以及注意到结果一定是实数，所以虚部抵消掉了，就得到了绿色的部分。

证明了引理之后，我们取 \(u_n=e^{2\pi if(n)}\)，得到

\[|S_N|^2\leq \frac{H(N+H-1)N}{H^2}+\frac{\sum_{h=1}^{H-1}2(N+H-1)H|\sum_{n=1}^{N-h}e^{2\pi i(f(n+h)-f(n))}|}{H^2}\]

接下来利用放缩 \(N+H-1\leq 2N\) 得到

\[ \begin{aligned} |S_N|^2&\leq \frac{4N}{H}\sum_{h=1}^{H-1}\Bigg|\sum_{n=1}^{N-h}e^{2\pi i(f(n+h)-f(n))}\Bigg| \\ &\leq \frac{4N^2}{H}\sum_{h=1}^{H-1}\Bigg|\frac{1}{N-h}\sum_{n=1}^{N-h}e^{2\pi i(f(n+h)-f(n))}\Bigg| \end{aligned} \]

由定理假设，以及 \(H\) 为有限数，得后面大 sigma 里面是 \(o(1)\)，故 \(|S_N|^2=o(N^2)\)，即证明 \(\{f(n)\}\) 是等分布 \([0,1]\) 上的序列。

一些应用：

对于 \(\sigma>0,a\neq\in\mathbb Z\),\(\{an^\sigma\}\) 在 \([0,1]\) 为等部分序列。

在 Exercise 8 中我们已经证明了 \(\sigma\in(0,1)\) 的时候的结果，对于 \(\sigma\in (k,k+1)\) 只需要每次差分然后数学归纳即可。

Exercise 4

\((\text{Wirtinger} \Rightarrow \text{isoperimetric})\)：

\[ \begin{aligned} 2(\pi-\mathcal A)&=\int_{-\pi}^\pi [x^\prime(s)^2+y^\prime(s)^2]\mathrm ds-\int_{-\pi}^\pi [x(s)y^\prime(s)-y(x)x^\prime(s)]\mathrm ds \\ &= \int_{-\pi}^\pi [x^\prime(s)+y(s)]^2\mathrm ds+\int_{-\pi}^\pi[y^\prime(s)^2-y^2(s)]\mathrm ds \\ &\geq 0 \end{aligned} \]

最后一步利用 Wirtinger 不等式。

\((\text{isoperimetric} \Rightarrow \text{wirtinger})\):

因为 \(f\) 连续，所以 \(f\) 有原函数，设 \(g\) 满足 \(g^\prime=-f\)

考虑 \(\gamma:[-\pi,\pi]\to \mathbb R^2:t\to(g(t),f(t))\)

$$

Exercise 5

注意到

\[(\frac{1-\sqrt 5}{2})^n+(\frac{\sqrt 5+1}{2})^n\]

是 \(a_n=a_{n-1}+a_{n-2},a_1=1,a_2=2\) 的通项公式，而 \((\frac{1-\sqrt 5}{2})^n\to 0\)，故随 \(n\to\infty\)，后面一项无限接近一个整数。

Exercise 8

\[\Big|\sum_{n=1}^N e^{2\pi ibn^\sigma}\Big|\leq \Big |\sum_{n=1}^Ne^{2\pi ibn^\sigma}-\int_1^N e^{2\pi ibx^\sigma}\mathrm dx\Big|+\Big|\int_1^N e^{2\pi i bx^\sigma}\mathrm dx \Big|\]

而后一项可以利用分部积分提出一个 \(e^{2\pi i b x^\sigma}\)，证明他是 \(O(N^{1-\sigma})\)，前一项可以 \((n,n+1)\) 分开考虑放缩，得到 \(O(N^\sigma)\)，即得证。

Exercise 9

这次是证明

\[\lim_{N\to\infty}\frac{1}{N}\sum_{n=1}^N e^{2\pi ib\ln n}>0\]

我们还是拆分成 \(\sum-\int_1^N\) 和 \(\int_1^N\) 两部分，注意到 \(\sum-\int_1^N=O(\log n)\)，因此不会对极限造成影响，而 \(\int_1^N\) 的结果是 \((N^{2\pi ib+1}-1)/(2\pi ib+1)\)，由 \(|N^{2\pi ib}|=1\) 知最后的极限是 \(1/(2\pi i b+1)\)

Exercise 11

首先求出 \(u-f\) 的傅里叶系数

\[\widehat{u-f}(n)=\widehat{(f*H_t)}(n)-\widehat f(n)=\widehat f(n)[e^{-4\pi^2n^2t^2}-1]\]

由 Parseval

\[\int_0^1 |u(x,t)-f(x)|^2\mathrm dx=\sum |\hat f(n)|^2+|\widehat{H_t}(n)-1|^2\mathrm dx\]

对于 \(\forall \epsilon>0\)

注意到因为 \(||f||<\infty\)，所以存在 \(N\) 使得

\[\sum_{|n|>N} |\hat f(n)|<\sqrt \epsilon\]

因此对于 \(|n|>N\) 的部分，由 \(|\widehat{H_t}(n)-1|\leq 1\) 可知后面的和 \(<\epsilon\)

对于 \(|n|\leq N\) 的部分，我们只需要 \(|\widehat{H_t}(n)-1|<\sqrt \epsilon(\forall t<\delta)\) 即可，可取 \(\delta=\dfrac{\ln(1-\sqrt \epsilon)}{4\pi^2N^2}\)

这样 \(\sum=\sum_{|n|\leq N}+\sum_{|n|>N}\leq ||f||\epsilon+\epsilon=O(\epsilon) (t\to 0)\)，即证。

Exercise 13(b)

感觉主要是想到第一步，后面都比较机械了。

先用 Jordan 不等式 \(|x|\leq \dfrac{1}{2}|\sin \pi x|,x\in [-\dfrac{1}{2},\dfrac{1}{2}]\)，转化成 \(\int |\sin\pi xH_t(x)|^2\mathrm dx\)，然后 Parseval，转化成傅里叶系数平方求和，用 \(\dfrac{1}{2i}(e^{i\pi x}-e^{-i\pi x})\) 代替 \(\sin x\)，最后可以转化成 \(\pi^4t^2\sum |(2n+1)^2e^{-8\pi^2 x^2 t}|\) 的形式，再转换成积分的形式，求阶即可。

Problem 1

1. 用 Exercise 15 Chap.3 的结论，有

\[2|a_n|=\frac{1}{2\pi}\int_{-\pi}^\pi (\gamma(t)-\gamma(t+\pi/n))e^{-int}\mathrm dt\]

2. 设 \(t\) 为 \(\gamma(\tau)\) 的切线与 \(y\) 轴的夹角，则 \(\gamma^\prime(t)\) 可写作 \(ie^{it}r(t)\)，其中 \(r(t)\) 控制在 \(\tau(t)\) 处的切线长度，则 \(r(t)\) 是周期为 \(2\pi\) 的实值函数且 \(r(t)=-r(t+\pi)\)

由分部积分

\[\gamma(t)=r(t)e^{it}-\int r^\prime(t)e^{it}\mathrm dt\]

求傅里叶系数得

\[\hat \gamma(1)=\frac{1}{2\pi}\int_{-\pi}^\pi r(t)\mathrm dt=\frac{1}{2\pi}\int_{-\pi}^\pi|\gamma^\prime(t)|\mathrm dt=\frac{\ell}{2\pi}\]

再由 \(2\hat \gamma(1)\leq d\) 即证。

Problem 3

运用 Problem 2 的结论，数学归纳法，每次差分，直到 \(\sigma\in (0,1)\)。

Problem 6

可将 \(f(n)\) 拆成若干段单调有界的函数，因此有 \(\hat f(n)=O(1/n)\)，然后用 Problem 5 的结论。

Bernoulli Number

伯努利数由 EGF 定义

\[\mathcal B(z)=\frac{z}{e^z-1}=\sum_{n=0}^\infty \frac{B_n}{n!}z^n \tag{1}\]

利用这个定义暴力展开生成函数，我们可以算出伯努利数的前几项。

\[ \begin{matrix} n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ B_n & 1 & -1/2 & 1/6 & 0 & -1/30 & 0 & 1/42 & 0 & -1/30 & 0 & 5/66 & 0 & -691/2730 \end{matrix} \]

注意到这些数都比较丑，并且 \(\geq 3\) 的奇数都是 \(0\)，这一点可以注意到 \(\dfrac{z}{e^z-1}+\dfrac{z}{2}\) 是一个偶函数。

事实上，伯努利数并不存在封闭形式，这一点可以从 \(-691/2730\) 这样一个诡异的形式中看出来。

另一种定义伯努利数的方法是通过递推定义，这一种定义和生成函数定义是等价的，可以用生成函数导出：

\[\frac{z}{e^z-1}-1=-\frac{z}{e^z-1}(\frac{e^z-1}{z}-1)\]

两边同时取 \(z^n\) 项，我们得到

\[B_n=-\frac{1}{n+1}\sum_{k=0}^{n-1}\binom{n+1}{k}B_k \tag{2}\]

Zeta Function at Positive Even Integers

伯努利数的一个重要应用就是他可以表示一类函数的展开系数，如 \(\zeta\) 函数，其在 \(2n(n\in\mathbb Z)\) 处的定义为

\[\zeta(2n)=\sum_{m=1}^\infty \frac{1}{m^{2n}} \tag{3}\]

为了导出 \(\zeta\) 函数的级数表示，我们首先研究一下 \(z\cot z\) 的展开。

\[ \begin{aligned} z\cot z &=(iz)\frac{e^{iz}+e^{-iz}}{e^{iz}-e^{-iz}} \\ &=\frac{1}{2}(2iz)\Big(\frac{1}{1-e^{-2iz}}+\frac{1}{e^{2iz}-1}\Big) \\ &=\frac{1}{2}(\mathcal B(2iz)+\mathcal B(-2iz)) \\ &=1+\sum_{n=1}^\infty (-1)^n\frac{2^{2n}B_{2n}}{(2n)!}z^{2n} \end{aligned}\tag{4} \]

另一方面，对于 \(\cot z\) 我们有经典的公式

\[\cot z=\frac{1}{z}+2\sum_{n=1}^\infty \frac{z}{z^2-n^2\pi^2}\]

则有

\[ \begin{aligned} z\cot z &=1+2\sum_{n=1}^\infty \frac{(\dfrac{z}{n\pi})^2}{(\dfrac{z}{n\pi})^2-1} \\ &=1-2\sum_{n=1}^\infty \sum_{j\in2\mathbb Z^+}\frac{z^j}{n^j\pi^j} \\ &=1-2\sum_{n=1}^\infty\frac{\zeta(2n)}{\pi^{2n}}z^{2n} \end{aligned}\tag{5} \]

对比 \((4),(5)\) 的系数，我们可以得到

\[\zeta(2n)=\frac{(-1)^{n+1}}{2}\frac{(2\pi)^{2n}}{(2n)!}B_{2n} \tag{6}\]

事实上，伯努利数还出现在更多的函数的表达式中，如将 \(\tan z\) 写作 \(\cot z-2\cot 2z\)，就可以得到 \(\tan z\) 的表达式。

Bernoulli Polynomial

伯努利多项式 \(B_n(x)\) 通过生成函数

\[\mathfrak B(x,z)=\frac{ze^{xz}}{e^z-1}=\sum_{n=0}^\infty \frac{B_n(x)}{n!}z^n \tag{7}\]

定义。

把 \(\mathfrak B(x,z)\) 写成 \(\mathcal B(z)\) 和 \(e^{xz}\) 的卷积的形式，比较系数就得到

\[B_n(x)=\sum_{k=0}^n \binom{n}{k}B_kx^{n-k} \tag{8}\]

下面两个结论和伯努利数的实际意义有着重要的关联，首先 \(B_n(x)\) 在离散微积分意义下和 \(x^n\) 很像，具体的，

\[\Delta B_n(x)=B_n(x+1)-B_n(x)=nx^{n-1} \tag{9}\]

证明只需用 \(\mathfrak B(x,z+1)-\mathfrak B(x,z)\) 即可。

另一个实际上是伯努利数被发现的原因，即 \(x^m\) 的离散积分的系数与 \(B_n\) 有着紧密的联系。

设 \(S_m(n)=\sum_{k=1}^{n-1}k^m=\sum_1^n x^m\delta x\)，则有

\[(m+1)S_m(n)=B_{m+1}(n)-B_{m+1} \tag{10}\]

证明只需在 \((9)\) 中取 \(n=m+1\)，然后对 \(x\) 从 \(1\) 到 \(m-1\) 求和即可。

Bernoulli Denominator

最后我们来考虑一下伯努利数的神秘的分母是什么。

对着表仔细观察可以注意到，他是所有满足 \((p-1)|(2n)\) 的素数 \(p\) 的乘积。

我们用数学归纳法证明这个猜想。

注意到这个猜想实际上等价于

\[I_{2n}=B_{2n}+\sum_{p为素数} \frac{[(p-1)|2n]}{p} \tag{11}\]

是一个整数。

观察到，对于素数 \(p\) 和 \(m>0\)，\(S_m(p)+[(p-1)|m]=\mathbb Zp\)

证明考虑 \(m\) 是 \((p-1)\) 的倍数，如果是，则 \(S_m(p)\equiv p-1 \bmod p\)，否则 \(S_m(p)\) 每一项模 \(p\) 互不相同，加起来是 \(p\) 的倍数。

有了这个结论之后，对于 \((p-1)|2n\) 的 \(p\)，利用 \((10)\) 取 \(m=2n\)，将其中的 \(B_{m+1}(x)\) 用 \((8)\) 展开。

\[B_{2n}+\frac{[(p-1)|2n]}{p}+\frac{1}{2n+1}\sum_{k=0}^{2n-2}\binom{2n+1}{k}B_kp^{2n+1-k}=S_{2n}(p)+\mathbb Z\in \mathbb Z\]

因此我们只需要证明

\[\frac{1}{2n+1}\sum_{k=0}^{2n-2}\binom{2n+1}{k}B_kp^{2n+1-k}=\sum_{k=0}^{2n-2}\binom{2n}{k}B_kp^2\frac{p^{2n-1-k}}{2n+1-k}\]

是整数即可，因为 \(p\) 是素数，这等价于他的分母不能被 \(p\) 整除。

由归纳假设，\(B_k\) 的分母中不含 \(p^2\)，因此 \(B_kp^2\) 的分母中不含 \(p\)，而在假设范围内有 \(p^{2n-1-k}\geq 2n+1-k\)，因此后面一部分的分母里同样没有 \(p\)，假设成立。

这也就完成了我们的证明。

因为 \(2n\geq 2\) 的时候，\(2-1,3-1\) 一定整除 \(2n\)，所以 \(\forall n\geq 1\),\(B_{2n}\) 的分母一定是 \(6\) 的倍数。

我们在这里证明一个广为人知的结论，即周长一定的闭合曲线为圆时围成的面积最大。

具体的，对于平面上的一条闭合曲线 \(\gamma:[a,b]\to \mathbb R^2\) ，\(\gamma(a)=\gamma(b)\)，其长度定义为

\[\ell=\int_a^b \sqrt{(x^\prime)^2(t)+(y^\prime)^2(t)}\mathrm dt\]

其面积定义为

\[\mathcal A=\frac{1}{2}\Bigg|\int_a^b x(t)y^\prime(t)-x^\prime(t)y(t)\mathrm dt \Bigg|\]

则有

\[\mathcal A\leq \frac{\ell^2}{4\pi}\]

当且仅当 \(\gamma\) 为一个圆时等式成立。

首先，我们需要把曲线转化成一个标准的形式。

对 \(t\) 做变量代换，我们可以把 \(\gamma\) 定义到 \([0,2\pi]\) 上。

其次，调整 \(x(t),y(t)\) 使得任意时刻 \((x^\prime)^2(t)+(y^\prime)^2(t)=1\)，这样我们将曲线的 \(\ell\) 调整为 \(2\pi\)，接下来我们只需要证明 \(\mathcal A\leq \pi\) 即可。

注意到 \(\gamma(0)=\gamma(2\pi)\)，我们可以将 \(x(t)\) 和 \(y(t)\) 分别写成傅里叶级数的表达

\[x(t)\sim \sum a_ne^{int} \text{ and } y(t)\sim \sum b_ne^{int}\]

则

\[x^\prime(t) \sim \sum a_nine^{int} \text{ and } y^\prime(t)\sim \sum b_nine^{int}\]

则

\[\mathcal A=\Big|\pi \sum n(a_n\overline{b_n}-b_n\overline{a_n})\Big|\]

利用

\[n\leq n^2 \tag{1}\]

\[|a_n\overline{b_n}-b_n\overline{a_n}|\leq 2|a_n||b_n| \tag{2}\]

\[2|a_n||b_n|\leq |a_n|^2+|b_n|^2 \tag{3}\]

得到

\[\mathcal A\leq \pi \sum n^2(|a_n|^2+|b_n|^2)=\pi ||x(t)||\cdot ||y(t)||=\pi \tag{4}\]

接下来考虑取等条件，\((1)\) 说明 \(a_k(|k|\geq 2)=0\)，因为 \(x(t),y(t)\in\mathbb R\)，说明 \(a_1=\overline{a_{-1}},b_1=\overline{b_{-1}}\)，\((4)\) 说明 \(|a_1|^2+|a_2|^2=1/2\)，\((3)\) 说明 \(|a_1|=|b_1|=\frac{1}{2}\)

因此可设

\[a_1=\frac{1}{2}e^{in\alpha} \text{ and } b_1=\frac{1}{2}e^{in\beta}\]

带入 \((3)\)，得到 \(|\sin(\alpha-\beta)|=1\)，也就是说 \(a_1\) 和 \(b_1\) 是垂直的。

旋转坐标系到 \(\alpha\)，不妨设 \(\beta=\alpha+\dfrac{\pi}{2}\)，在新的坐标系下，有

\[x(t)=a_0+2a_1\cos t\text{ and }y(t)=b_0+2b_1\sin t\]

这正是圆的形式。

莫队加 bitset 解决前三个操作

第四个操作在 \(x>\sqrt n\) 的时候同样解决了。

\(x\leq \sqrt n\) 的时候，对于 \(x\) 相同的放在一起处理，设 \(f[i]\) 表示最大的 \(j\) 满足 \([i,j]\) 中有一对商是 \(x\) 的，不难转移。

复杂度 \(O(n\sqrt n)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

# include <bits/stdc++.h>

using namespace std;

# define Rep(i,a,b) for(int i=a;i<=b;i++)
# define _Rep(i,a,b) for(int i=a;i>=b;i--)
# define RepG(i,u) for(int i=head[u];~i;i=e[i].next)

typedef long long ll;
typedef double db;

# define chkmax(a,b) a=max(a,b)
# define chkmin(a,b) a=min(a,b)
# define PII pair<int,int>
# define mkp make_pair

const int N=1e5+5;

template<typename T> void read(T &x){
    x=0;int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0';
    x*=f;
}

int n,m;
int a[N];
int pos[N],sq;
int cnt[N];
int lst[N],f[N];
int out[N];
int lim=300;
int qcnt;

bitset<N> S,SI;

struct misaka{
    int opt,l,r,x,id;
}Q[N];

vector<misaka> T[305];

bool cmp(misaka x,misaka y){
    if(pos[x.l]!=pos[y.l])return pos[x.l]<pos[y.l];
    else if(pos[x.l]&1)return x.r<y.r;
    else return x.r>y.r;
}

void ins(int x){
    if(!cnt[x])S[x]=1,SI[100000-x]=1;
    cnt[x]++;
}

void del(int x){
    cnt[x]--;
    if(!cnt[x])S[x]=0,SI[100000-x]=0;
}

int main()
{
    # ifndef ONLINE_JUDGE
    freopen("testdata.in","r",stdin);
    //freopen("test1.out","w",stdout);
    # endif
    read(n),read(m);
    Rep(i,1,n)read(a[i]);
    sq=sqrt(n)+1;
    Rep(i,1,n)pos[i]=(i-1)/sq+1;
    Rep(i,1,m){
        int opt,x,l,r;
        read(opt),read(l),read(r),read(x);
        if(opt==4&&x<=lim)T[x].push_back((misaka){4,l,r,x,i});
        else Q[++qcnt]=(misaka){opt,l,r,x,i};
    }
    sort(Q+1,Q+qcnt+1,cmp);
    for(int i=1,l=1,r=0;i<=qcnt;i++){
        while(l>Q[i].l)ins(a[--l]);
        while(r<Q[i].r)ins(a[++r]);
        while(l<Q[i].l)del(a[l++]);
        while(r>Q[i].r)del(a[r--]);
        if(Q[i].opt==1)out[Q[i].id]=((S<<Q[i].x)&S).any();
        else if(Q[i].opt==2)out[Q[i].id]=((S<<(100000-Q[i].x))&SI).any();
        else if(Q[i].opt==3){
            for(int j=1;j*j<=Q[i].x;j++)
                if(Q[i].x%j==0&&S[j]&&S[Q[i].x/j])
                    out[Q[i].id]=true;
        }
        else{
            for(int j=1;j*Q[i].x<=100000;j++)
                if(S[j]&&S[j*Q[i].x])
                    out[Q[i].id]=true;
        }
    }
    Rep(x,1,lim){
        if(T[x].empty())continue;
        Rep(i,1,n){
            int y=a[i];
            lst[y]=i;
            f[i]=f[i-1];
            if(x*y<=100000)chkmax(f[i],lst[x*y]);
            if(y%x==0)chkmax(f[i],lst[y/x]);
        }
        for(auto i:T[x])
            out[i.id]=i.l<=f[i.r];
        memset(f,0,sizeof(f));
        memset(lst,0,sizeof(lst));
    }
    Rep(i,1,m)puts(out[i]?"yuno":"yumi");
    return 0;
}

首先注意到每一位是独立的，只需要枚举 \(0\) 进去还是 \(1\) 进去对应的就可以算出来。

这个不难用树剖线段树/LCT 维护，得到 3log 的做法。

然后可以用一个 unsigned long long 把每一位压到一起，然后就 2log(1log) 了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182

#include <bits/stdc++.h>

using namespace std;

# define Rep(i,a,b) for(int i=a;i<=b;i++)
# define _Rep(i,a,b) for(int i=a;i>=b;i--)
# define RepG(i,u) for(int i=head[u];~i;i=e[i].next)

const int N=1e5+5;
const unsigned long long inf=0-1;

# define ll long long
# define db double
# define ull unsigned long long
# define uint unsigned int
# define chkmax(a,b) a=max(a,b)
# define chkmin(a,b) a=min(a,b)
# define mkp make_pair
# define PII pair<int,int>
# define PLL pair<ll,ll>
# define PIL pair<int,ll>
# define PLI pair<ll,int>

template<typename T> void read(T &x){
    x=0;int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0';
    x*=f;
}

int n,m,bit;
int head[N],cnt;
int o[N];
ull a[N];
int dfn[N],siz[N],_a[N],top[N],dep[N],faz[N],son[N],dfsxu;

struct Edge{
    int to,next;
}e[N<<1];

void add(int x,int y){
    e[++cnt]=(Edge){y,head[x]},head[x]=cnt;
}

struct node{
    ull l0,l1,r0,r1;
    node(){l0=r0=0,l1=r1=inf;}
}seg[N<<2];

void dfs1(int u,int fa){
    faz[u]=fa,dep[u]=dep[fa]+1;
    siz[u]=1;
    RepG(i,u){
        int v=e[i].to;
        if(v==fa)continue;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])son[u]=v;
    }
}

void dfs2(int u,int _top){
    dfn[u]=++dfsxu;
    _a[dfsxu]=u;
    top[u]=_top;
    if(!son[u])return;
    dfs2(son[u],_top);
    RepG(i,u){
        int v=e[i].to;
        if(v==faz[u]||v==son[u])continue;
        dfs2(v,v);
    }
}

# define lc (u<<1)
# define rc (u<<1|1)

ull calc(ull x,int p){
    if(o[p]==1)return x&a[p];
    if(o[p]==2)return x|a[p];
    if(o[p]==3)return x^a[p];
}

node merge(node x,node y){
    node res;
    res.l0=(x.l0&y.l1)|((~x.l0)&y.l0); 
    res.l1=(x.l1&y.l1)|((~x.l1)&y.l0);
    res.r0=(y.r0&x.r1)|((~y.r0)&x.r0);
    res.r1=(y.r1&x.r1)|((~y.r1)&x.r0);
    return res;
}

void build(int u,int l,int r){
    if(l==r){
        seg[u].l0=seg[u].r0=calc(0,_a[l]);
        seg[u].l1=seg[u].r1=calc(inf,_a[l]);
        return;
    }
    int mid=l+r>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    seg[u]=merge(seg[lc],seg[rc]);  
}

void update(int u,int l,int r,int x){
    if(l==r){
        seg[u].l0=seg[u].r0=calc(0,_a[l]);
        seg[u].l1=seg[u].r1=calc(inf,_a[l]);
        return;
    }
    int mid=l+r>>1;
    if(x<=mid)update(lc,l,mid,x);
    else update(rc,mid+1,r,x);
    seg[u]=merge(seg[lc],seg[rc]);
}

node query(int u,int l,int r,int ql,int qr){
    if(l>=ql&&r<=qr)return seg[u];
    int mid=l+r>>1;
    if(qr<=mid)return query(lc,l,mid,ql,qr);
    else if(ql>mid)return query(rc,mid+1,r,ql,qr);
    else return merge(query(lc,l,mid,ql,qr),query(rc,mid+1,r,ql,qr));
}

node RouteQuery(int x,int y){
    node l,r;
    while(top[x]!=top[y])
        if(dfn[top[x]]>dfn[top[y]]){
            l=merge(query(1,1,n,dfn[top[x]],dfn[x]),l);
            x=faz[top[x]];
        }
        else{
            r=merge(query(1,1,n,dfn[top[y]],dfn[y]),r);
            y=faz[top[y]];
        }
    if(dfn[x]<dfn[y])r=merge(query(1,1,n,dfn[x],dfn[y]),r);
    else l=merge(query(1,1,n,dfn[y],dfn[x]),l);
    swap(l.l0,l.r0),swap(l.l1,l.r1);
    return merge(l,r);
}

int main()
{
    # ifndef ONLINE_JUDGE
    freopen("testdata.in","r",stdin);
    //freopen("test1.out","w",stdout);
    # endif
    memset(head,-1,sizeof(head));
    read(n),read(m),read(bit);
    Rep(i,1,n)read(o[i]),read(a[i]);
    Rep(i,1,n-1){
        int x,y;
        read(x),read(y);
        add(x,y),add(y,x);
    }
    dfs1(1,0);
    dfs2(1,1);
    build(1,1,n);
    Rep(i,1,m){
        int opt,x,y;
        ull z;
        read(opt),read(x),read(y),read(z);
        if(opt==2){
            o[x]=y;
            a[x]=z;
            update(1,1,n,dfn[x]);
        }
        else{
            node res=RouteQuery(x,y);
            ull ans=0;
            _Rep(i,63,0){
                int v0=(res.l0>>i)&1ull;
                int v1=(res.l1>>i)&1ull;
                if(v0>=v1||((1ull<<i)>z))ans|=(v0?(1ull<<i):0);
                else ans|=(v1?(1ull<<i):0),z-=1ull<<i;
            }
            printf("%llu\n",ans);
        }
    }
    return 0;
}

Exercise 6

假设存在 \(f\) 的傅里叶系数是 \(\{a\}\)，则 \(|f|\leq M\)

\[A_r(f)(0)=\bigg|\frac{1}{2\pi}\int_{-\pi}^{\pi}P_r(0-t)f(t)\mathrm dt\bigg|\leq M\frac{1}{2\pi}\int_{-\pi}^\pi P_r(t)\mathrm dt=M\]

另一方面，

\[\bigg|\sum_{n={-\infty}}^\infty a_nr^{|n|}e^{in\theta}\bigg|=\sum_{n=1}^{\infty} \frac{r^n}{n}\to \infty(r\to 1)\]

出现矛盾。

Exercise 10

\[ \begin{aligned} E^\prime(t)&=\rho\int_0^{L}\frac{\partial u}{\partial t}\frac{\partial^2 u}{\partial t^2}\mathrm dx+\tau\int_0^L \frac{\partial u}{\partial x}\frac{\partial^2 u}{\partial x\partial t}\mathrm dx \\ &=\rho\int_0^{L}\frac{\partial u}{\partial t}\frac{\partial^2 u}{\partial t^2}\mathrm dx+\tau \frac{\partial u}{\partial t}\frac{\partial u}{\partial x}\Big|_0^L-\tau \int_0^L \frac{\partial u}{\partial t}\frac{\partial^2 u}{\partial x^2}\mathrm dx \\ &=0 \end{aligned} \]

Exercise 12

注意到 \(\dfrac{1}{\sin \dfrac{x}{2}}-\dfrac{2}{x}\) 在 \(0\) 处是可去间断点，补充定义后可令其 \(\in \mathcal R[0,\pi]\)，由 Riemann-Lebesgue Lemma

\[\int_0^{\pi}\Bigg(\frac{1}{\sin\dfrac{x}{2}}-\frac{2}{x}\bigg)\sin(N+\frac{1}{2})x\mathrm dx\to 0,N\to \infty\]

而

\[\int_0^\pi \frac{\sin(N+\dfrac{1}{2})x}{\sin \dfrac{x}{2}}\mathrm dx=\int_0^\pi D_N(x)\mathrm dx=\pi\]

得到

\[\int_0^\pi \frac{\sin(N+\dfrac{1}{2})x}{x}\mathrm dx\to \frac{\pi}{2},N\to\infty,N\in \mathbb Z\]

换元得到

\[\int_0^{(N+\frac{1}{2})\pi} \frac{\sin x}{x}\mathrm dx\to \frac{\pi}{2},N\to\infty,N\in \mathbb Z\]

两边取极限即得所求为 \(\dfrac{\pi}{2}\)

Exercise 14

\(\hat f^\prime(n)=\dfrac{1}{in}\hat f(n)\)

于是有

\[\sum_{n\neq 0} |\hat f(n)|\leq \sum_{n\neq 0}\dfrac{|\hat f^\prime(n)|}{|n|}\leq \sqrt{\sum_{n\neq 0}|\hat f^\prime(n)|^2}\cdot\sqrt{\sum_{n\neq 0}\frac{1}{n^2}}=C||f^\prime||< \infty\]

于是 \(\sum |\hat f(n)|\) 绝对收敛，即一致收敛。

Exercise 18

因为 \(\epsilon_n\to\infty\)，所以 \(\forall k\in \mathbb Z^+,\exist \epsilon_{n_k}<\dfrac{1}{2^k}\)，取 \(f=\sum \epsilon_{n_k}e^{in_kx}\) 即可。

这个练习归纳了之前关于傅里叶级数收敛速度的一些结论。

• \(f\in C^k\Rightarrow \hat f(n)=O(1/|n|^k)\)
• \(f\) is Lipschitz \(\Rightarrow \hat f(n)=O(1/|n|)\)
• \(f\) is monotonic \(\Rightarrow \hat f(n)=O(1/|n|)\)
• \(f\) satisfies Holder's condition with exponent \(0<\alpha<1 \Rightarrow \hat f(n)=O(1/|n|^{\alpha})\)
• \(f\) is Riemann Integrable \(\Rightarrow \hat f\in \ell^2,\hat f(n)=o(1)\)

Problem 1

\[\tilde D_N(x)=\frac{\cos\dfrac{x}{2}-\cos(N+\dfrac{1}{2})x}{\sin \dfrac{x}{2}}\]

用和差化积

\[|\tilde D_N(x)|=2\frac{|\sin(\dfrac{N}{2}+1)x\sin Nx|}{|\sin\dfrac{x}{2}|}\leq 2\pi\frac{|\sin Nx|}{|x|}\]

其中用了 \(|\sin(\dfrac{N}{2}+1)x| \leq 1\) 和 Jordan 不等式 \(|\sin \dfrac{x}{2}|\geq |\dfrac{x}{\pi}|\)

对 \(\dfrac{|\sin Nx|}{|x|}\) 在 \([0,\pi]\) 上积分，考虑对 \(\sin Nx\) 的符号分段讨论，\(x\) 放缩成区间左端点，就得到了类似调和级数的表达式，因此为 \(O(\log N)\)

假设 \(\sum_{n=1}^\infty\) 是某个 \(f\in\mathcal R\) 的傅里叶级数，则

\[(f*\tilde D_n)(0)=\frac{i}{\pi}\int_0^\pi f(t)\sum_{n=1}^\infty (e^{int}-e^{-int})\mathrm dt=2i\sum_{n=1}^\infty \frac{1}{n^\alpha}=\omega(\log N)\]

得到矛盾，因此不存在这样的 \(f\)。

首先有一个经典的结论，就是对于固定的右端点，or 和的不同的值最多只有 \(O(\log a)\) 个。

考虑分块，对于每个整块，维护前缀和后缀的所有不同的 or 和。

对于跨越块的区间，每次查询从左向右扫，记录前 \(k-1\) 个块的后缀不同 or 和，然后用这个后缀和第 \(k\) 个块的前缀做一个双指针计算答案，然后将前 \(k-1\) 个块的后缀 or 上第 \(k\) 个块，再将第 \(k\) 个块内的后缀加入更新去重即可。

对于块内的部分，我们用 \(f(len)\) 表示长度 \(\leq len\) 的区间中 or 和最大的是多少，每次询问二分即可。

对于修改，我们暴力重构一个块即可。

注意在块内 \(f(len)\) 的部分，对于每个右端点计算 \(O(\log a)\) 个左区间的时候，实际上就是对于每一位求 \(\leq i\) 的第一个 1，这部分如果额外排序的话就会损失一个 \(\log \log a\)。所以我们从左往右推的时候用队列维护一下这个顺序就可以了，因为除了 \(a_i\) 是 \(1\) 的那些为其他位变成 \(1\) 的顺序和 \(i-1\) 是一样的。

复杂度 \(O(n\sqrt n\log a)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

#include <bits/stdc++.h>

using namespace std;

# define Rep(i,a,b) for(int i=a;i<=b;i++)
# define _Rep(i,a,b) for(int i=a;i>=b;i--)
# define RepG(i,u) for(int i=head[u];~i;i=e[i].next)

const int N=50005;
const int M=135;

# define ll long long
# define db double
# define ull unsigned long long
# define uint unsigned int
# define chkmax(a,b) a=max(a,b)
# define chkmin(a,b) a=min(a,b)
# define mkp make_pair
# define PII pair<int,int>
# define PLL pair<ll,ll>
# define PIL pair<int,ll>
# define PLI pair<ll,int>

template<typename T> void read(T &x){
    x=0;int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0';
    x*=f;
}

int n,m;
int a[N];
int L[N],R[N],pos[N],sq=400,bl;
PII res[66];
int len;
int orsum[M];
int mx[M][405];
int lenp[M],lens[M];
PII pre[M][33],suf[M][33];
PII myq[23333],cach[66];

void rebuild(int x){
    memset(mx[x],0,sizeof(mx[x]));
    lenp[x]=lens[x]=0;
    int tmp=0;
    Rep(i,L[x],R[x]) if((tmp|a[i])!=pre[x][lenp[x]].first)tmp|=a[i],pre[x][++lenp[x]]=mkp(tmp,i);
    tmp=0;
    _Rep(i,R[x],L[x])if((tmp|a[i])!=suf[x][lens[x]].first)tmp|=a[i],suf[x][++lens[x]]=mkp(tmp,i);
    int head=1,tail=0;
    Rep(i,L[x],R[x]){
        int lst=tail;
        for(int j=a[i];j;j-=j&-j)myq[++tail]=mkp(__builtin_ctz(j),i);
        for(int j=head;j<=lst;j++)if(!(a[i]>>myq[j].first&1))myq[++tail]=myq[j];
        head=lst+1;
        tmp=0;
        Rep(j,head,tail){
            tmp|=a[myq[j].second];
            chkmax(mx[x][i-myq[j].second+1],tmp);
        }
    }
    Rep(i,2,R[x]-L[x]+1)chkmax(mx[x][i],mx[x][i-1]);
    orsum[x]=0;
    Rep(i,L[x],R[x])orsum[x]|=a[i];
}

void maintain(){
    Rep(i,2,len)if(res[i].first==res[i-1].first)res[i].second=res[i-1].second;
    len=unique(res+1,res+len+1)-res-1;
}

void merge(int x){
    int i=1,j=1,it=1;
    while(i<=len&&j<=lens[x])
        if(res[i].first<suf[x][j].first)cach[it++]=res[i++];
        else cach[it++]=suf[x][j++];
    while(i<=len)cach[it++]=res[i++];
    while(j<=lens[x])cach[it++]=suf[x][j++];
    it--;
    len=it;
    Rep(i,1,len)res[i]=cach[i];
    maintain();
}

int calc(int x,int k){
    int ans=1e9+114514;
    Rep(i,1,lenp[x])
        while(len&&(res[len].first|pre[x][i].first)>=k)
            chkmin(ans,pre[x][i].second-res[len].second+1),len--;
    return ans;
}

int main()
{
    # ifndef ONLINE_JUDGE
    freopen("testdata.in","r",stdin);
    //freopen("test1.out","w",stdout);
    # endif
    read(n),read(m);
    Rep(i,1,n)read(a[i]);
    Rep(i,1,n)pos[i]=(i-1)/sq+1;
    bl=pos[n];
    Rep(i,1,bl)L[i]=(i-1)*sq+1,R[i]=i*sq;
    R[bl]=n;
    Rep(i,1,bl)rebuild(i);
    Rep(i,1,m){
        int opt,x,y;
        read(opt),read(x);
        if(opt==1){
            read(y);
            a[x]=y;
            rebuild(pos[x]);
        }
        else{
            int ans=1e9+114514;
            Rep(i,1,bl)if(orsum[i]>=x)chkmin(ans,(int)(lower_bound(mx[i]+1,mx[i]+R[i]-L[i]+2,x)-mx[i]));
            len=0;
            merge(1);
            Rep(i,2,bl){
                chkmin(ans,calc(i,x));
                Rep(j,1,len)res[j].first|=orsum[i];
                maintain();
                merge(i);
            }
            if(ans>1e9)puts("-1");
            else printf("%d\n",ans);
        }   
    }
    return 0;
}