CF1420D：
注意到任意条线段的交集如果非空的话必定是一条线段，且这条线段的左端点一定是某条线段的左端点。
很明显先将线段离散化，然后去枚举相交的线段的左端点。
我们设 \(p\) 是覆盖了某个位置的线段的数量，\(s\) 是以这个位置为左端点的线段数量。由于我们选出的这 \(k\) 条线段中至少要有一条以这个位置为左端点，所以容斥一下得到这个位置的答案为
\(\binom{p}{k}-\binom{p-s}{k}\)。
具体细节看代码。
Code：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 300005, M = 600005, mod = 998244353;
int n, k;
int fac[N], inv[N];
int l[N], r[N], _[M], tot;
int cntL[M], cntR[M];
int qpow(int x, int y) {
int res = 1;
while (y) {
if (y & 1) res = 1ll * res * x % mod;
x = 1ll * x * x % mod;
y >>= 1;
}
return res;
}
void init(int n) {
fac[0] = 1;
for (int i = 1; i <= n; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
inv[n] = qpow(fac[n], mod - 2);
for (int i = n - 1; ~i; --i) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
}
int C(int n, int m) {
if (n < m || n < 0 || m < 0) return 0;
return 1ll * fac[n] * inv[n - m] % mod * inv[m] % mod;
}
int main() {
scanf("%d%d", &n, &k), init(n);
for (int i = 1; i <= n; ++i) scanf("%d%d", &l[i], &r[i]), _[++tot] = l[i], _[++tot] = r[i];
sort(_ + 1, _ + tot + 1), tot = unique(_ + 1, _ + tot + 1) - (_ + 1);
for (int i = 1; i <= n; ++i) {
l[i] = lower_bound(_ + 1, _ + tot + 1, l[i]) - _, r[i] = lower_bound(_ + 1, _ + tot + 1, r[i]) - _;
++cntL[l[i]], ++cntR[r[i] + 1];
}
int sum = 0, ans = 0;
for (int i = 1; i <= tot; ++i) {
sum += cntL[i] - cntR[i];
ans = (ans + (C(sum, k) - C(sum - cntL[i], k) + mod) % mod) % mod;
}
printf("%d", ans);
return 0;
}
CF gym102012 G：
把序列搬到了树上。
重点在于怎么不重不漏的统计答案。
下文称顶点为一条路径的两个端点的 LCA。
注意到如果两条路径有公共点，那么其中必有一个点是某条路径的顶点
所以想到枚举每个点，计算至少有一条路径的顶点是该点的方案数。
简单说明一下，因为对于一个点 \(x\)，和一条经过它的路径 \(L\)，必有 \(L\) 的顶点不是 \(x\) 就是 \(x\) 的祖先，不可能是 \(x\) 的后代。也就是说 \(x\) 是这个选法中深度最深的顶点。而一个选法不可能有两个不同的深度最深的顶点（否则这两个顶点对应的路径就没有公共点了），所以这个对应方法是唯一的了。
具体细节看代码。
Code：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 300005, mod = 1e9 + 7;
int T;
int n, t, m, k;
int head[N], ver[N*2], nxt[N*2], cnt;
int fac[N], inv[N];
int fa[N][20], dep[N];
int num[N], a[N];
void add(int u, int v) {
ver[++cnt] = v, nxt[cnt] = head[u], head[u] = cnt;
}
int qpow(int x, int y) {
int res = 1;
while (y) {
if (y & 1) res = 1ll * res * x % mod;
x = 1ll * x * x % mod;
y >>= 1;
}
return res;
}
void init(int n) {
fac[0] = 1;
for (int i = 1; i <= n; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
inv[n] = qpow(fac[n], mod - 2);
for (int i = n - 1; ~i; --i) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
}
int C(int n, int m) {
if (n < m || n < 0 || m < 0) return 0;
return 1ll * fac[n] * inv[n - m] % mod * inv[m] % mod;
}
void dfs(int u, int Fa) {
for (int i = head[u]; i; i = nxt[i]) {
int v = ver[i];
if (v == Fa) continue;
dep[v] = dep[u] + 1, fa[v][0] = u;
for (int j = 1; j <= t; ++j)
fa[v][j] = fa[fa[v][j - 1]][j - 1];
dfs(v, u);
}
}
void dfs1(int u, int Fa) {
for (int i = head[u]; i; i = nxt[i]) {
int v = ver[i];
if (v == Fa) continue;
dfs1(v, u), a[u] += a[v];
}
}
int LCA(int x, int y) {
if (dep[x] > dep[y]) swap(x, y);
for (int i = t; ~i; --i)
if (dep[x] <= dep[fa[y][i]]) y = fa[y][i];
if (x == y) return x;
for (int i = t; ~i; --i)
if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
return fa[x][0];
}
void solve() {
scanf("%d%d%d", &n, &m, &k), t = (log(n) / log(2)) + 1;
memset(head + 1, 0, sizeof (int) * n), cnt = 0;
memset(num + 1, 0, sizeof (int) * n);
memset(a + 1, 0, sizeof (int) * n);
for (int i = 1, u, v; i < n; ++i) scanf("%d%d", &u, &v), add(u, v), add(v, u);
dep[1] = 1, dfs(1, 0);
for (int i = 1, x, y; i <= m; ++i) {
scanf("%d%d", &x, &y); int z = LCA(x, y);
++num[z]; ++a[x], ++a[y], --a[z], --a[fa[z][0]];
}
dfs1(1, 0);
int ans = 0;
for (int i = 1; i <= n; ++i) ans = (ans + (C(a[i], k) - C(a[i] - num[i], k) + mod) % mod) % mod;
printf("%d\n", ans);
}
int main() {
init(300000);
scanf("%d", &T);
while (T--) solve();
return 0;
}