D
很显然可以用一个背包算出来凑齐i个位置的方案
然后总的答案就是\(dp_{n / 2}\)
然后需要扣掉不符合条件的就是把选出来的数的贡献剪掉的贡献
然后注意因为是多重集合的排列，所以需要乘上\(\frac{fac[n / 2]}{fac[cnt_a]fac[cnt_b].....}\ast \frac{fac[n / 2]}{fac[cnt_c]fac[cnt_d].....}\)
然后显然下面是所有个数的阶乘积，然后没了
#include<bits/stdc++.h>using namespace std;const int N = 1e5 + 10;
const int M = 60;
const int Mod = 1e9 + 7;int add(int a, int b) {return (a += b) >= Mod ? a - Mod : a;
}int sub(int a, int b) {return (a -= b) < 0 ? a + Mod : a;
}int mul(int a, int b) {return 1ll * a * b % Mod;
}int fast_pow(int a, int b) {int res = 1;for (; b; b >>= 1, a = mul(a, a))if (b & 1) res = mul(res, a);return res;
}int inv[N], fac[N];
int ans[M][M] = {0}, cnt[M];
int n, q, f[N];
char s[N];int id(char c) {if ('a' <= c && c <= 'z') {return c - 'a' + 27;} else {return c - 'A' + 1;}
}int C(int a, int b) {return a >= b ? mul(fac[a], mul(inv[b], inv[a - b])) : 0;
}void modify(int id, int typ) {if (typ) {for (int i = n / 2; i >= cnt[id]; i--)f[i] = add(f[i], f[i - cnt[id]]);} else {for (int i = cnt[id]; i <= n / 2; i++)f[i] = sub(f[i], f[i - cnt[id]]);}
}int main() {
#ifdef dream_makerfreopen("input.txt", "r", stdin);
#endifscanf("%s", s + 1);n = strlen(s + 1);inv[0] = fac[0] = 1;for (int i = 1; i <= n; i++)fac[i] = mul(fac[i - 1], i);inv[n] = fast_pow(fac[n], Mod - 2);for (int i = n - 1; i >= 1; i--)inv[i] = mul(inv[i + 1], i + 1);for (int i = 1; i <= n; i++)cnt[id(s[i])]++;f[0] = 1;for (int i = 1; i <= 52; i++)if (cnt[i]) modify(i, 1);for (int i = 1; i <= 52; i++) if (cnt[i] && cnt[i] <= n / 2) {modify(i, 0);ans[i][i] = f[n / 2 - cnt[i]];modify(i, 1);}for (int i = 1; i <= 52; i++) if (cnt[i]) {modify(i, 0);for (int j = 1; j <= 52; j++) if (i != j && cnt[j] && cnt[j] + cnt[i] <= n / 2) {modify(j, 0);ans[i][j] = f[n / 2 - cnt[i] - cnt[j]];modify(j, 1);}modify(i, 1);}int bas = mul(fac[n / 2], fac[n / 2]);for (int i = 1; i <= 52; i++)bas = mul(bas, inv[cnt[i]]);for (int i = 1; i <= 52; i++)for (int j = 1; j <= 52; j++)ans[i][j] = mul(ans[i][j], mul(2, bas));scanf("%d", &q);while (q--) {int x, y;scanf("%d %d", &x, &y);printf("%d\n", ans[id(s[x])][id(s[y])]);}return 0;
}E
首先如果在虚树上考虑，我们按照深度进行dp
发现\(f_{i,j}\)表示i个点分成j个集合的方案数有转移：
\(f_{i,j}=f_{i - 1,j}\ast (j - h_i)+f_{i - 1,j - 1}\)
其中h是一个节点的父亲个数
然后h咋算呢？
就是可以用i到1的节点个数加上r到1的节点个数减去lca到1的节点个数的两倍
然后以1为根的时候每一个点在dfs序上的贡献都是一个区间，用bit算一下就可以了
然后就直接dp就可以了
因为有多次询问，所以注意边界就可以了
#include<bits/stdc++.h>using namespace std;const int N = 1e5 + 10;
const int M = 5e2 + 10;
const int LOG = 20;
const int Mod = 1e9 + 7;int add(int a, int b) {return (a += b) >= Mod ? a - Mod : a;
}int mul(int a, int b) {return 1ll * a * b % Mod;
}int n, q, f[N][M];
vector<int> g[N];
int dep[N], fa[N][LOG];
int bg[N], ed[N], ind = 0;void dfs(int u, int father) {dep[u] = dep[father] + 1;bg[u] = ++ind;fa[u][0] = father;for (int i = 1; i < 18; i++)fa[u][i] = fa[fa[u][i - 1]][i - 1];for (auto v : g[u])if (v != father)dfs(v, u);ed[u] = ind;
}int lca(int x, int y) {if (dep[x] < dep[y]) swap(x, y);int delta = dep[x] - dep[y];for (int i = 0; i < 18; i++)if ((delta >> i) & 1)x = fa[x][i];if (x == y) return x;for (int k = 17; k >= 0; k--) {if (fa[x][k] != fa[y][k]) {x = fa[x][k];y = fa[y][k];}}return fa[x][0];
}int bit[N];void modify(int t, int vl) {for (; t <= n; t += t & (-t))bit[t] += vl;
}int query(int t) {int res = 0;for (; t; t -= t & (-t))res += bit[t];return res;
}void solve() {static int h[N], p[N], k, m, r;static bool mark[N];scanf("%d %d %d", &k, &m, &r);for (int i = 1; i <= k; i++)scanf("%d", &p[i]);for (int i = 1; i <= k; i++) {modify(bg[p[i]], 1);modify(ed[p[i]] + 1, -1);mark[p[i]] = 1;}int hrt = query(bg[r]);for (int i = 1; i <= k; i++) {int g = lca(p[i], r);h[i] = query(bg[p[i]]) + hrt - 2 * query(bg[g]) + mark[g] - 1; }for (int i = 1; i <= k; i++) {modify(bg[p[i]], -1);modify(ed[p[i]] + 1, 1);mark[p[i]] = 0;}sort(h + 1, h + k + 1); // 相当于在虚树上按照深度进行dpf[0][0] = 1;for (int i = 1; i <= k; i++) {for (int j = 1; j < h[i]; j++)f[i][j] = 0;for (int j = h[i]; j <= min(i, m); j++)f[i][j] = add(mul(j - h[i], f[i - 1][j]), f[i - 1][j - 1]);}int res = 0;for (int i = 1; i <= m; i++)res = add(res, f[k][i]);printf("%d\n", res);
}int main() {
#ifdef dream_makerfreopen("input.txt", "r", stdin);
#endifscanf("%d %d", &n, &q);for (int i = 1; i < n; i++) {int u, v;scanf("%d %d", &u, &v);g[u].push_back(v);g[v].push_back(u);}dfs(1, 0);while (q--)solve();return 0;
}
