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

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

五月 30, 2022 · Kenshin2438

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

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

五月 22, 2022 · 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)....

五月 9, 2022 · Kenshin2438

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

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

四月 17, 2022 · Kenshin2438

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

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}$来讨论这个问题,则只要看$\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}$,由于$M\nmid a_1$,显然恰好一个解。 当$n\geq M$结论显然成立。 当$2 \leq n \leq M - 1$时,我们进行反证。假设上式有多余$n$个解(不妨令为$x_0,x_1,\dots,x_k,(k \geq n+1)$,并且$\forall i\neq j, x_i \not\equiv x_j\pmod{M}$) 由于: $$f(x)-f(x_0)\equiv\sum_{i=0}^{k}a_i(x^i-x_0^i)=(x-x_0)g(x)\pmod{M}$$ 容易知道,此时的$g(x)$为一个$n-1$次多项式,且$[x^{n-1}]g(x)=a_n\not\equiv 0\pmod{M}$。...

三月 22, 2022 · 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]) $$...

三月 12, 2022 · Kenshin2438

CSUST - 2021 ACMore新生赛

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

十二月 13, 2021 · Kenshin2438

用来避免行末空格的cout<<"\n "[i < n];是什么语法?

在算法竞赛中,很多赛题都需要输出一整个数组,但是由于评测姬的机制不同,某些OJ会卡行末空格,这样的体验是很痛苦的,如果不报PE那更是要命。 在众多避免行末空格的方法中,cout << "\n "[i < n];显得十分简洁,但是它究竟是什么语法允许的?之前一直想不通,今天突然想到了下标,测试了一下果真如此,同时也找到了具体的语法依赖。 ...

十二月 3, 2021 · Kenshin2438

CSUST - 2021 组队选拔赛

闲言 比赛链接:传送门 没有代码,放心食用。 ...

十月 23, 2021 · Kenshin2438

$V+F-E=2$ 平面图欧拉示性数公式

一直没啥想写的,不过最近又看见一道和欧拉示性数公式相关的思维题,所以萌生出了写这篇博客的想法。 首先是关于平面图欧拉示性数公式的定义: 设$G$是一个连通的平面图,顶点的数目为$V$,边的数目为$E$,面的数目为$F$,则有$$V+F-E=2$$ ...

九月 23, 2021 · Kenshin2438