Fibonacci博弈

Problem

两个人进行Fibonacci博弈,若先手要有必胜策略,求他第一次至少要取多少个?

Solution

由Fibonacci博弈可知,如果当前石子数是fibonacci数,则先手必败,所以此时当前的先手必须全部取走

齐肯多夫(zeckendorf)定理:任何一正整数都能拆成一堆互不相同的正整数的和,且一定存在一种取法取到不超过它的最大Fibonacci数

1+

测试推莫反&打LaTeX的速度

无聊,不看论文和博客我能否手推莫比乌斯反演公式?

计时开始13:34

Möbius function:
\[
\mu(n) = \left\{\begin{matrix}0 & \mathrm{if} \: n \: \mathrm{is \: NOT \: square free.}\\ (-1)^{\omega (n)} & \mathrm{if} \: n \: \mathrm{is \: square \: free.} \end{matrix}\right.
\]

To Prove:
\[
\displaystyle{F(n) = \sum_{d|n} f(d)} \Rightarrow \displaystyle{f(n) = \sum_{d|n} \mu(d) F \left ( \frac{n}{d} \right)}
\]

Proof:
\[
\begin{align} \quad \sum_{d|n} \mu(d) F \left ( \frac{n}{d} \right ) &= \sum_{d|n} \mu(d) \sum_{d|n} f \left ( \frac{n}{d} \right ) \\ &= \sum_{d|n} \mu(d) \sum_{e|\frac{n}{d}} f(e) \\ &= \sum_{d|n} \sum_{e|\frac{n}{d}} \mu(d) f(e) \end{align}
\]
From \( e | \frac{n}{d} \Rightarrow d | \frac{n}{e}\) and \( \mu \circ \mathit{1} = \iota \)we deduce that
\[
\begin{align} \quad \sum_{e|n} \mu (d) F \left ( \frac{n}{d} \right ) &= \sum_{e|n} \sum_{d|\frac{n}{e}} \mu(d) f(e) \\ &= \sum_{e|n} \left ( f(e) \cdot \sum_{d|\frac{n}{e}} \mu(d) \right ) \\ &= \sum_{e|n} f(e) \iota \left ( \frac{n}{e} \right ) \\ &= \sum_{e|n} f(e) \cdot \left\{\begin{matrix} 0 & \mathrm{if} \: e \neq n \\ 1 & \mathrm{if} \: e = n \end{matrix}\right. \\ &= f(n) \end{align}
\]

Hence \(\begin{align} \quad f(n) = \sum_{d|n} \mu(d) F \left ( \frac{n}{d} \right ) \quad \blacksquare \end{align}\)

计时结束13:47

13分钟打完以上内容

1+

FFT-多项式乘法【模板】

UOJ的那道题

0

解不定方程ax+by=c【模板】

若c不是gcd(a,b)的倍数,那么一定不存在整数解

0

China Reminder Theorem 模板

继续考前打模板

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

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

返回顶部