Maths, OI, and other amazing stuffs!

1030总结

T1

这一题太水了,然而还是写错了 TwT 以后要认真读题

T2

答案是

\[ \frac { \left[ \sum _ { i = 1 } ^ {  { k } } \sum _ { j = 1 } ^ {  { k } } \operatorname { dis } \left( d _ { i } , d _ { j } \right) \right] \times ( k – 1 ) ! } { k ! }\]

然后\( O(n)\)树形dp即可

T3

考虑从每个点向外出发,状压一个\(S\)表示\(4P+1 \sim 4P+3\)步走到的点。
然后bfs即可。
检验某个点是否被覆盖\(k\)次,如果是则符合题意。
\(O(k(n+m))\),实际上还要带个常数\(16\)

0

1031总结

T1

考虑概率=合法方案数/所有方案数
所有方案数\(n^n\)
合法方案数:\(f_n = f_{n-1} + (n-1) f_{n-2}\)
打表就可以发现这个规律
然后就没了

T2

考虑分治,每次预处理mid向左向右的背包
然后每次处理跨中点的询问
\(O((NM+Q)\log N+QM)\)

T3

满分做法:
考虑错位排列的方案数定义
\[ \text{subfactorial}_n = n! \sum _{k=0}^n \frac{(-1)^k}{k!}\]
概率就是除掉n!
显然\(\displaystyle \sum _{k=0}^n \frac{(-1)^k}{k!} \) 收敛于 \( \dfrac{1}{e}\)
树链剖分维护(大到一定值(大概25左右)就不用修改了),均摊线段树

0

1101总结

T1

共有\( n \)种竞赛,对于其中任意\( i \)种竞赛,\(1≤i≤n\),有\(a_i\)个人同时参加,问有多
少个人参加了至少一门竞赛?

傻逼容斥。系数即为组合数。加个大模数。没了

T2

有一棵\( n \)个点的树,每个叶子节点上都有一个人,他们按照每秒钟走一条边的
速度向树根(节点\( 1\))前进。
你可以运用\( k \)次瞬移,让某一个节点(除了根节点)上的所有人瞬间(耗时为\( 0\))
转移到这个节点的父亲上。
你想知道最少需要多少时间,所有人可以到达根节点。

\( k \leq 5 \times 10^5\)
贪心,搞个优先队列

T3

有一个\( n \)面的骰子,第\( i \)面的数是\( v_i\),朝上的概率是\( p_i\)。
不停地抛这个骰子,直到某一面朝上了两次,就停止抛骰子,求所有朝上的面
的数字的和的期望\( E \)是多少. \( n \leq 500\)

想了一个\(n^2\)做法
看pdf

0

Positive numbers expressible as a product of Fibonacci numbers


Given a positive integer n, decide whether it is expressible as a product of Fibonacci numbers. That is:

\[ n \stackrel{?}{=} \prod_{i = 1}^k f_i^{p_i} \text{ with } f_i \text{ distinct Fibonacci numbers and all } p_i > 0.\]

t turns out to have a very straightforward solution. The numbers expressible as a product of Fibonacci numbers are known and even have their own »OEIS sequence«, which however does not explain how to find out whether a given number if expressible in this form. The answer is the following procedure which only takes \(O(\log n)\) time:

  • Let \(f_1,f_2,…,f_k\) be the finite sequence of Fibonacci numbers smaller or equal to \(n\), in decreasing order, except \(8\) and \(144\).
  • For each \(f_i\) in this order, divide \(n\) by \(f_i\) as many times as possible.
  • If the number remaining, in the end, is \(1\), \(n\) is expressible as a product of Fibonacci numbers, otherwise, it is not.

Proof. If the remaining number is \(1\), we have just expressed \(n\) as a product of Fibonacci numbers. Conversely, assume \(n\) is expressible as some product of Fibonacci numbers. First off, we substitute any appearance of \(8\) and \(144\) in the product for \(2⋅2⋅2\) and \(2⋅2⋅2⋅2⋅3⋅3\) respectively. Let \(f_1\) be the largest Fibonacci number in the product. By Carmichael’s theorem, there exists a prime \(p_1\) which divides both \(n\) and \(f_1\) but none of the other Fibonacci numbers in the product. The number of \(f_1\) ‘s in the product must be then equal to the exponent \(e_1\) of \(p_1\) in prime factorisation of \(n\), which is also the “maximal number of times that \(f_1\) divides n”. Similarly, \(f_2\) (the second largest Fibonacci number in the product) appears in the product \(e_2\) times, which is the “maximal number of times that \(f_2 \)divides \(\dfrac n {f_1^{e_1}}\).Continuing, the number that remains at the end of the procedure will be \(\dfrac {n} {f_1^{e_1} f_2^{e_2} \cdots f_k^{e_k}} = 1\)

