A – 铁轨

sb 题，不讲。（为什么 B 组会有这么水的题？）

B – 独立集

这道题翻译过来就是独立集计数，也是一道 sb 题。

首先，这种计数题肯定都是基于树形 DP 的，所以我们来设状态。起初，我设的状态是：该节点所在的子树的独立集个数为 \(dp[u]\)。后面发现不太对劲：状态转移时，大体可以分为两种进行计数，一种是儿子子树内的乘积（包括空集在内，这样就可以算所有的并集个数），还有一种是孙子子树和本节点的独立集。所以，这些信息要分开储存：设\(dp[u][1]\)为独立集个数，\(dp[u][0]\)孙子节点的独立集个数。所以，可以得到下列方程：

\[ dp[u][0] = 1, dp[u][1] = 2, deg[u] = 1 \text{且} u \text{不是根节点} \\ \begin{cases} dp[u][0] = \prod_{v \in son(u)} dp[v][1] – dp[v][0] \\ dp[u][1] = dp[u][0] + \prod_{v \in son(u)} dp[v][1] \end{cases} \]

记得判定根节点的度数时要特殊处理（考场上因此丢掉 70 分）。

// B.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100100, mod = 10081;

int head[MAX_N], current, dp[MAX_N][2], deg[MAX_N], n;

struct edge
{
	int to, nxt;
} edges[MAX_N<<1];

void addpath(int src, int dst)
{
	edges[current].to = dst, edges[current].nxt = head[src];
	head[src] = current++;
}

void dfs(int u, int fa)
{
	if(deg[u] == 1)
	{
		dp[u][0] = 1, dp[u][1] = 2;
		return;
	}
	int tmp_A = 1, tmp_B = 1;
	for(int i = head[u];i!=-1;i=edges[i].nxt)
		if(edges[i].to != fa)
		{
			dfs(edges[i].to, u);
			tmp_A = tmp_A * dp[edges[i].to][1] % mod, tmp_B = tmp_B * (dp[edges[i].to][1] - dp[edges[i].to][0] + mod) % mod;
		}
	dp[u][0] = tmp_B % mod;
	dp[u][1] = (tmp_A + tmp_B) % mod;
}

int main()
{
	memset(head, -1, sizeof(head));
	scanf("%d", &n);
	for(int i = 1, tmpx, tmpy; i <= n - 1; i++)
		scanf("%d%d", &tmpx, &tmpy), addpath(tmpx, tmpy), addpath(tmpy, tmpx), deg[tmpx]++, deg[tmpy]++;
	int rt = 1;
	deg[rt]++;
	dfs(rt, 0);
	printf("%d", dp[rt][1]);
	return 0;
}

C – 石子游戏

真 tm 毒瘤。

这道题很明显是博弈论。首先将目光瞄准\(k=1\)的情况，打表可知形如\(n = 2^x\)的是先手必败局势，下面是解释：

在\(k=1\)的情况下，我们把\(n\)拆解成二进制的数。在游戏一开始，先手就要决定整个游戏的上界，且之后的操作序列肯定是不升的。考虑从二进制数中拿走一些 1 ，然后会发现，在 2 的幂的情况下，每次拿走一部分，都会留下至少一个 1 给对手，这样的话对手就可以在最后一轮赢下整场游戏。

考虑\(k = 2\)的情况，根据某个定理，任意一个正整数都可以被分解成几个 Fibonacci 数，然后发现任意两个不相邻的 Fibonacci 数之间的比例总是大于\(k = 2\)，所以依照这个思路，如果\(n\)为 Fibonacci 数的话，那么就是必败的（由连续的 Fibonacci 数组成），解释如下：

对于\(n\)不为 Fibonacci 数的情况，\(n\)总是可以分解成不连续的 Fibonacci 数列之子序列的和，这样的话，在不连续的地方，倍数总是大于\(k=2\)，所以我们就可以在这里制造最后一次的取石子的动作，这样就可以完成必胜序列；而对于\(n\)为 Fibonacci 数的情况，每一个 Fibonacci 数都可以被重新分解，所以连续的情况下，对手取走两倍之内的石子数简直就是易如反掌！这样就是必败局势。

考虑泛情况，我们也可以构造一个数列，类似于 Fibonacci 数列。要构造一个这样的\( \{ a_i \} \)，我们可以开一个辅助序列\( \{ b_i \} \)，表示前\(i\)个中，合法（求和顺序要符合取石子的顺序）加起来的最大数字。这样的话，考虑下一个\(a_{i+1}\)时就可以直接从\(b_i\)处转移即可，然后合法取数多加一个指针指向上一个满足\(ka_{cursor} < a_i\)的就行了。

// C.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2000000;

int ai[MAX_N], bi[MAX_N], T, n, k;

int main()
{
	scanf("%d", &T);
	for (int cas = 1; cas <= T; cas++)
	{
		scanf("%d%d", &n, &k);
		int i = 0, j = 0;
		ai[0] = bi[0] = 1;
		while (ai[i] < n)
		{
			i++;
			ai[i] = bi[i-1]+1;
			while(ai[j + 1] * k < ai[i])
				j++;
			if(ai[j]* k < ai[i])
				bi[i] = bi[j] + ai[i];
			else
				bi[i] = ai[i];
		}
		printf("Case %d: ", cas);
		if (ai[i] == n)
			printf("lose\n");
		else
		{
			int ans = 0;
			while (n != 0)
			{
				if(n >= ai[i])
					n -= ai[i], ans = ai[i];
				i--;
			}
			printf("%d\n", ans);
		}
	}
	return 0;
}