Hello World - Hugo博客搭建笔记

Hello World 无法忍受hexo的速度,故换到hugo,使用主题为PaperMod,正在一步步转移博客内容。 ...

April 1, 2022 · 1 min · Kenshin2438

CSUST - 2022 ACM个人排位赛

出了一堆水题,结果榜歪得离谱?!害,人都麻了。

August 5, 2022 · 15 min · Kenshin2438

一个关于阶乘比值的求和问题(不严谨做法)

问题描述: $$ \sum_{t=0}^{n - 1} \frac{(t+a)!}{t!} = \text{?} $$ 使用wolframalpha,可以见结果为: $$ \sum_{t=0}^{n - 1} \frac{(a + t)!}{t!} = \frac{n \times (a + n)!}{(a + 1) \times n!} $$ 这是一个涉及阶乘求和的问题,但问题同时和分式搅合在一块,比较麻烦。一开始,我回想起高中写的裂项相消,但尝试许久未果,于是便转向求助群里的dalao们。 结果非常amazing啊,瞬间达成共识,裂项,淦就完了。(结果我淦不出来) 眼看dalao们不再关注这个问题,我就顺便逛逛zhihu,准备发个求助帖,然后突然就看见了一个询问$\Gamma$函数欧拉-高斯公式的问题。 众所周知,$\Gamma$函数满足:$\Gamma(n + 1) = n!$,那么这个问题可以换成$\Gamma$函数来写吗? 转换思路 $$ \sum_{t=1}^{n} \frac{\Gamma(t+a)}{\Gamma{(t)}}=\frac{n\Gamma(a+n+1)}{(a+1)\Gamma{(n+1)}} $$ 搜索过程中,我发现等价的问题在2013年就有人提问过,问题链接。没看下面回答之前还挺高兴的,以为这个问题就到此为止了,结果看完人都不好了,给的居然是归纳证明?(证明?谁要证明了?哦,题主啊,那没事了。) 转化成$\Gamma$函数表示后有什么好处呢?个人认为一个很重要的点就是引入了积分。当然,很多时候,无端地引入一些复杂的元素并非明智之举。 积分和求和的顺序转换是解决许多问题的妙手,特别是像这类带着$x^n$的。探索证明时,我发现自己无法将式子转换成$\sum_{t}\Gamma(t)$的形式。那会不会是$\mathrm{B}$函数呢?这两个家伙可是有着莫大的关系! 要解决这个问题,我们需要先了解$\Gamma$函数和$\mathrm{B}$函数的一些重要性质。 $\Gamma(n + 1) = n\Gamma(n)$ $\mathrm{B}(x,y)=\frac{\Gamma(x)\Gamma(y)}{\Gamma(x+y)}=\int_{0}^{1}{t^{x-1}(1-t)^{y-1}}\mathrm{d} t$ 下面是证明: $$ \begin{aligned} \sum_{t=1}^{n} \frac{\Gamma(t+a)}{\Gamma{(t)}} &= \sum_{t=1}^{n} \frac{\mathrm{B}(t+a,-a)}{\Gamma{(-a)}} \\ &= \frac{1}{\Gamma{(-a)}}\sum_{t=1}^{n}\int_{0}^{1}x^{t+a-1}(1-x)^{-a-1}\mathrm{d} x\\ &= \frac{1}{\Gamma{(-a)}}\int_{0}^{1}\left(\sum_{i=a}^{a+n-1}x^{i}\right)(1-x)^{-a-1}\mathrm{d} x\\ &= \frac{1}{\Gamma{(-a)}}\int_{0}^{1}(x^a-x^{a+n})(1-x)^{-a-2}\mathrm{d} x\\ &= \frac{1}{\Gamma{(-a)}}\left[\mathrm{B}(a+1,-a-1)-\mathrm{B}(a+n+1,-a-1)\right]\\ &= \frac{\Gamma{(-a-1)}}{\Gamma{(-a)}}\times\left[\frac{\Gamma{(a+1)}}{\Gamma{(0)}} - \frac{\Gamma{(a+n+1)}}{\Gamma{(n)}}\right]\\ &= \frac{\Gamma{(a+n+1)}}{(a+1)\Gamma{(n)}} = \frac{n\Gamma{(a+n+1)}}{(a+1)\Gamma{(n+1)}} \end{aligned} $$...

June 5, 2022 · 1 min · Kenshin2438

R - 尝试使用Rmarkdown完成数电PPT的制作  [draft]