A code snippet that does the job is below. It gives the answer instantly for numbers as big as Python’s arithmetic allows.

 

0

1102总结

T1

原题就是让你化简式子:
\[
\begin{aligned}
\sum _ { j = l } ^ { r } \left( \begin{array} { c } { j } \\ { k + j – l } \end{array} \right) &= \sum _ { j = l } ^ { r } \left( \begin{array} { c } { j } \\ { l – k } \end{array} \right)
\\
&= \left( \begin{array} { c } { r + 1 } \\ { l – k + 1 } \end{array} \right) – \left( \begin{array} { c } { l } \\ { l – k + 1 } \end{array} \right)
\end{aligned}
\]

T2

判断是否能加入一条边时,如果这条边的两端已经联通,我们需要知道这个联通块是否有环。
如果不连通,那么可以加入这条边,而且通过两端的联通块是否有环可以得到新的联通块是
否有环。
于是我们用并查集维护连通性,额外维护联通块里是否有环即可
\( O ( ( n + m ) \log n )\)

T3

哈希二分的方法其实就是不断的询问字符串的某一部分的哈希值。
我们可以用线段树来维护哈希值,那么每次修改一个位置只需要把父亲的线段树改一个位置。
利用主席树来维护,比较的时候也从主席树的两个根开始递归比较,可以做到\( O \left( n \log ^ { 2 } n \right) \)

0

GCD of Divisors

\[
\bigstar \fbox{此题极难。全世界通过者不足200人。慎入。}
\]

Problem Description

每个\(n \)的因子\(d\)都有它的对偶因子\(\dfrac{n}{d}\)

设\(f(n)\)是\(n\)的所有正除数\(d\)和\(\dfrac{n}{d}\)的最大公约数之和,即\(\displaystyle f(n)=\displaystyle\sum\limits_{d|n}\, \text{gcd}(d,\frac n d)\)

令\(F\)为\(f\)的和,也就是\(\displaystyle F(k)=\displaystyle\sum\limits_{n=1}^k \, f(n)\)

已知\(F(10)=32,  F(1000)=12776\)

求\(F(10^{15})\)

Solution

此题的难点就在于公式难推导,需要拐好几个弯。重点的地方都已经加粗表示,希望读者认真体会

这个范围显然杜教筛也是做不了的,而且考虑直接化简\(f(n)\)也遇到了困难,所以考虑将前缀和的\(\sum\)一起化简

\[ F(n)=\sum_{i=1}^{n}\sum_{d|i}\left (d,\frac{i}{d} \right ) \]

这一步很常见的是第一重和式改为枚举倍数,但这样化简后面就推不下去了。

想到这种题通常的做法都要化成\( \sigma_0(n)\)的形式(有gcd,又需要是积性函数)

还是用套路,直接枚举gcd值

\[ F(n)=\sum_{d=1}^{n}d\sum_{i=1}^{n}\sum_{g|i}\left [ \left (g,\frac{i}{g} \right)=d \right ] \]

这里有\( \displaystyle \left (g,\frac{i}{g} \right)=d\),说明\(i\)中必须至少包含\(2\)个\(d\),那么令,\(g\)即可任取\(i\)的因子,最终的\(g\)和\(\dfrac{i}{g}\)各乘\(d\)即可,所以可以进行如下化简

\[ F(n)=\sum_{d=1}^{n}d\sum_{i=1}^{\frac{n}{d^2}}\sum_{g|i}\left[ \left (g,\frac{i}{g} \right )=1 \right ]\]

看起来不像可以转化为\( \varphi\)

……

好像卡住了!算了,直接使出绝招—莫比乌斯反演!

