0

T2

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

T3

$$O(k(n+m))$$，实际上还要带个常数$$16$$

0

T2

$$O((NM+Q)\log N+QM)$$

T3

$\text{subfactorial}_n = n! \sum _{k=0}^n \frac{(-1)^k}{k!}$

0

T2

$$k \leq 5 \times 10^5$$

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

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

0

GCD of Divisors

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

Solution

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

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

$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 ]$

……

$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}]$

$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)$

$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)$

$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$

$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$

$\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]$

$$\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”的…真实太愚蠢了

$\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\}$

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}$

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}}

$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)$

$B_{p+n} \equiv B_n+B_{n+1} (\mod p)$

$B(x) = \sum _{n=0}^{\infty } \frac{B_n x^n}{n!}=e^{e^x-1}$

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

0

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

$3T^n = R_{n}+(a+b)S_{n-1}+3(a^2+b^2)T_{n-1}$

q-Continued fraction

$\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

$\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}$

$\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

$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