T1

1、

​ $f(1) = \text{popcount}(1) + \text{popcount}(0) = 1$

​ $ f(4) = \text{popcount}(3) + \text{popcount}(1) = 3$

​ $f(9) = \text{popcount}(7) + \text{popcount(2)} = 4$

2、 解法一：

$$f(x) = \begin{cases} f(\frac {x -1}{2}) +1, &\text{当 $x$ 为奇数}\\ f(\frac x 2 -1) +2, &\text{当 $x$ 为奇数} \end{cases} $$

​ 解法二：

​ 令 $c$ 为最大的 $i$ 使得 $2^i -1\leq n$，则 $f(n) = \text{popcout}(c) + \text{popcount}(n-c)$.

3、 $2324$

T2

1、 写出一种拆分并画出图，例：$7 = 1+1+2+3$

2、 可重拆分：$7$ 种，不可重拆分： $3$ 种.

3、 对于 $n$ 的一种不可重拆分，把元素从小到大排序后既满足：

$$a_1<a_2<a_3<\cdots < a_{k-1}< a_k$$

​ 删去楼梯部分后，满足：

$$a_1 -1\leq a_2 - 2 \leq a_3 -3 \leq \cdots \leq a_{k-1} -(k-1) \leq a_k - k $$

​ 因为条件从小于变为了小于等于，所以得到的即为可重拆分.

4、 把得到的 Ferrers 图旋转 90° 重新排序，得到的依然是一个可重拆分的 Ferrers 图，且原先对列数的限制变成了对最高列高度的限制，易得旋转先后 Ferrers 图对应的可重拆分是双射的，所以整数 $n$ 可重拆分成最多不超过 $i$ 个数的和的方案数等于 $n$ 可重拆分成最大不超过 $i$ 的方案数.

T3

1、 奇数先手必胜偶数先手必败.

2、 存在，先手拿 $n-1$ 颗，对方至少拿 $1$ 颗，则先手者胜利.

3、 石子数是 $k+1$ 的倍数时必败，否则先手必胜。

理由：设 $f(n)$ 是石子数为 $n$ 时先手必胜或者必败，其中 $1$ 为必胜，$0$ 为必败

$$f(n) = [\sum_{i=\max(n-k,0)}^{n-1} f(i) \neq k]$$

这个式子的意义是：如果他能转移到的所有状态中对方都是必胜的，那他必败，否则他转移到对方必败的状态即必胜.

$1\sim k +1$ 中只有 $k+1$ 是先手必败的，因为 $1\sim k$ 都能拿到剩 $0$ 个的状态，则他们拿到剩 $0$ 个即必胜，而 $k+1$ 只能拿到剩下 $1\sim k$ 的情况，这些情况对方都是必胜的，所以他是必败的，后面部分同理。

策略：每次拿走 $n' \bmod (k+1)$ 个石子即可，易证不会超过 $k$ 个.

4、 易得：设一个状态 $S$ 每堆石子的 $\mid$ 运算和为 $f(S)$，则有：

• $f(\{0,0,\cdots,0\}) = 0$