\[F(n)=\sum_{d=1}^{n}d\sum_{i=1}^{\frac{n}{d^2}}\sum_{g|i}\sum_{d’|g \cap d’|\frac{i}{g}}\mu(d’) \\
F(n)=\sum_{d=1}^{n}\sum_{d’=1}^{n}d \circ \mu(d’)\sum_{i=1}^{\frac{n}{d^2}}\sum_{g|i}[d’|g \cap d’|\frac{i}{g}]\]

这里和上面一样,都是要求\(d’|g\)并且\(d’|\dfrac{i}{g}\),因此从\(i\)中提取\(2\)\(d’\),即令\(i=\dfrac{i}{d’^2}\)。

\[ F(n)=\sum_{d=1}^{n}\sum_{d’=1}^{n}d \circ \mu(d’)\sum_{i=1}^{\frac{n}{(dd’)^2}}\sum_{g|i}1\]

会发现后面是约数个数。

\[ F(n)=\sum_{d=1}^{n}\sum_{d’=1}^{n}d \circ \mu(d’)\sum_{i=1}^{\frac{n}{(dd’)^2}}\sigma_0(i)\]

前面部分发现\(d \circ μ(d’)\)可以卷积到\(\varphi\),考虑合并\(dd’\)来构造卷积,令\(d=dd’\)

\[ F(n)=\sum_{d=1}^{\sqrt{n}}\sum_{g|d}g \circ \mu \left (\frac{n}{g} \right )\sum_{i=1}^{\frac{n}{(dd’)^2}}\sigma_0(i) \]

为什么只枚举到\( \sqrt{n}\),因为\( d> \sqrt{n}\)之后的\( \sum=0\)没有贡献。因此可以缩小实际枚举范围

然后根据狄利克雷卷积\(\mu \circ \text{N} =\varphi(N(n)=n)\)可以化简

\[ F(n)=\sum_{d=1}^{\sqrt{n}}\varphi(d)\sum_{i=1}^{\frac{n}{(dd’)^2}}\sigma_0(i)\]

其中,约数个数的前缀和可以进行分块取值优化,如下

\[ \sum_{i=1}^{n}\sigma_0(i)=\sum_{i=1}^{n}\sum_{d|i}1=\sum_{i=1}^{n}\sum_{j=1}^{\frac{n}{i}}1 \\
\sum_{i=1}^{n}\sigma_0(i)=\sum_{i=1}^{n}\left \lfloor \frac{n}{i} \right \rfloor
\]

然后线性筛\( \varphi\)的过程中求解即可

\[ O \left (\sum_{i=1}^{\sqrt{n}}\sqrt{\frac{n}{i^2}}\right ) = O \left (\sum_{i=1}^{\sqrt{n} }\frac{\sqrt{n}}{i} \right)= O \left (\int_{1}^{\sqrt{n} }\frac{\sqrt{n}}{i} \text{d} i \right) = O \left (\sqrt{n} \ln \sqrt{n} \right )\]

0

复习复习…各种奇奇怪怪的数…


最近也不想学什么新的♂了,就把老本啃一啃当作复习吧

要讲各种神奇的数,第一肯定少不了我们的——组合数!

Binomial Coef

组合数,也被称为二项式系数,它长这样:
\[ \left(
\begin{array}{c}
n \\
k \\
\end{array}
\right) \]
还可以长这样
\[
C_{n}^k
\]
意义是相同的,就是\(n\)个元素里面取\(k\)个的方案数,都等于\(\dfrac{n!}{k!(n-k)!}\)
组合数最著名的公式恐怕是这个了:
\[ \left(
\begin{array}{c}
n \\
k \\
\end{array}
\right)=\left(
\begin{array}{c}
n \\
n-k \\
\end{array}
\right)=\left(
\begin{array}{c}
n-1 \\
k-1 \\
\end{array}
\right)+\left(
\begin{array}{c}
n-1 \\
k \\
\end{array}
\right)\]
好了接下来得请出一位重磅嘉宾了

Stirling number

你说说看一个数还分个两类是不是很烦…

Stirling number of First Kind

第一类斯特林数长这样:

\[ \displaystyle \left[
\begin{array}{c}
n \\
k \\
\end{array}
\right] \]

好像还可以写成什么大S形式,不大清楚,那种记法不仅容易和另一类斯特林数混淆而且比较丑陋

