1

2

3

4

## cactus

Definition: each edge of the graph at most belongs to a single circle.

We can process tree easily, so consider how to convert a cactus into a tree.

[Circle-Square Tree]

## Game Theory

Basic definition:

BZOJ 2275

# Fibonacci game.

Theorem The game with initial state of Fibonacci number will get failed.
Proof. By induction.
(i) Obv $i = 2$ get failed. Checked.
(ii) Assume $i \le k$ valid. Let $i = k + 1$. Denote $x$ as the first amount, $y$ as the second.
We have $x \ge \frac{1}{3} f_{k-1}, y \le \frac{2}{3} f_{k-1} \le \frac{1}{2} f_k$. The second one get the last stone, which means the first failed. QED.

Theorem(Zeckendorf) $\forall n \in \mathbb{N}\_+$, n can be represented by a discontiniousness sequence of Finobaccis.
Proof: By induction.
(i) $n = 2, 3$, obv.
(ii) Assume $n = 1..m-1$ valid. Consider the case of $n = m$.
(a) $m \in \mathcal{F}$, valid.
(b) $m \not\in \mathcal{F}$, let $F_{n_1} < m < F_{n_1+1}$, we have $m' = m - F_{n_1} < F_{n_1-1}$, by assumption, follow the previous we can define such $n_i$ s. Since $n_2 < n_1-1$, we get the conclusion. QED

By the 2 thms above, we know the previous player who take $\min F_n$ at the very first time will win the game.

## Code (8632 kb 4 ms)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>
#include <stack>
using namespace std;
{
T p = 1, n = 0; char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '-') p = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){n = n * 10 + ch - '0'; ch = getchar();}
x = p * n;
}
const int maxn = 1e6;
long long f[maxn];
int main()
{
f[0] = 1, f[1] = 2;
int cur;
for(cur = 2; f[cur - 1] <= n; cur++) f[cur] = f[cur - 2] + f[cur - 1];
cur--;
while(n)
{
while(f[cur] > n) cur--;
if(f[cur] == n)
{
printf("%lld\n", f[cur]);
return 0;
}
n -= f[cur];
}
return 0;
}

HDU 2516

## Code(1540K,0)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>
#include <stack>
using namespace std;
{
T p = 1, n = 0; char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '-') p = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){n = n * 10 + ch - '0'; ch = getchar();}
x = p * n;
}
const long long maxn = 1e6, maxm = 1LL << 31;
long long f[maxn];
set<long long> S;
int main()
{
long long n;
f[0] = 0, f[1] = 1; S.insert(0); S.insert(1);
for(int cur = 2; f[cur - 1] <= maxm; cur++)
f[cur] = f[cur - 2] + f[cur - 1], S.insert(f[cur]);

puts(S.count(n) ? "Second win" : "First win");
return 0;
}

## Wythoff Game

Theorem(Beatty) Let $\frac{1}{\alpha} + \frac{1}{\beta} = 1, \alpha, \beta \text{~irrational}, a_n = \lfloor \alpha n \rfloor, b_n = \lfloor \beta n \rfloor$, then we have
(1) ${a_n}, {b_n}$ is increasing;
(2) ${a_n} + {b_n} = \mathbb{N_+}$.
Proof. (1) It's easy to find out $\alpha,\beta > 1$, which implies the increasing.
(2) Assume that $a_p \le k, a_{p+1} > k, k \in \mathbb{N}_+$. We have

\begin{align} \alpha p < k+1 \\\\ \alpha(p+1)>k+1 \end{align} \Rightarrow p = \lfloor \frac{k+1}{\alpha} \rfloor \\\\ \Rightarrow S = \frac{k+1}{\alpha} + \frac{k+1}{\beta} \\\\ \Rightarrow k-1<S<k+1 \\\\ \Rightarrow S = k

which means the previous k numbers get the first k numbers in natural number set.
Q.E.D.

By definition of the game, we can easily figure out that each odd situation (shown by a pair (a, b)) satisfies the following proposition: (Assume the first element of the pair is less than the second)
(i) We have $(a_i, a_i + k)$ for the $k$-th odd;
(ii) a_i is the minimum excluded integer from the previous pairs;
(iii) The first non-trial odd is $(1,2)$.

By Beatty's Theorem, we let $\beta - \alpha = 1$, then we know the sequence $a, b$ is what we find to describe the odds of the game. In general, each odd has a form as $(\lfloor \frac{1+\sqrt{5}}{2} n \rfloor, \lfloor \frac{1+\sqrt{5}}{2} n + n \rfloor)$, where $n$ is an integer meaning the order.