4707

题意：无向连通图中，每条边距离为 1，问其中距离起点距离大于 d 的点数。 分析：由起点出发，标记每个点距离起点的距离。 #include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 1e5 + 1 ......

前面的 kthmin-max 容斥的推导到70分做法是平凡的。 当我们写出来一个暴力的时候，我们知道 $dp(i,j)$ 表示选 $i$ 个数，和为 $j$ 的方案数，其系数是 $(-1)^{i-k}\binom{i-1}{k-1}\dfrac{m}{j}$ 的，注意到，这东西仅跟 $i,j$ 有关 ......