斯特林数取模小素数 - Congruence for Stirling Number

笔者在此并不想涉及过多的组合内容,其一,诸如此类的介绍文章在zhihu和csdn已经大量存在;其二,笔者并无自信将斯特林数的知识点吃透,也不觉得自己能够在这种理解程度下,提供什么特别的内容。 但是,本人在Google检索的过程中却鲜少见Stirling数取模小素数的内容,所以在基本明白之后,在此记录。 关于Stirling数的组合性质,推荐繁凡的《小学生都能看懂的三类斯特林数从入门到升天教程 》(含性质完整证明、斯特林反演、拉赫数) 关于斯特林数取模,只检索到 《第一类Stirling数的Lucas定理》 (不知道为啥是B站,好迷,公式排版不太能看懂) 定义 以及 前置知识 将 $n$ 个元素分成 $k$ 组,每组内部进行环排列,这样的方案数称为无符号第一类斯特林数,记作 $c(n, k)$。 可以发现,$c(n, k)$ 存在如下的递推关系: $$c(n, k) = (n − 1)c(n − 1, k) + c(n − 1, k − 1)$$ 定义有符号第一类斯特林数 $s(n, k) = (−1)^{n−k}c(n, k)$,则有 $$(x)_ {n} = x(x − 1) \dots(x − n + 1) = \sum_{k=0}^{n} s(n,k) x^k$$ 将 $n$ 个元素分成 $k$ 个非空集合,集合之间不计顺序,这样的方案数称为第二类斯特林数,记作 $S(n, k)$。 可以发现,$S(n, k)$ 存在如下的递推关系: $$S(n, k) = S(n − 1, k − 1) + kS(n − 1, k)$$...

九月 1, 2022 · Kenshin2438

关灯问题(Lights Out) - Light chasing

有一个$n \times n$的方阵,每个位置上都有一盏灯。每次可以选择一个格子,选定后它与它相邻(有公共边)的格子的亮暗状态都会发生改变。现给定初始方阵中每盏灯的亮暗情况,请输出一个使所有灯都熄灭的方案。 该问题在wikipedia上的词条 Lights Out(game),尚未有中文页。 如有读者想验证自己的程序,可在LibreOJ提交,LibreOJ #6243. 关灯问题 。 初探 如果你有线性代数的相关知识储备,相信你此时已经意识到,该问题可以做如下的转换: 有$n^2$个开关,一共控制了$n^2$盏灯。同时,我们也已知每个开关所控制的灯集合。所以,只要将方程(一共$n^2$个,变量为每个开关的状态)列出,解决这个线性方程组便解决了这道题。 至于代码实现,不过是一个Gaussian elimination,写成记录异或路径的线性基也可,这个应该不是问题。甚至,对于某些原题自动机,可能已经找到了原题。 问题到这似乎已经解决,但是时间复杂度呢? 无论选择以上哪种实现,时间复杂度都在妥妥的$\mathcal{O}(\frac{n^6}{\omega})$。 $n$很小时,或许能够在$1s$内解决。例如这题,gym102920 J。 一个或许可行的方案 怎么办呢?无脑冲高斯消元似乎是不可能的了,那么,可以优化吗?于是,你开始注意到,这个系数矩阵似乎有点意思啊!(以$n=5$为例) $$ \left( \begin{matrix} C & I & O & O & O \newline I & C & I & O & O \newline O & I & C & I & O \newline O & O & I & C & I \newline O & O & O & I & C \newline \end{matrix} \right) $$...

八月 29, 2022 · Kenshin2438

CSUST - 2022 ACM个人排位赛

写点题外话 出题的时候: “大水题,大铁牌题” “别出太难了,到时候大家都不会写,跟没出一样。” “这场是不是太简单了点,感觉难度都没选拔赛高啊?” “预计rank1在8题左右,其他人写个4,5题的样子。” “20的应该都见过这些题(指字典树和线段树这两题),感觉要被过穿啊!” “简单点好啊,大家多过点题,开心一点。” 然后…… “怎么有人搁那挂机啊?” “为什么不关同步流?你在干什么啊?!” “看不懂。” “训练了啥?” “我麻了。” “这个榜是不是有点惨啊。” “快看看其它题,快看看其它题……” “hy,你的茶颜没了” 太惨了,不过前面的几位同学打得还可以,在我预期的范围内。其他人要好好加油啊,你们那刷题量也太可怜了,ACM又不是纯理论,是要求代码实现的!暑训没刷个3,4百题,感觉也没什么意义。 给个查刷题数目的网站,都去看看自己。还有一点就是,为了冲题量而去刷水题没有任何意义。 OJ Analyzer CF 刷题类型分析 编译参数 1 -std=c++17 -Wall -O2 -DLOCAL -ID:\Document\repos\Code-of-ACM\template\debug\ 如需运行以下代码,编译环境至少需要c++14,最好是c++17。 以下代码均为个人验题使用的代码,不代表出题人的std写法。在语法上,除了结构化声明和结构化绑定为c++17标准、复数字面量1i从c++14才开始有定义,其它用到的语法和函数均在c++11标准内。另,使用了GCC的built-in函数,不保证其它编译器能通过编译。 代码缺省 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 #include <bits/stdc++.h> using namespace std; using ll = long long; #define all(a) begin(a), end(a) #ifdef LOCAL #include "debug....