\( \displaystyle \left[
\begin{array}{c}
n \\
k \\
\end{array}
\right] \)计算的是将\(n\)个元素拍成\(k\)个轮换(cycle)(不是正规子群链那个cycle),所以我们将\( \displaystyle \left[
\begin{array}{c}
n \\
k \\
\end{array}
\right] \)读作“n轮换k”

PS: 在没读CM之前我一直是念“中括号nk”的…真实太愚蠢了

接下来就亮出递推公式叭,推导懒得写了,自行google

\[ \left[
\begin{array}{c}
n \\
k \\
\end{array}
\right]=(n-1)\left[
\begin{array}{c}
n-1 \\
k \\
\end{array}
\right]+\left[
\begin{array}{c}
n-1 \\
k-1 \\
\end{array}
\right]\]

另外值得注意的是,排列和轮换本质上是相同的。因此我们可以脑补出一个公式:

\[ \sum _{k=0}^n \left[
\begin{array}{c}
n \\
k \\
\end{array}
\right]=n!,n\geq 0\]

Stirling number of Second Kind

第二类斯特林数事实上比第一类常用…

它长这样

\[ \left\{
\begin{array}{c}
n \\
k \\
\end{array}
\right\}\]

表示将一个有\(n\)件物品的集合划分成\(k\)个非空子集的方案数。

怎么避免与第一类斯特林数的混淆?有个很妙的方法:集合也是用花括号记的,第二类斯特林数里面有“子集”二字,读作“n子集k”(聪明的你一定已经猜到没读CM前的我把它称为什么了)

关于这个数我们也有几个好玩的式子:

1.\[ \left\{
\begin{array}{c}
n \\
2 \\
\end{array}
\right\}=2^{n-1}-1,n>0\]这个应该很容易脑补

2.递推公式: \[ \left\{
\begin{array}{c}
n \\
k \\
\end{array}
\right\}=\left\{
\begin{array}{c}
n-1 \\
k-1 \\
\end{array}
\right\}+k \left\{
\begin{array}{c}
n-1 \\
k \\
\end{array}
\right\}\]

推导也不详细说了,考虑最后一个元素怎么放即可

接下来介绍一个没什么用的东西

Bernoulli number

伯努利数好像在数论上挺有用的,虽然我不知道怎么个有用法…目前只在一些渐进式里面遇到

它用生成函数定义的,这个定义方式就很不亲民…

\[ \frac{z}{e^z-1}=\sum _{n=0}^{\infty } \frac{B_n z^n}{n!}, z\in \mathbb{C}\]

还是来看一下递推定义叭,这个简直…

\[ B_n=[m=0]-\sum _{k=0}^{m-1} \frac{B_k \left(
\begin{array}{c}
m \\
k \\
\end{array}
\right)}{-k+m+1}\]

看到这个东西就已经不想知道它是干啥的了

事实上还是很有趣的,比如证明所有自然数的平方倒数和就有一种伯努利的极短的证法,主要用了它的生成函数的亚纯的性质以及Mittag-Leffler定理,具体证明不写了,网上也找不到= =

