首先令 $a_n$ 为 $n$ 个奇点的奇树数量，类似的，定义 $b_n$ 为 $n$ 个偶点的偶树数量。

然后令 $A(x)=\sum_{i \ge 0}{a_ix^i}\ ,\ B(x)=\sum_{i \ge 0}{b_ix^i}$.

我们肯定是往根下面连若干个偶树使其成为奇树，或者是往根下面连若干个奇树使其成为偶树。

对于前者，枚举子树的大小，类似背包，可以得到：

$$A(x)=x\prod_{i \ge 1}{(1+x^i+x^{2i}+\dots)^{b_i}}$$

$$=x\prod_{i \ge 1}{(\frac{1}{1-x^i})^{b_i}}$$

乘 $x$ 是因为根本身是一个奇点。

于是：

$$\ln(A(x))=\ln(x)-\sum_{i \ge 1}{b_i\ln(1-x^i)}$$

两边求导：

$$\frac{A'(x)}{A(x)}=\frac{1}{x}+\sum_{i \ge 1}{ib_i\frac{x^{i-1}}{1-x^i}}$$

两边乘 $xA(x)$:

$$xA'(x)=A(x)+A(x)\sum_{i \ge 1}{ib_i\frac{x^i}{1-x^i}}$$

考虑第 $n$ 项系数：

$$na_n=a_n+\sum_{i=1}^{n-1}{a_i\sum_{j=1}^{n-1}{jb_j([x^{n-i}]\frac{x^j}{1-x^j})}}$$

而：

$$\frac{x^j}{1-x^j}=\sum_{i \ge 1}{x^{ij}}=\sum_{i \ge 1}{[j|i]x^i}$$

于是：

$$na_n=a_n+\sum_{i=1}^{n-1}{a_i\sum_{j=1}^{n-1}{jb_j[j|n-i]}}$$

也就是：

$$a_n=\frac{\sum_{i=1}^{n-1}{a_i\sum_{j=1}^{n-1}{jb_j[j|n-i]}}}{n-1}$$

再看后者，类似的，有：

$$B(x)=\prod_{i \ge 1}{(\frac{1}{1-x^i})^{a_i}}-1$$

$-1$ 是因为不存在 $0$ 个偶点的偶树。

类似得到：

$$b_n=\frac{\sum_{i=0}^{n-1}{(b_i+[i=0])\sum_{j=1}^{n}{ja_j[j|n-i]}}}{n}$$

这样就可以使用分治 $NTT$ 解决了，时间复杂度 $O(n\log^2n)$.

拆分成前缀和的形式，$f(x)$ 表示 $[0,x]$ 范围内的解，则答案为 $f(y)-f(x-1)$。

问题等价于将数字转化为 $b$ 进制后 $1$ 的位数为 $k$ 的方案数。

数位 DP 的思想是从高位到低位沿着 $x$ 的上界进行枚举，每次累加这一位取不到上界时的方案数，本题中，这个方案数就是组合数。

时间复杂度为 $O(log^2n)$，瓶颈在于预处理组合数。

细节有：如果 $x$ 满足条件需要在最后累加进去，且一旦有一位上的数大于 $1$ 则代表后面若干位可以任意填 $1$，这时需要跳出循环，选择了 $k$ 个 $1$ 后也应跳出循环，此时后面的若干位应全部填 $0$。

二分图的最大匹配、完美匹配和匈牙利算法

差分约束模板题

本题求最小值，需构造 $\ge$ 不等式组，构图求最长路，如果存在正环，则说明无解。

分析给定的 $5$ 个条件：

（1） $A==B \iff A-B \ge 0\ ,\ B-A \ge 0$；

（2） $A<B \iff B \ge A + 1\ ,B-A\ \ge 1$；

（3） $A \ge B \iff A-B\ \ge 0$；

（4） $A > B \iff A \ge B + 1\ ,A-B \ge 1$；

（5） $A \le B \iff B \ge A , B-A \ge 0$；

另外还有一隐含条件：

每个小朋友都要分到糖果，因此 $x_i \ge 1$。我们可以建立一个超级源点 $x_0 = 0$，则有： $x_i\ ≥\ x_0 + 1 , x_i\ -\ x_0\ \ge 1$，即从0号点到其他所有点连边，边权为1，因为这样可确保到达任意点，到达任意边，满足所有不等式。

因为我们能求出每个 $x_i$ 的最小值，所以总体最小值就是所有的 $x_i$ 之和。

构图建边数：

如果 $K$ 取 $10^5$，假设所有的条件都是（$1$），则需要 $2 \times 10^5$ 条边，从超级源点建边，需要 $10^5$ 条，因此边数预估需要 $3 \times 10^5$ 条边。

另外如果每个小朋友的糖果数是单调递增的，则结果可能爆 $int$，因此需要使用 $long\ long$ 存储结果。

计数问题，考虑 dp。

设 $f(i,j)$ 表示走到点 $i$，路径长度为 $j$ 时的方案数。状态数 $n^2\times c_i$，显然不行。

考虑优化状态。发现当且仅当 $j\in [\mathrm{dis}_i,\mathrm{dis}_i+k]$ 时有贡献，其中 $\mathrm{dis}_i$ 表示 $1\to i$ 的最短路长度。

此时 $f(i,j)$ 表示走到点 $i$，路径长度为 $\mathrm{dis}_i+j$ 的方案数。状态数 $nk$。

考虑判断无解。当且仅当存在 0 环，且 0 环上的点有合法路径时无解。正反跑一次最短路，把 0 边抽出来跑 tarjan 求 scc，对于每个大小 >1 的 scc 判断即可。

洛谷题解里提到，可以记忆化搜索，过程中判断这个状态是否入栈。然而如果这个状态不提供合法路径，这样判断就是错的。这是我的思考，不知道对不对。

对于剩下的图，显然不能 dijkstra 那样 dp 转移，考虑把状态集合抽象成一个 DAG，拓扑排序跑 dp 即可。但是这样有较多的无效边。感觉跑起来不会快。感觉记忆化搜索会好一些，但也不好说，毕竟拓扑常数小，记忆化搜索需要的栈空间很多，常数非常大。

时间复杂度 $\mathcal O(T(m\log m+nk))$。榜上一些 SPFA 跑得比我 dijkstra 快我是不理解的。应该是那个年代还没有针对 SPFA 构造 hack 数据的习惯。

FLOYD算法模板练习题，+FLOODFILL，没什么可说

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <cstring>
using namespace std;

const int MAXN = 165;
const double INF = 1e20;
int n, m, id = 0, field[MAXN], vis[MAXN];
double tot_ans, dis[MAXN][MAXN], md[MAXN], maxdis[MAXN];
struct node{
	double x, y;
}a[MAXN];

double calc(node x, node y){
	double disx = abs(x.x - y.x);
	double disy = abs(x.y - y.y);
	return sqrt(disx*disx + disy*disy);
}

void dfs(int u, int answer){
	vis[u] = 1; field[u] = answer;
	for (int i = 1; i <= n; i++)
		if (!vis[i] && dis[i][u] != INF)
			dfs(i, answer);
}

int main(){
	freopen("cowtour.in", "r", stdin);
	freopen("cowtour.out", "w", stdout);
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i].x >> a[i].y;
	memset(dis, 0x3f, sizeof(dis));
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++){
			char c; cin >> c;
			if (c == '1' || i == j)
				dis[i][j] = calc(a[i], a[j]);
			else dis[i][j] = INF;
		}
	
	for (int i = 1; i <= n; i++)
		if (!vis[i]) dfs(i, ++id);
	
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				if (dis[i][j] > dis[i][k] + dis[k][j])
					dis[i][j] = dis[i][k] + dis[k][j];
	
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++)
			if (dis[i][j] < INF)
				md[i] = max(md[i], dis[i][j]);
		maxdis[field[i]] = max(maxdis[field[i]], md[i]);
	}
	
	tot_ans = INF;
	for (int i = 1; i <= n; i++)
		for (int j = i+1; j <= n; j++)
			if(field[i] != field[j]){
				double maxd = max(max(maxdis[field[i]],maxdis[field[j]]),md[i]+md[j]+calc(a[i],a[j]));
				tot_ans = min(tot_ans, maxd);
			}
	
	printf("%.6f\n", tot_ans);
	
	return 0;
}