实际上为Beamer(PDF)输出, R语言用得不太熟练还不如直接用LaTex…

May 30, 2022 · 4 min · Kenshin2438

CSUST - 第十七届ACM程序设计竞赛

贴个题解,看不懂代码就看不懂吧。没用宏定义我已经尽力了。⌓‿⌓

May 22, 2022 · 8 min · Kenshin2438

CSUST - OJ周练题解及代码汇总  [draft]

Warning 代码都是重新写的,所以更新得比较慢,还有部分代码之后再拉上来(最近我考试比较多),如果你们现在需要的话直接私聊我也行。 如果有任何问题,可以直接去群里或者私下找学长学姐问。 代码可以参考,但不要直接照抄,不然看起来是补了题,实则不懂的还是不懂!!! 编译参数: 1 "g++" -std=c++17 -Wall -Ofast -DLOCAL "ac.cpp" -o "ac.exe" 代码缺省: 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 #include <bits/stdc++.h>using namespace std; #ifdef LOCAL #include "debug.hpp"#else #define debug(...) 42 #endif #define PII pair<int, int> #define vec vector #define str string #define fi first #define se second #define all(a) (a)....

May 9, 2022 · 23 min · Kenshin2438

Cpp Tricks - 语言向进阶(?)指南

记录一些常用的C++代码技巧(竞赛向),可能会用到比较高的C++版本。

April 17, 2022 · 6 min · Kenshin2438

多项式Hash函数冲突概率的探究  [draft]

Hash 简介 Hash 的思想很简单,通过某种映射将一个序列或者字符串对应到一个值域较小的值,自然,我们只希望这种映射关系是单射的。 常用的 Hash 函数是一个模意义下的整系数多项式(同余式),例如,对于字符串$S$,定义Hash函数: $$ h(S)=\left(\sum_{i=1}^{|S|}\mathrm{base}^{|S| - i} \times S_i \right) \bmod M $$ 那么,何为 Hash 冲突呢?对于另一个等长的串$T$,满足$T \neq S, h(T)=h(T)$,即: $$ h(T)-h(S) = \left(\sum_{i=1}^{n}\mathrm{base}^{n - i} \times (T_i - S_i) \right) \equiv 0 \pmod{M} $$ 注意到,我们的 Hash 函数中的$\mathrm{base},M$均为自定义的值,显然影响冲突概率的正好是这两数。如果固定模数$M$来讨论这个问题,则只要看$\mathrm{base}\in[1,M)$有多少为该同余式的解。 $M$ 为素数 $\textrm{Lagrange}$定理 $$ f(x)=\sum_{i=0}^{n}a_i\times x^i \equiv 0 \pmod{M} $$ 满足$n>0,a_n \not\equiv 0 \pmod{M},M\in \mathrm{Prime}$,则上同余式最多$n$个解。 证明: 当$n=1$时,一次同余式$a_1x+a_0\equiv 0\pmod{M},a_1\nmid M$显然恰好一个解。 假设定理对于$n-1\geq 1$同余式成立,下面证定理对$n$次同余式也成立。 $M$ 为合数 CRT/孙子剩余定理

March 22, 2022 · 1 min · Kenshin2438

Convolution 卷积与变换  [draft]

卷积积分/离散卷积 多项式卷积 一般来说,多项式卷积表示的就是多项式乘法对应项的系数 $$ c[k] = \sum_{i+j=k}(a[i] \times b[j]) $$ FFT FFT 三次变两次 由于复数平方满足下式: $$ z = a + bj \rightarrow z^2=(a^2 + b^2) + 2abj $$ 我们在所用的复数数组,其实部和虚部分别为两多项式的系数,然后平方取虚部的一半即可得到答案,此时只要一次DFT和一次IDFT。 NTT $$ c[k] = \sum_{i+j=k}(a[i] \times b[j]) \bmod P $$ $P=r\times 2^k+1$为一个素数,$g$为模$P$的原根。 MTT 任意模数NTT,考虑的是没有原根的情况。 异或卷积 $$ c[k] = \sum_{i \oplus j = k}(a[i] \times b[j]) $$ FWT 或卷积/与卷积 OR $$ c[k] = \sum_{i | j = k}(a[i] \times b[j]) $$...

March 12, 2022 · 1 min · Kenshin2438

CSUST - 2021 ACMore新生赛

true Update at 2021.12.14 B题 更新一份Hack数据构造代码 学弟学妹们明年带带 ...

December 13, 2021 · 3 min · Kenshin2438