找到了发评论吧(

Bell number

\(B_n\)是基数为\(n\)的集合划分数目。集合S的一个划分是定义为S的两两不相交的非空子集的族,它们的并是S。例如\(B_3 = 5\),因为3个元素的集合{a, b, c}有5种不同的划分方法:
{{a}, {b}, {c}}
{{a}, {b, c}}
{{b}, {a, c}}
{{c}, {a, b}}
{{a, b, c}}

关于它的一些公式很有意思:

首先如果我们跟斯特林数联系起来的话,每个贝尔数都是第二类Stirling数的和,也就是

\[
B_n=\sum _{k=1}^n \left \{
\begin{array}{c}
n \\
k \\
\end{array}
\right\}
\]

然后递推公式也很容易写,就是
\[
B_{n+1}=\sum _{k=0}^n B_k \left(
\begin{array}{c}
n \\
k \\
\end{array}
\right)
\]
看上去比较怪异…还带个\( \sum\)

并且Bell数也适合Touchard同余:
若\( p \in Primes\)
那么
\[ B_{p+n} \equiv B_n+B_{n+1} (\mod p)\]
怎么证的窝不知道,窝也不想知道…

当然还要来看一下它的母函数,这次是egf而不是ogf了…
\[ B(x) = \sum _{n=0}^{\infty } \frac{B_n x^n}{n!}=e^{e^x-1}\]
怎么样…秀不秀…

Bell数还符合一个叫做Dobinski公式的东西,不过概率论我学的没太深入,所以不懂

0

关于Fibonacci number的一些comment


关于Tribonacci constant…

对于Fibonacci number, 它的discriminant \( \sqrt{5}\)起作用,对于Tribonacci series来说,它就变成了\( \sqrt{11}\)

Sequences

Given three sequences with recurrence \( s_n = s_{n-1}+s_{n-2}+s_{n-3}\)but different initial values as,
\[
\begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline
\text{Name} & \text{Formula} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & OEIS\\
\hline
R_n & x_1^n+x_2^n+x_3^n &3 &1 &3 &7 &11 &21 &39 & 71 & A001644 \\
\hline
S_n &\frac{x_1^n}{y_1}+\frac{x_2^n}{y_2}+\frac{x_3^n}{y_3}&3 &2 &5 &10 &17 &32 &59 &108 &(none)\\
\hline
T_n &\frac{x_1^n}{z_1}+\frac{x_2^n}{z_2}+\frac{x_3^n}{z_3}&0 &1 &1 &2 &4 &7 &13 &24& A000073 \\
\hline
\end{array}
\\
y_i =\tfrac{1}{19}(x_i^2-7x_i+22)
\\
z_i =-x_i^2+4x_i-1
\]
\( x_i \)是方程\(x^3-x^2-x-1=0\)的根,其中\(T_n\)是Tribonacci series,它的实根\(T = x_1 \approx 1.83929\)近似于Tribonacci constant

Powers

令\( a=\dfrac{1}{3}(19+3\sqrt{33})^{1/3},\; b=\dfrac{1}{3}(19-3\sqrt{33})^{1/3} \), then powers of the tribonacci constant \(T\) can be expressed in terms of those three sequences as,
\[ 3T^n = R_{n}+(a+b)S_{n-1}+3(a^2+b^2)T_{n-1}\]

q-Continued fraction

令\( q = -1/(e^{\pi\sqrt{11}})\)则
\[ \frac{(e^{\pi\sqrt{11}})^{1/24}}{\frac{1}{T}+1} = 1 + \cfrac{q}{1-q + \cfrac{q^3-q^2}{1 + \cfrac{q^5-q^3}{1 + \cfrac{q^7-q^4}{1 + \ddots }}}}\]

Snub cube

https://en.wikipedia.org/wiki/Snub_cube

Pi Formula

令\( v = 1/T\)则

\[ \sum_{n=0}^\infty \frac{(2n)!^3}{n!^6}\frac{2(4v+1)(2v+1)n+(4v^2+2v-1)}{(v+1)^{24n}} =\frac{4}{\pi}\]

Infinite Nested Radical

\[ \frac{1}{T-1} = \sqrt[3]{\frac{1}{2}+ \sqrt[3]{\frac{1}{2}+ \sqrt[3]{\frac{1}{2}+ \sqrt[3]{\frac{1}{2}+\dots}}}}\]

Complete elliptic integral of the first kind

它的精确值是

\[
K(k_{11}) = \frac{1}{11^{1/4}(4\pi)^2} \bigl(\tfrac{T+1}{T}\bigr)^2\; \Gamma\bigl(\tfrac{1}{11}\bigr) \Gamma\bigl(\tfrac{3}{11}\bigr) \Gamma\bigl(\tfrac{4}{11}\bigr) \Gamma\bigl(\tfrac{5}{11}\bigr) \Gamma\bigl(\tfrac{9}{11}\bigr) = 1.570983\dots
\]

Cubic Pell-Type Equation

丢番图三次Pell型方程
\[
a^3 – 2 a^2 b + 2 b^3 – a^2 c – 2 a b c + 2 b^2 c + a c^2 + 2 b c^2 + c^3=1
\]
有无穷多组整数解
\[ a,\;b,\;c = T_{n-1},\;T_{n-2},\;T_{n-3}\]

0

对偶范畴小记


对偶概念的一切一切的本质是对偶范畴.

在同一个范畴里,对象之间通过态射相联系. 而在不同的范畴之间,则通过函子联系:函子把一个范畴里的对象映到另一个范畴里的对象,同时把对象间的态射映到相应对象间的态射. 这性质简直逆天. 我先给出共变函子和反变函子的定义:

定义1:设\( \mathcal{C} \)和\( \mathcal{D} \)是两个范畴. 从\( \mathcal{C} \)到\( \mathcal{D} \)的共变函子(covariant functor) \(F:\mathcal{C}\rightarrow \mathcal{D}\) 满足两个性质
(1)它把\( \mathcal{C} \)中的对象\( A \)映为 \(\mathcal{D} \)中的对象\( F(A)\)
(2)它把态射\( f\in \mathrm{hom}_{\mathcal{C}}(A,B) \)映为态射\( F(f)\in \mathrm{hom}_{\mathcal{D}}(F(A),F(B))\) , 这些映射要满足下列条件:

(I) 对于\( \mathcal{C} \)中的对象\( A \)都成立\( F(1_A)=1_{F(A)} \);

(II)\( F(gf)=F(g)F(f) \)对于\( \mathcal{C} \)中所有使\( gf \)有意义的态射\( f \)和\( g \).

定义2:设\( \mathcal{C} \)和\( \mathcal{D} \)是两个范畴. 从\( \mathcal{C} \)到\( \mathcal{D} \)的反变函子(contravariant functor) \(G:\mathcal{C}\rightarrow \mathcal{D} \)满足两个性质
(1)它把\( \mathcal{C} \)中的对象\( A \)映为\( \mathcal{D} \)中的对象\( G(A)\)
(2)它把态射\( f\in \mathrm{hom}_{\mathcal{C}}(A,B) \)映为态射\( G(f)\in \mathrm{hom}_{\mathcal{D}}(G(A),G(B))\), 这些映射要满足下列条件:

(I) 对于\( \mathcal{C} \)中的对象\( A \)都成立\( G(1_A)=1_{G(A)} \);

(II)\( G(gf)=G(g)G(f) \)对于\( \mathcal{C} \)中所有使\( gf \)有意义的态射\( f \)和\( g \).

反变函子就是把共变函子的箭头换个方向.

基于这样的想法和以上的概念,对于给定一个范畴\( \mathcal{C} \), 我们会这样给出对偶范畴(dual category)\( \mathcal{C}^{op}\) : 使得 \(\mathrm{ob}(\mathcal{C}^{op})=\mathrm{ob}(\mathcal{C}) \), 且\( \mathrm{hom}_{\mathcal{C}}(B,A)=\mathrm{hom}_{\mathcal{C}^{op}}(A,B) \).从这个定义就可以看出\( \mathcal{C}^{op} \)中的共变函子就是\( \mathcal{C} \)中的反变函子.

举个例子:考虑范畴\( \mathcal{C} \)是域上的有限维向量空间, 态射是向量空间之间的同构映射. 如果\( f:V\rightarrow U \)是\( \mathcal{C} \)里的态射, 那么就有它的对偶映射\( \bar{f}:U^*\rightarrow V^* \)也是\( \mathcal{C} \)里的态射, 且有\( [\bar{f}(u^*)](v)=u^*[f(v)] . \)如果定义 \(G:\mathcal{C}\rightarrow \mathcal{C},G(V)=V^{**} \), 实际上是一种同构.

从范畴角度来讲为什么会经常出现一些对偶的概念, 因为当我们看到\( f:A\rightarrow B \)这样的关系时总希望箭头反过来也能成立, 由此对偶的概念必然会产生的.

0

玄学排序

Problem

有一种排序叫做玄学排序,大概是这样的,每次随机选两个数进行交换,直到原数组有序

玄学排序的交换次数被定义为交换过程的执行次数(也就是随机两个数算一次交换)。

小 S 开始专注于研究长度为\( n \)的排列,他想知道,在你运气足够好的情况下(即每次冒泡排序的交换次数都是可能的最少交换次数,仿佛有上帝之手在操控),对于一个等概率随机的长度为\(n \)的排列,进行这样的玄学排序的期望交换次数是多少?\( n ≤ 10^7, T \leq 10^5, mod = 998244353 \)

0

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部