八月 5, 2022 · 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)}} \newline &= \frac{1}{\Gamma{(-a)}}\sum_{t=1}^{n}\int_{0}^{1}x^{t+a-1}(1-x)^{-a-1}\mathrm{d} x\newline &= \frac{1}{\Gamma{(-a)}}\int_{0}^{1}\left(\sum_{i=a}^{a+n-1}x^{i}\right)(1-x)^{-a-1}\mathrm{d} x\newline &= \frac{1}{\Gamma{(-a)}}\int_{0}^{1}(x^a-x^{a+n})(1-x)^{-a-2}\mathrm{d} x\newline &= \frac{1}{\Gamma{(-a)}}\left[\mathrm{B}(a+1,-a-1)-\mathrm{B}(a+n+1,-a-1)\right]\newline &= \frac{\Gamma{(-a-1)}}{\Gamma{(-a)}}\times\left[\frac{\Gamma{(a+1)}}{\Gamma{(0)}} - \frac{\Gamma{(a+n+1)}}{\Gamma{(n)}}\right]\newline &= \frac{\Gamma{(a+n+1)}}{(a+1)\Gamma{(n)}} = \frac{n\Gamma{(a+n+1)}}{(a+1)\Gamma{(n+1)}} \end{aligned} $$...

六月 5, 2022 · Kenshin2438

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

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

五月 22, 2022 · Kenshin2438

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

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 卷积与变换

卷积积分/离散卷积 多项式卷积 一般来说,多项式卷积表示的就是多项式乘法对应项的系数 $$ 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]) $$ AND $$ c[k] = \sum_{i \& j = k}(a[i] \times b[j]) $$...

三月 12, 2022 · Kenshin2438

CSUST - 2021 ACMore新生赛

Changelog Update at 2021.12.14 B题 更新一份Hack数据构造代码 学弟学妹们明年带带 我永远喜欢樱岛麻衣(思维) $(x_1,y_1),(x_2,y_2)$ 之间的曼哈顿距离为 $d=|x_1-x_2|+|y_1+y_2|$ ,即两点各方向上坐标之差的绝对值的和。 如果使得其中一点为零点 $(0,0)$ ,另一点为 $(x,y)$ ,那么式子简化成 $d=|x|+|y|$ ,在坐标平面上的图像如下: 我们至少需要两条线才能保证确定麻衣学姐的位置,即在方格中两幅图像只具有一个交点时。(可以选择同一条边的两端点) 但是要注意一个特殊情况,由于我们待求的是整点,对于 $n=1$ 或 $m=1$ 的情况,只需要一个点就能确定; 但同时,当 $n=1$ 且 $m=1$ 时,方格中只有一个整点,故不需要选择点,答案为 $0$ 。 lq的简单题(思维,map) 数组的平均数为 $Average = \frac{1}{n}\sum_{i=1}^{n}a_i$ ,如果删除两数后平均数依旧保持不变,这说明,删去的两个数的平均数和数组的平均数相等,则它们的和为 $2\times Average$ 。所以,问题转变成求解有多少和为 $2\times Average$ 的不同数对。 我们只要枚举其中一个数,看看剩余数中值为 $2\times Average - a_i$ 的数的个数,累计求和就好了(注意不要重复计算)。 使用c++的同学这时候可以直接上map了。(可能是double在此处的精度足够高,或着数据太水,map<double, int>确实能过) 但除此之外别无他法了吗?考虑到 $a_i$ 均为整数,那么$2\times Average$ 若是不为整数,则必然无解;反之,则原先的浮点误差就不复存在了,使用数组cnt[]记录个数的方案就可行了(记得初始化和开2倍的空间)。 下面的代码用于Hack赛中某位同学的代码。随机数据确实没考虑到使用map<int, int>的key值溢出问题(变成long long后强制转换到int)。 Hack思路 32位整值溢出可以理解为在模 $2^{32}$ 意义下同余,那么代码实际求值会包括一部分满足下面式子的数对 $$ n\times(2\times avg - a_i - a_j)\equiv 0 \pmod{2^{32}} $$...

十二月 13, 2021 · Kenshin2438