• 若 $f(S)\neq 0$，选出最大的那一堆 $X$，由 $a\mid b \leq \max(a,b)$ 得，$f(S / \{a_X\}) \leq a_X$.

  又因为 $f(S) \neq 0$，所有 $f(S/\{a_X\}) \mid a_X \neq 0$，$f(S/\{x\}) \neq X$，则 $f(S/\{a_X\})<a_X$

  所以把 $X$ 这堆拿到 $f(S/\{a_x\})$，则 $f(S') = f(S/\{a_x\}) \mid f(S/\{a_x\}) = 0$

• 若 $f(S) = 0$，假设从 $X$ 堆拿了 $k$ 个，易得：$f(S')= f(S)\mid X\mid (X-k)$，

  易得 $X\mid (X-k)\neq 0$，则 $f(S')\mid X \mid (X-k) \neq 0$.

​ 则当 $f(S) = 0$，转移到的状态一定存在 $f(S') \neq 0$ 的，当 $f(S) = 0$，所有转移到的节点 $f(S') \neq 0$.

​ 那么假如先手拿到的 $f(S) \neq 0$，我们走到任意一个 $f(S') = 0$ 的状态，那对方必然会走回到 $f(S'') \neq 0$ 的状态，易知有限步内必走到 $T=\{0,0,\cdots, 0\}$ 的情况，此时 $f(T) = 0$，一定是该后手操作，则后手必败，先手必胜。

​ 反之也成立.

T4

1、 $(n-1)!$

2、 $(n-1)!$

3、 $9$

4、 不会，给定 $f_0, f_1$，设 $f(n-2),f(n-1)$ 没有计重，有：

通过第一种方案，我们从 $f(n-1)$ 的方案转移而来，所以原排列不会计重，而相同排列不同交换位置会导致 $n$ 的位置不同，不会计重，所以第一种方案里没有计重；

第二种方法，从 $f(n-2)$ 的方案转移而来，同理；

而第一种方案不会存在第二种方案 $f_i =n, f_n = i$ 的情况，所以两种方案之间不会计重.

​ 则归纳得 $f(n)$ 没有计重.

5、 $f(n) = (n-1) [f(n-1) + f(n-2)]$

6、 一个 trivial 的结论，每个联通块其实就是错排的一个置换环。

设所有长为 $n$ 错排的置换环个数和为 $f(n)$，所有长为 $n$ 错排个数为 $g(n)$.

考虑错排计数的递推的组合意义，当前 $n-1$ 个 交换结束，与 $a_n$ 交互的是 $i$，当且仅当此时 $a_i =i$ 才会产生新的置换环，那么本质上由 $n$ 造成的置换环的增量为 $(n-1)g(n-2)$，剩下的直接乘上系数继承即可.

则有：

$$f(n)=(n-1)[f(n-1)+f(n-2)+g(n-2)]$$

​ 那么答案即为 $\frac {f(n)} {g(n)}$。

7、 枚举置换环大小，得到式子：

$$f(n)=\sum_{k=2}^n k^2 \binom n k (k-1)! g(n-k)$$

其中 $g(n)$ 是长度为 $n$ 的错排的个数，可以做到 $O(n)$ 递推，那么每次暴力计算这个式子复杂度 $O(Tn)$

考虑化式子。

$$\begin{aligned} f(n)&=\sum_{k=2}^n k^2 \binom n k (k-1)! g(n-k)\\&=\sum_{k=2}^n k^2 \frac {n!}{(n-k)!k!} (k-1)! g(n-k)\\ &=n!\sum_{k=2}^n k \frac {g(n-k)}{(n-k)!} \end{aligned} $$

考虑生成函数：

$$A(x)=\sum_{k=2}^\infty kx^k =\frac {x}{(1-x)^2}-x\\ G(x)=e^{\ln \frac 1 {1-x}-x}=\frac {e^{-x}}{1-x} $$

那么 $f(n) =n![x^n]A(x)G(x)$.

尝试化简：

$$A(x)G(x) = \frac {xe^{-x}}{(1-x)^3} - \frac {e^{-x}}{1-x}+e^{-x} $$

考虑前面单独计算，设 $B(x) = \frac {e^{-x}}{(1-x)^3}$，则有：

$$\begin{aligned} B'(x)&=\frac {3e^{-x}}{(1-x)^4} - \frac {e^{-x}}{(1-x)^3}\\ &= 3\frac {B(x)}{1-x} - B(x) \\ (1-x)(B'(x)+ B(x))&= 3B(x) \end{aligned} $$

取 $n$ 次项系数可得到：

$$b_{n+1} + b_n - n(b_n+b_{n-1})=3b_n$$

化简可得

$$b_{n+1} = (n+2)b_n + nb_{n-1}$$

那么可得：

$$A(x)G(x) = x(B(x)- G(x))$$

则：

$$f(n)=n(b_{n-1} - g_{n-1})$$