2018冬令营模拟测试赛（二）
[Problem A]最小生成树
试题描述
输入
见“试题描述”
输出
见“试题描述”
输入示例
见“试题描述”
输出示例
见“试题描述”
数据规模及约定
见“试题描述”
题解
这是一道坑了我的结论题（考场上推了半天结果得零分，最气的是发现再特判一下就 A 了！！！）
我们不妨让最终的最小生成树长成一条链，然后这条链的边权从左到右依次单调不降。
那么为了构建出 (m) 条边的无向图，我们可以贪心地再左边加边，即 (t) 从 (1) 开始计，每次将前 (t) 个点加边加成完全图，然后 (t) 加 (1)，直到 (t=n)（注意最开始要先把所有节点按顺序串成一条链）。
那么一个安排边权的贪心策略来了：将前 (n-1) 个点之间连接的所有边的边权安排成 (1)，然后剩下的边（即和第 (n) 个点连的所有边）边权安排成 (n-2)。
这样显然不是最优的，但这给我们提供了一个很好的思路，接下来的算法就是在上面这个建图基础上的。
我们假设一开始所有边权都是 (0)，那么有两种选择：一种是将所有边权 (+1)，一种是将和最后一个点有关的所有边权 (+1)；目标是让生成树的所有边之和 (=s)，那么这两种选择就相当于两种物品，背包的容量为 (s)，第一种体积为 (1)，代价为 (x)（即和最后一个点有关的边数）（注意这里用代价是因为我们要最小化这个值，而“价值”是一个褒义词故不用它），第二种物品物品体积为 (n-1)，代价为 (m)。那么假设我们选择 (a) 个第一种物品，(b) 个第二种物品，令 (N = n-1)，则有 (a + bN = s)，要最小化 (ax + bm) 的值；把 (a) 用 (b) 表示得到最小化 ((s-bN)x + bm = sx - Nxb + mb = (m-Nx)b + sx)，当 (m-Nx ge 0) 时 (b = 0) 即可，否则让 (b) 取到最大，也即 (lfloor frac{s}{N} floor)。于是答案可以 (O(1)) 得到。
当然不要忘掉一个我考场上漏掉的特殊情况。容易发现我们上面列出的两个并不是全部可选的物品，因为我们还可以选择后任意多个点之间的所有边 (+1)——只需要保证每时每刻那条链的边权单调不降就行。这个问题的解决方案是所有边取平均值 (frac{s}{m})（前面的边下取整，后面的边上取整）就好了。至于为啥，我不知道。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define rep(i, s, t) for(int i = (s); i <= (t); i++)
#define dwn(i, s, t) for(int i = (s); i >= (t); i--)
#define LL long long
LL read() {
LL x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
LL calc(int x) { return (LL)x * (x - 1) >> 1; }
LL solve(int n, LL m, LL s, LL restm) {
if(restm <= calc(n - 1)) return min(restm, calc(n - 1)) + s + 1;
n--;
restm -= calc(n); restm++;
// printf("(1, %lld)
(%d, %lld)
s = %lld
", restm, n, m, s);
if(m - restm * n >= 0) return s * restm + m;
LL a = s, b = 0;
LL k = a / n; b += k;
return s * restm + b * (m - restm * n) + m;
}
LL avg(int n, LL m, LL s) {
LL lo = s / (n - 1), hi = (s + n - 2) / (n - 1);
if(lo == hi) return m * lo;
n--;
LL restm = m - 1 - calc(n) + 1, sma = lo * n + n - s, pre = min(calc(sma + 1) - sma + 1, m - n + 1) + sma - 1, suf = m - pre;
return pre * lo + suf * hi;
}
int main() {
int T = read();
while(T--) {
int n = read();
LL m = read(), s = read() - n + 1, restm = m - 1;
printf("%lld
", min(solve(n, m, s, restm), avg(n, m, s + n - 1)));
}
return 0;
}
[Problem B]没有上司的舞会
试题描述
输入
见“试题描述”
输出
见“试题描述”
输入示例
见“试题描述”
输出示例
见“试题描述”
数据规模及约定
见“试题描述”
题解
用数据结构维护 dp 信息。一句话解决问题。
好吧还是讲讲，我们考虑用 LCT 维护动态加点的操作，每个节点 (i) 记录 (f_0(i)) 和 (f_1(i)) 分别表示不选和选择它自己最多能从它以及它所有 LCT 上“非访问边”中选择多少个节点。(access) 操作的时候直接对 (f_0) 和 (f_1) 进行加减操作实现加入一个儿子和删掉一个儿子。此外在 splay 中搞一个 (F_{a,b}(i))（(a, b) 都是 (0) 或 (1) 的整数）表示对于 splay 中的子树 (i)，首、尾选不选的 dp 值，这样就可以方便地合并了。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define rep(i, s, t) for(int i = (s); i <= (t); i++)
#define dwn(i, s, t) for(int i = (s); i >= (t); i--)
int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
#define maxn 300010
#define oo 2147483647
struct LCT {
int f[maxn][2], F[maxn][2][2];
int fa[maxn], ch[maxn][2];
bool isrt(int u) { return ch[fa[u]][0] != u && ch[fa[u]][1] != u; }
void merge(int to, int l, int r) {
int nf[2][2];
nf[0][0] = max(max(F[l][0][1] >= 0 && F[r][0][0] >= 0 ? F[l][0][1] + F[r][0][0] : -1, F[l][0][0] >= 0 && F[r][1][0] >= 0 ? F[l][0][0] + F[r][1][0] : -1), F[l][0][0] >= 0 && F[r][0][0] >= 0 ? F[l][0][0] + F[r][0][0] : -1);
nf[0][1] = max(max(F[l][0][1] >= 0 && F[r][0][1] >= 0 ? F[l][0][1] + F[r][0][1] : -1, F[l][0][0] >= 0 && F[r][1][1] >= 0 ? F[l][0][0] + F[r][1][1] : -1), F[l][0][0] >= 0 && F[r][0][1] >= 0 ? F[l][0][0] + F[r][0][1] : -1);
nf[1][0] = max(max(F[l][1][1] >= 0 && F[r][0][0] >= 0 ? F[l][1][1] + F[r][0][0] : -1, F[l][1][0] >= 0 && F[r][1][0] >= 0 ? F[l][1][0] + F[r][1][0] : -1), F[l][1][0] >= 0 && F[r][0][0] >= 0 ? F[l][1][0] + F[r][0][0] : -1);
nf[1][1] = max(max(F[l][1][1] >= 0 && F[r][0][1] >= 0 ? F[l][1][1] + F[r][0][1] : -1, F[l][1][0] >= 0 && F[r][1][1] >= 0 ? F[l][1][0] + F[r][1][1] : -1), F[l][1][0] >= 0 && F[r][0][1] >= 0 ? F[l][1][0] + F[r][0][1] : -1);
memcpy(F[to], nf, sizeof(nf));
return ;
}
void maintain(int u) {
F[u][0][0] = f[u][0]; F[u][1][1] = f[u][1];
F[u][0][1] = F[u][1][0] = -1;
if(ch[u][0]) merge(u, ch[u][0], u);
if(ch[u][1]) merge(u, u, ch[u][1]);
return ;
}
void rotate(int u) {
int y = fa[u], z = fa[y], l = 0, r = 1;
if(!isrt(y)) ch[z][ch[z][1]==y] = u;
if(ch[y][1] == u) swap(l, r);
fa[u] = z; fa[y] = u; fa[ch[u][r]] = y;
ch[y][l] = ch[u][r]; ch[u][r] = y;
return maintain(y);
}
void splay(int u) {
while(!isrt(u)) {
int y = fa[u], z = fa[y];
if(!isrt(y)) {
if(ch[y][0] == u ^ ch[z][0] == y) rotate(u);
else rotate(y);
}
rotate(u);
}
return maintain(u);
}
void access(int u) {
splay(u);
int fson[2];
if(ch[u][1]) {
fson[0] = max(F[ch[u][1]][0][0], F[ch[u][1]][0][1]);
fson[1] = max(F[ch[u][1]][1][0], F[ch[u][1]][1][1]);
f[u][0] += max(fson[0], fson[1]); f[u][1] += fson[0];
}
ch[u][1] = 0;
maintain(u);
while(fa[u]) {
splay(fa[u]);
if(ch[fa[u]][1]) {
fson[0] = max(F[ch[fa[u]][1]][0][0], F[ch[fa[u]][1]][0][1]);
fson[1] = max(F[ch[fa[u]][1]][1][0], F[ch[fa[u]][1]][1][1]);
f[fa[u]][0] += max(fson[0], fson[1]); f[fa[u]][1] += fson[0];
}
fson[0] = max(F[u][0][0], F[u][0][1]);
fson[1] = max(F[u][1][0], F[u][1][1]);
f[fa[u]][0] -= max(fson[0], fson[1]); f[fa[u]][1] -= fson[0];
ch[fa[u]][1] = u;
maintain(fa[u]);
splay(u);
}
return ;
}
void link(int a, int b) { // b should be a leaf
f[b][0] = 0; f[b][1] = 1; maintain(b);
access(a); fa[b] = a; ch[a][1] = b;
maintain(a);
return ;
}
} sol;
int main() {
int n = read() + 1, type = read(), lstans = 0;
// printf("%d %d
", n, type);
sol.f[1][0] = 0; sol.f[1][1] = 1; sol.maintain(1);
rep(i, 2, n) {
int fa = (read() ^ type * lstans) + 1;
sol.link(fa, i);
sol.access(1);
printf("%d
", lstans = max(sol.f[1][0], sol.f[1][1]));
}
return 0;
}
[Problem C]排列问题
试题描述
输入
见“试题描述”
输出
见“试题描述”
输入示例
见“试题描述”
输出示例
见“试题描述”
数据规模及约定
见“试题描述”
题解
我去这题有点毒瘤。
首先你需要想到容斥 dp，其它 dp 方式都无法搞定正解。
令 (f(i, j)) 表示对于前 (i) 种颜色，序列强行分了 (j) 段的方案数，那么转移就简单了，枚举最后一种颜色分多少段即可，然后推式子搞搞成为卷积的形式：(f(i, j) = sum_{k=1}^{mathrm{min}{ a_i, j }} { f(i-1, j-k) cdot C_j^k cdot C_{a_i-1}^{k-1} } = sum_{k=1}^{mathrm{min}{ a_i, j }} { f(i-1, j - k) cdot frac{j!}{k!(j-k)!} cdot frac{(a_i-1)!}{(k-1)!(a_i-k)!} } Rightarrow frac{f(i, j)}{j!} = sum_{k=1}^{mathrm{min}{ a_i, j }} { frac{f(i-1, j-k)}{(j-k)!} cdot frac{(a_i-1)!}{k!(k-1)!(a_i-k)!} })
于是令 (A_i(x) = sum_{k=1}^{a_i} { frac{(a_i - 1)!}{k!(k-1)!(a_i-k)!} cdot x^k })，(F_0(x) = 1)，那么得到的 (F_n(x) = F_0(x) cdot prod_{i=1}^n {A_i(x)}) 所有系数就是最后的 (f(n, i) cdot i!)，由于乘法有结合律，可以先分治 FFT 求出后面那一坨 (A_i(x)) 乘起来的多项式，然后再用 (F_0(x)) 去乘就好了。
然后我们还要容斥，显然上面会重复计算，上面的 dp 会对球序列多分几段，所以要依次减掉多分一段的，加上多分两段的，减去多分三段的……形式化地：令 (forall i in [1, m], g(i) = f(n, i))，最终分 (i) 段的方案数为 (Ans_i)，则 (Ans_i = sum_{j=1}^i { (-1)^{i-j} cdot g(j) cdot C_{m-j}^{i-j} } Rightarrow Ans_i cdot (m-i)! = sum_{j=1}^i {g(j) cdot (m-j)! cdot frac{(-1)^{i-j}}{(i-j)!} })，还是卷积！再 FFT 一下就好了。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <vector>
using namespace std;
#define rep(i, s, t) for(int i = (s); i <= (t); i++)
#define dwn(i, s, t) for(int i = (s); i >= (t); i--)
int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
#define maxn 524288
#define MOD 998244353
#define Groot 3
#define LL long long
int rev[maxn];
int Pow(int a, int b) {
int ans = 1, t = a;
while(b) {
if(b & 1) ans = (LL)ans * t % MOD;
t = (LL)t * t % MOD; b >>= 1;
}
return ans;
}
void FFT(vector <int> &A, int len, int tp) {
int n = 1 << len;
rep(i, 0, n - 1) if(i < rev[i]) swap(A[i], A[rev[i]]);
rep(i, 1, len) {
int wn = Pow(Groot, MOD - 1 >> i);
if(tp < 0) wn = Pow(wn, MOD - 2);
for(int j = 0; j < n; j += 1 << i) {
int w = 1;
rep(k, 0, (1 << i >> 1) - 1) {
int al = A[j+k], ar = (LL)w * A[j+k+(1<<i>>1)] % MOD;
A[j+k] = (al + ar) % MOD;
A[j+k+(1<<i>>1)] = (al - ar + MOD) % MOD;
w = (LL)w * wn % MOD;
}
}
}
if(tp < 0) rep(i, 0, n - 1) A[i] = (LL)A[i] * Pow(n, MOD - 2) % MOD;
return ;
}
void Mul(vector <int> &A, vector <int> &B) {
int n = A.size() - 1, N = 1, len = 0;
while(N <= n) N <<= 1, len++;
rep(i, 1, N - 1) rev[i] = (rev[i>>1] >> 1) | ((i & 1) << len - 1);
FFT(A, len, 1); FFT(B, len, 1);
rep(i, 0, N - 1) A[i] = (LL)A[i] * B[i] % MOD;
FFT(A, len, -1);
return ;
}
int m, a[maxn], fac[maxn], ifac[maxn];
vector <int> GetTrans(int l, int r) {
if(l == r) {
vector <int> A(a[l] + 1);
A[0] = 0;
rep(i, 1, a[r]) A[i] = (LL)fac[a[l]-1] * ifac[i] % MOD * ifac[i-1] % MOD * ifac[a[r]-i] % MOD;
return A;
}
int mid = l + r >> 1;
vector <int> A = GetTrans(l, mid), B = GetTrans(mid + 1, r);
int asiz = A.size(), bsiz = B.size(), siz = asiz + bsiz, need = 1;
while(need <= siz - 2) need <<= 1;
A.resize(need); B.resize(need);
rep(i, asiz, need - 1) A[i] = 0; rep(i, bsiz, need - 1) B[i] = 0;
Mul(A, B);
vector <int> E(siz-1);
rep(i, 0, siz - 2) E[i] = A[i];
return E;
}
int main() {
int n = read();
rep(i, 1, n) a[i] = read(), m += a[i];
fac[0] = ifac[0] = 1;
rep(i, 1, m) fac[i] = (LL)fac[i-1] * i % MOD, ifac[i] = (LL)ifac[i-1] * Pow(i, MOD - 2) % MOD;
vector <int> A = GetTrans(1, n), F;
int siz = A.size(), need = 1;
while(need <= siz - 1) need <<= 1;
F.resize(need); F[0] = 1; rep(i, 1, need - 1) F[i] = 0;
A.resize(need); rep(i, siz, need - 1) A[i] = 0;
Mul(F, A);
rep(i, 0, siz - 1) F[i] = (LL)F[i] * fac[i] % MOD;
// printf("F[0~%d]: ", m); rep(i, 0, m) printf("%d%c", F[i], i < m ? ' ' : '
');
need = 1;
while(need <= (m << 1)) need <<= 1;
vector <int> G(need), T(need);
G[0] = 0; rep(i, 1, m) G[i] = (LL)F[i] * fac[m-i] % MOD; rep(i, m + 1, need - 1) G[i] = 0;
// rep(i, 0, m) printf("%d%c", G[i], i < m ? ' ' : '
');
rep(i, 0, m) T[i] = (i & 1) ? MOD - ifac[i] : ifac[i]; rep(i, m + 1, need - 1) T[i] = 0;
Mul(G, T);
rep(i, 0, m) G[i] = (LL)G[i] * ifac[m-i] % MOD;
int q = read();
while(q--) {
int k = read();
printf("%d
", G[m-k]);
}
return 0;
}