[ABC298Ex] Sum of Min of Length
在下文的推导中假设 \(\operatorname{depth}_{L} \le \operatorname{depth}_R\)，若不符合则交换 \(L\) 和 \(R\)。
首先我们可以发现，我们可以找到 \(R\) 的 \(\left\lfloor\frac{\operatorname{dist}\left(L, R\right)}{2}\right\rfloor\) 级祖先 \(M\)。可以发现，在 \(M\) 子树内的节点距离 \(R\) 更近，而在 \(M\) 子树外的节点距离 \(L\) 更近。因此我们可以将问题转化为求 \(M\) 子树内的节点到 \(R\) 的距离和 \(M\) 子树外的节点到 \(L\) 的距离和。若 \(M\) 为 \(L\) 和 \(R\) 的最近公共祖先那么特殊考虑即可。
考虑如何计算答案，首先以求 \(M\) 子树内的节点到 \(R\) 的距离和为例，我们不妨求出所有节点到 \(R\) 的距离和后排除非 \(M\) 子树节点的贡献。具体的，通过换根 DP 我们可以对于每个节点 \(u\) 求出 \(f_u\) 代表所有节点到 \(u\) 的距离和，\(g_u\) 代表其子树内的全部节点到 \(u\) 的距离和。那么 \(M\) 子树内的节点到 \(R\) 的距离和即为：
\[f_R - \left(f_M - g_M\right) - \left(N - \operatorname{size}_M\right) \times \operatorname{dist}\left(M, R\right) \]其中 \(N\) 为节点总数，\(\operatorname{size}_M\) 为 \(M\) 子树的节点数。同理，\(M\) 子树外的节点到 \(L\) 的距离和为：
\[f_L - g_M - \operatorname{size}_M \times \operatorname{dist}\left(M, L\right) \]直接计算即可。
Code
#include <bits/stdc++.h>
typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;
valueType N, Q;
ValueMatrix G;
ValueVector InTree, OutTree, size, depth, father, son, top;
ValueVector leftBound, rightBound, node;
void dfs(valueType x, valueType from) {
father[x] = from;
size[x] = 1;
depth[x] = depth[from] + 1;
InTree[x] = 0;
for (auto const &to : G[x]) {
if (to == from)
continue;
dfs(to, x);
size[x] += size[to];
InTree[x] += InTree[to] + size[to];
if (son[x] == 0 || size[to] > size[son[x]])
son[x] = to;
}
}
void build(valueType x, valueType from, valueType _top) {
static valueType dfsCount = 0;
top[x] = _top;
if (from != 0)
OutTree[x] = OutTree[from] - (InTree[x] + size[x]) + (N - size[x]) + InTree[x];
leftBound[x] = ++dfsCount;
node[dfsCount] = x;
if (son[x] != 0)
build(son[x], x, _top);
for (auto const &to : G[x]) {
if (to == from || to == son[x])
continue;
build(to, x, to);
}
rightBound[x] = dfsCount;
}
valueType GetLCA(valueType u, valueType v) {
while (top[u] != top[v]) {
if (depth[top[u]] < depth[top[v]])
std::swap(u, v);
u = father[top[u]];
}
return depth[u] < depth[v] ? u : v;
}
valueType GetDist(valueType u, valueType v) {
if (u < 1 || u > N || v < 1 || v > N)
return 0;
return depth[u] + depth[v] - 2 * depth[GetLCA(u, v)];
}
valueType Jump(valueType u, valueType k) {
while (u != 0) {
if (depth[u] - depth[top[u]] + 1 <= k) {
k -= depth[u] - depth[top[u]] + 1;
u = father[top[u]];
} else {
return node[leftBound[u] - k];
}
}
return 0;
}
valueType solve(valueType u, valueType v) {
if (u == v)
return OutTree[u];
if (depth[u] > depth[v])
std::swap(u, v);
valueType lca = GetLCA(u, v);
valueType const dist = GetDist(u, v);
valueType const mid = Jump(v, dist / 2);
valueType ans = 0;
ans += OutTree[v];
ans -= (OutTree[mid] - InTree[mid]) + (N - size[mid]) * GetDist(mid, v);
ans += OutTree[u];
ans -= InTree[mid] + size[mid] * GetDist(mid, u);
return ans;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
std::cin >> N;
G.resize(N + 1);
InTree.resize(N + 1);
OutTree.resize(N + 1);
size.resize(N + 1);
depth.resize(N + 1);
father.resize(N + 1);
son.resize(N + 1);
top.resize(N + 1);
leftBound.resize(N + 1);
rightBound.resize(N + 1);
node.resize(N + 1);
for (valueType i = 1; i < N; ++i) {
valueType u, v;
std::cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1, 0);
OutTree[1] = InTree[1];
build(1, 0, 1);
std::cin >> Q;
for (valueType q = 0; q < Q; ++q) {
valueType u, v;
std::cin >> u >> v;
std::cout << solve(u, v) << '\n';
}
std::cout << std::flush;
return 0;
}
信封问题
定义在排列 \(p\) 中满足 \(p_i = i\) 的 \(i\) 为确定点，设 \(f(n, k)\) 表示在长度为 \(n\) 的排列中钦定有 \(k\) 个确定点的方案数，\(g(n, k)\) 表示在长度为 \(n\) 的排列中恰好有 \(k\) 个确定点的方案数。那么我们有：
\[f(n, k) = \sum\limits_{i = k}^{n} \dbinom{i}{k} g(n, i) \]根据二项式反演，我们有：
\[g(n, k) = \sum\limits_{i = k}^{n} \dbinom{i}{k} \left(-1\right)^{i - k} f(n, i) \]考虑如何求 \(f(n, k)\)，发现我们确定了 \(k\) 个点后，剩下的 \(n - k\) 个点可以任意排列，因此我们有：
\[\begin{aligned} f(n, k) =& \dbinom{n}{k}\left(n - k\right)! \\ =& \frac{n!}{k!} \\ \end{aligned}\]而我们要求的是错排数，即 \(g(n, 0)\)，那么我们有：
\[\begin{aligned} g(n, 0)=& \sum\limits_{i = 0}^{n} \dbinom{i}{0} \left(-1\right)^{i} f(n, i) \\ =& \sum\limits_{i = 0}^{n} \left(-1\right)^{i} \frac{n!}{i!} \\ \end{aligned}\]直接计算即可，复杂度 \(O\left(n\right)\)。
Code
#include <bits/stdc++.h>
typedef long long valueType;
typedef std::vector<valueType> ValueVector;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
valueType N;
std::cin >> N;
ValueVector Fact(N + 1, 1);
for (valueType i = 1; i <= N; ++i)
Fact[i] = Fact[i - 1] * i;
valueType ans = 0;
for (valueType i = 0; i <= N; ++i) {
if (i & 1)
ans -= Fact[N] / Fact[i];
else
ans += Fact[N] / Fact[i];
}
std::cout << ans << std::endl;
return 0;
}
已经没有什么好害怕的了
首先我们可以将题目要求的转化为恰好存在 \(k\) 对满足 \(a_i > b_i\)。
首先将序列 \(a, b\) 均按升序排列，设 \(h_{i, j}\) 表示只考虑前 \(i\) 位，选出 \(j\) 对满足 \(a_i > b_i\) 的方案数。那么我们有：
\[h_{i, j} = h_{i - 1, j} + \left(r_i - \left(j - 1\right)\right) \cdot h_{i - 1, j - 1} \]其中 \(r_i = \max\limits_{k \le i \land b_k < a_i} k\)。不难发现 \(r_{i - 1} \le r_{i}\)，因此使用一个指针维护即可。
发现上述 DP 求出的方案数与题意不符，考虑如何修正。由于上述 DP 求出的是至少存在 \(j\) 对的方案数，我们可以考虑使用二项式反演将其转化为恰好存在 \(j\) 对的方案数。设 \(f(k)\) 表示钦定存在 \(k\) 对满足 \(a_i > b_i\) 的方案数，\(g(k)\) 表示恰好存在 \(k\) 对满足 \(a_i > b_i\) 的方案数。那么我们有：
\[f(k) = \sum\limits_{i = k}^{n} \dbinom{i}{k} g(i) \]根据二项式反演，我们有：
\[g(k) = \sum\limits_{i = k}^{n} \dbinom{i}{k} \left(-1\right)^{i - k} f(i) \]考虑如何求出 \(f(k)\)，发现 \(f(k)\) 与 \(h_{n, k}\) 的区别是 \(h_{n, k}\) 未考虑剩余的数对的方案数，因此我们有：
\[f(k) = h_{n, k} \times \left(n - k\right)! \]直接计算即可，复杂度 \(O\left(n^2\right)\)。
Code
#include <bits/stdc++.h>
typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;
namespace MODINT_WITH_FIXED_MOD {
constexpr valueType MOD = 1e9 + 9;
template<typename T1, typename T2, typename T3 = valueType>
void Inc(T1 &a, T2 b, const T3 &mod = MOD) {
a = a + b;
if (a >= mod)
a -= mod;
}
template<typename T1, typename T2, typename T3 = valueType>
void Dec(T1 &a, T2 b, const T3 &mod = MOD) {
a = a - b;
if (a < 0)
a += mod;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 sum(T1 a, T2 b, const T3 &mod = MOD) {
return a + b >= mod ? a + b - mod : a + b;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 sub(T1 a, T2 b, const T3 &mod = MOD) {
return a - b < 0 ? a - b + mod : a - b;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 mul(T1 a, T2 b, const T3 &mod = MOD) {
return (long long) a * b % mod;
}
template<typename T1, typename T2, typename T3 = valueType>
void Mul(T1 &a, T2 b, const T3 &mod = MOD) {
a = (long long) a * b % mod;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 pow(T1 a, T2 b, const T3 &mod = MOD) {
T1 result = 1;
while (b > 0) {
if (b & 1)
Mul(result, a, mod);
Mul(a, a, mod);
b = b >> 1;
}
return result;
}
}// namespace MODINT_WITH_FIXED_MOD
using namespace MODINT_WITH_FIXED_MOD;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
valueType N, K;
std::cin >> N >> K;
if ((N - K) & 1) {
std::cout << 0 << std::endl;
return 0;
}
ValueVector Fact(N + 1, 1), InvFact(N + 1, 1);
for (valueType i = 1; i <= N; ++i)
Fact[i] = mul(Fact[i - 1], i);
InvFact[N] = pow(Fact[N], MOD - 2);
for (valueType i = N - 1; i >= 0; --i)
InvFact[i] = mul(InvFact[i + 1], i + 1);
auto C = [&](valueType n, valueType m) -> valueType {
if (n < 0 || m < 0 || n < m)
return 0;
return mul(Fact[n], mul(InvFact[m], InvFact[n - m]));
};
ValueMatrix F(N + 1, ValueVector(N + 1, 0));
F[0][0] = 1;
ValueVector A(N + 1, 0), B(N + 1, 0);
for (valueType i = 1; i <= N; ++i)
std::cin >> A[i];
for (valueType i = 1; i <= N; ++i)
std::cin >> B[i];
std::sort(A.begin() + 1, A.end());
std::sort(B.begin() + 1, B.end());
std::swap(A, B);
valueType pointer = 0;
F[0][0] = 1;
for (valueType i = 1; i <= N; ++i) {
while (pointer < N && A[pointer + 1] < B[i])
++pointer;
for (valueType j = 0; j <= N; ++j) {
F[i][j] = F[i - 1][j];
if (j == 0)
continue;
Inc(F[i][j], mul(pointer - j + 1, F[i - 1][j - 1]));
}
}
K = K + (N - K) / 2;
valueType ans = 0;
for (valueType i = K; i <= N; ++i) {
if ((i - K) & 1) {
Dec(ans, mul(C(i, K), mul(F[N][i], Fact[N - i])));
} else {
Inc(ans, mul(C(i, K), mul(F[N][i], Fact[N - i])));
}
}
std::cout << ans << std::endl;
return 0;
}
[JLOI2016] 成绩比较
首先，我们将方案数分为两部分：
- 选出 \(k\) 名被碾压的同学并分配每位同学每个学科的分数与 B 神的关系。
- 对每个学科的分数进行排列。
对第一部分做出一点解释：将计算碾压同学的方案数和分配分数与 B 神的关系放到一起是因为一位同学各学科的分数与 B 神的关系决定了其是否被碾压，因此需要将其放到一起考虑。
下面考虑如何计数，首先是第一部分。若不考虑除我们钦定外的同学是否被碾压，那么我们钦定已经有 \(w\) 名同学被碾压，而其余 \(n - w - 1\) 名同学是否被碾压是不确定的，因此我们有：
\[f_{w} = \prod\limits_{i}\dbinom{n - w - 1}{R_i - 1} \]发现这样计数在这 \(n - w - 1\) 名同学中可能存在同学被碾压，因此 \(f_w\) 实质上表达的是钦定有 \(w\) 名同学被碾压的方案数，设 \(g_w\) 表示恰好有 \(w\) 名同学被碾压的方案数，那么我们有：
\[f_w = \sum\limits_{i = 1}^{w} \dbinom{w}{i} g_i \]根据二项式反演，我们有：
\[g_w = \sum\limits_{i = 1}^{w} \dbinom{w}{i} \left(-1\right)^{w - i} f_i \]因此我们可以在 \(\mathcal{O}(nm)\) 的时间内求出 \(g_k\)，完成第一部分的计数。
下面考虑第二部分，如何统计每个学科的分数排列方案数。首先由于各学科是独立的，因此我们只需要考虑如何求解单独一门学科的方案数即可。设 \(U\) 表示该门学科的最高分，\(r\) 表示 B 神在这门学科中的排名
由于分数的值域较大，不能直接计算，因此我们考虑枚举有多少种分数，设有 \(t\) 种分数，那么一种直观的想法是枚举 B 神的分数 \(i\)，进而可以确定两个分数段及其对应的人数，有 \(x\) 人的分数一个长度为 \(l\) 的区间内的方案数为 \(l^x\)，因此上述计数方法对应的计算式为：
\[f_t = \sum\limits_{i} i^{n - r}\times\left(n - i\right)^{r - 1} \]但是我们可以发现上述计数方法存在一个问题，即可能会计算到实际分数种类不足 \(t\) 的情况，因此我们不妨设 \(f_t\) 表示给定 \(t\) 种分数的情况下赋分方案数，\(g_t\) 表示恰好使用 \(t\) 种分数的赋分方案数，那么我们有：
\[f_t = \sum\limits_{i = 1}^{t} \dbinom{t}{i} g_i \]根据二项式反演，我们有：
\[g_t = \sum\limits_{i = 1}^{t} \dbinom{t}{i} \left(-1\right)^{t - i} f_i \]因此我们可以在 \(\mathcal{O}(n^2)\) 的时间内求出 \(g_t\)，完成第二部分的计数。
总复杂度为 \(\mathcal{O}(n^2m)\)。
Code
#include <bits/stdc++.h>
typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;
typedef std::map<valueType, valueType> ValueMap;
typedef std::vector<ValueMap> MapVector;
namespace MODINT_WITH_FIXED_MOD {
constexpr valueType MOD = 1e9 + 7;
template<typename T1, typename T2, typename T3 = valueType>
void Inc(T1 &a, T2 b, const T3 &mod = MOD) {
a = a + b;
if (a >= mod)
a -= mod;
}
template<typename T1, typename T2, typename T3 = valueType>
void Dec(T1 &a, T2 b, const T3 &mod = MOD) {
a = a - b;
if (a < 0)
a += mod;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 sum(T1 a, T2 b, const T3 &mod = MOD) {
return a + b >= mod ? a + b - mod : a + b;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 sub(T1 a, T2 b, const T3 &mod = MOD) {
return a - b < 0 ? a - b + mod : a - b;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 mul(T1 a, T2 b, const T3 &mod = MOD) {
return (long long) a * b % mod;
}
template<typename T1, typename T2, typename T3 = valueType>
void Mul(T1 &a, T2 b, const T3 &mod = MOD) {
a = (long long) a * b % mod;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 pow(T1 a, T2 b, const T3 &mod = MOD) {
if (a == 0)
return b == 0 ? 1 : 0;
T1 result = 1;
while (b > 0) {
if (b & 1)
Mul(result, a, mod);
Mul(a, a, mod);
b = b >> 1;
}
return result;
}
}// namespace MODINT_WITH_FIXED_MOD
using namespace MODINT_WITH_FIXED_MOD;
class BinomialCoefficient {
private:
valueType N;
ValueVector Fact, InvFact;
public:
BinomialCoefficient() = default;
BinomialCoefficient(valueType n) : N(n), Fact(N + 1, 1), InvFact(N + 1, 1) {
for (valueType i = 1; i <= N; ++i)
Fact[i] = mul(Fact[i - 1], i);
InvFact[N] = pow(Fact[N], MOD - 2);
for (valueType i = N - 1; i >= 0; --i)
InvFact[i] = mul(InvFact[i + 1], i + 1);
}
valueType operator()(valueType n, valueType m) {
if (n < 0 || m < 0 || n < m)
return 0;
if (m > N)
throw std::out_of_range("BinomialCoefficient::operator() : m > N");
if (n <= N)
return mul(Fact[n], mul(InvFact[m], InvFact[n - m]));
valueType result = 1;
for (valueType i = 0; i < m; ++i)
Mul(result, n - i);
Mul(result, InvFact[m]);
return result;
}
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
valueType N, M, K;
std::cin >> N >> M >> K;
BinomialCoefficient C(N);
ValueVector U(M + 1, 0), R(M + 1, 0);
for (valueType i = 1; i <= M; ++i)
std::cin >> U[i];
for (valueType i = 1; i <= M; ++i)
std::cin >> R[i];
valueType ans = 1;
{// part one
ValueVector F(N + 1, 0);
for (valueType i = 0; i < N; ++i) {
valueType const remain = N - i - 1;
F[i] = C(N - 1, i);
for (valueType j = 1; j <= M; ++j)
Mul(F[i], C(remain, R[j] - 1));
}
valueType sum = 0;
for (valueType i = K; i <= N; ++i) {
if ((i - K) & 1) {
Dec(sum, mul(F[i], C(i, K)));
} else {
Inc(sum, mul(F[i], C(i, K)));
}
}
Mul(ans, sum);
}
std::cerr << "ans = " << ans << std::endl;
{// part two
for (valueType m = 1; m <= M; ++m) {
ValueVector F(N + 1, 0);
for (valueType t = 1; t <= N; ++t) {
for (valueType i = 1; i <= t; ++i)
Inc(F[t], mul(pow(i, N - R[m]), pow(t - i, R[m] - 1)));
}
valueType sum = 0;
for (valueType i = 1; i <= N; ++i) {
valueType S = 0;
for (valueType j = 1; j <= i; ++j) {
if ((i - j) & 1) {
Dec(S, mul(F[j], C(i, j)));
} else {
Inc(S, mul(F[j], C(i, j)));
}
}
Inc(sum, mul(S, C(U[m], i)));
}
Mul(ans, sum);
}
}
std::cout << ans << std::endl;
return 0;
}