260302 模拟赛

T1

给定一个长度为 \(n\)，值在 \([1,V]\) 内均匀独立随机生成（\(1\le V\le 10^{12}\)）的序列 \(a\)，然后把一些宽度为 \(1\)，高度为 \(a_i\) 的矩形按顺序挨着放在一起，底边紧贴 \(x\) 轴，形成一个直方图。

你需要在直方图内部放置 \(k\) 个互不重叠的矩形，底边也要平行于 \(x\) 轴。你要对 \(k\in [1,n]\) 求出矩形面积和的最大值。

\(n\le 1000,~\sum n^2\le 10^7\)

考虑在笛卡尔树上 dp，设计状态 \(f_{u,i}\) 表示区间 \(u\) 里面放了 \(i\) 个矩形。但是注意到大区间可能在小区间的下面放一个大矩形，因此小区间还要记录 \(d\) 表示最低不能放在 \(d\) 下面。

注意有用的 \(d\) 也只有 \(dep\) 个。我们在大区间处把所有小区间卷到一起，然后尝试放置一个大矩形。卷积的复杂度是 \(O(\sum sz^2)\) 的（任意两个点产生 \(dep[lca]\) 的贡献），这玩意差不多是 \(O(n^2)\) 级别的，所以可以通过。

代码

#include<iostream>
using namespace std;
typedef long long ll;
const int N = 1010;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int T, n;
ll a[N], f[50][50][N]; int dep[N];

ll sta[50]; int top;
void solve(int l, int r) {
    for(int i = 0; i <= top; i++) f[top][i][0] = 0;
    if(l > r) return;
    if(l == r) {
        for(int i = 0; i <= top; i++) f[top][i][1] = a[l] - sta[i];
        return;
    }
    ll mn = INF;
    for(int i = l; i <= r; i++) mn = min(mn, a[i]);
    sta[++top] = mn;
    int cur = 0;
    for(int i = l, pre = l - 1; i <= r + 1; i++) {
        if(i == r + 1 || a[i] == mn) {
            solve(pre + 1, i - 1);
            int sz = i - pre; pre = i;
            for(int d = 0; d <= top; d++) {
                for(int j = cur + sz; j >= 0; j--) {
                    ll res = 0;
                    for(int k = max(j - cur, 0); k <= j && k <= sz; k++) {
                        if(k < sz) res = max(res, f[top - 1][d][j - k] + f[top][d][k]);
                        if(k && i != r + 1) res = max(res, f[top - 1][d][j - k] + f[top][d][k - 1] + (sta[top] - sta[d]));
                    }
                    f[top - 1][d][j] = res;
                }
            }
            cur += sz;
        }
    }
    for(int d1 = 0; d1 < top; d1++) {
        for(int i = 1; i <= r - l + 1; i++) {
            f[top - 1][d1][i] = max(f[top - 1][d1][i], f[top - 1][top][i - 1] + (r - l + 1) * (sta[top] - sta[d1]));
        }
    }
    top--;
}

int main() {

    freopen("histo.in", "r", stdin);
    freopen("histo.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> T;
    while(T--) {
        cin >> n;
        for(int i = 1; i <= n; i++) cin >> a[i];
        solve(1, n);
        for(int i = 1; i <= n; i++) cout << f[0][0][i] << ' ';
        cout << '\n'; 
    }

    return 0;
}

T2

有一个 \(n\) 个点的图，你需要按照 \(1\sim n\) 的顺序往里面一个一个加点，初始为空。加入第 \(i\) 个点时，你会从 \(i\) 向一些以前的节点连边。设加入第 \(i\) 个节点之后的边双连通分量数量为 \(c_i\)，那么这个图（加边方案）的权值为 \(\prod_{i=1}^{n}w[c_{i-1}-c_i+1]\)，其中 \(c_0=0\)。要求 \(c_n=1\)。给定 \(w[0\sim n-1]\)，问所有图的权值和。

\(n\le 200\)

为了统一下文和我草稿的字母，令 \(nn\) 表示 \(n\)，\(n\) 表示题面中的 \(i\)。

注意到，两个弱连通块在合并之前是相互独立的，也就是说合并时可以直接将它们的权值相乘（当然还有二项式系数）。这启发我们考察加入第 \(n\) 个点时被合并的一些连通块。又注意到割边其实不会影响当前的 \(c\)，所以我们先删掉所有与 \(n\) 相连的割边，只考察 \(n\) 所在的 bcc。

这样就会产生一些非常好的结构：插入 \(n\) 时加入一些 bcc 之间的割边，然后把这些 bcc 和 \(n\) 都合并成一个 bcc，期间其它的点都可以不用管。

于是考虑 dp，设 \(f_n\) 表示 \(n\) 个点的答案，考虑什么时候能合并成一个 bcc，这需要原来边双树的叶子都和 \(n\) 有边相连，孤立 bcc 需要和 \(n\) 有两条边相连。考虑容斥，钦定一些 bcc 为叶子并且不与 \(n\) 相连。为了方便后续计算，我们钦定弱连通性必须满足。没有被钦定成叶子的 bcc 构成一个边双森林，由于弱连通性的限制，每个钦定的叶子都需要有恰好一条边和边双森林中的点相连。

于是我们尝试转移，\(g_{n,k},~h_{n,k},~s_{n,k}\) 的定义由下式给出：

\[ \begin{align*} g_{0,0}&=1\\ g_{n,k}&=\sum_{i=k-1}^{n-1}g_{i,k-1}f_{n-i}\binom{n-1}{i}(n-i)\\ h_{n,k}&=n^{k-2}g_{n,k}\\ s_{0,0}&=1\\ s_{n,k}&=\sum_{i=0}^{n-1}\sum_{j=0}^{\min(i,k)}s_{i,j}h_{n-i,k-j}\binom{n-1}{i}(2^{n-i}-1) \end{align*} \]

显然 \(h\) 的含义是边双树的权值和，\(s\) 的含义是边双森林的权值和，再从每个连通块中选择一个非空点集（向 \(n\) 连边）。那么可以写出转移式：

\[ f_{n}=\sum_{i=0}^{n-1}\sum_{k_1=0}^{i}g_{i,k_1}(-1)^{k_1}(n-i-1)^{k_1}\sum_{k_2=0}^{n-i-1}s_{n-i-1,k_2}\binom{n-1}{i}w_{k_1+k_2} \]

但是和孤立 bcc 只有一条边相连的情况也会被算进去。此时继续考虑容斥，先拆分上式的贡献：

\[ f_{n,k_1+k_2}\gets \sum_{i=0}^{n-1}g_{i,k_1}(-1)^{k_1}(n-i-1)^{k_1}s_{n-i-1,k_2}\binom{n-1}{i} \]

然后，钦定一些 bcc 是孤立的，它们的方案数显然是 \(g\)，剩下的东西可以用以前的 \(f\)，于是有如下修正：

\[ f'_{n,k_1+k_2}\gets~~-\sum_{i=k_1}^{n-1}g_{i,k_1}f_{n-i,k_2}\binom{n-1}{i} \]

最终

\[ f_n=\sum_{k=1}^{n-1}f_{n,k}w_k \]

时间复杂度 \(O(n^4)\)，可以通过。并且显然可以通过 NTT 优化到 \(O(n^3\log n)\)。

闲话：其实上面的 \(g\) 和 \(h\) 显然就是在做 \(\exp\)，\(s\) 是二元 EGF 的 \(\exp\)。但显然这么简单的式子用不到 EGF 形式。

还有 \(n^4\) 过 \(200\) 是认真的吗？场上推出了完整的式子（除了那个修正的地方有点问题），因为犯唐所以没调出来。

代码

#include<iostream>
using namespace std;
typedef long long ll;
const int N = 205;
const int MOD = 1e9 + 7;

inline void add(int &a, int b) { a += b; (a >= MOD) && (a -= MOD); }
inline int qpow(int a, int b) {
    int res = 1;
    while(b) {
        if(b & 1) res = (ll)res * a % MOD;
        a = (ll)a * a % MOD;
        b >>= 1;
    }
    return res;
}

int nn;
int w[N];
int f[N], f1[N][N], g[N][N], h[N][N], s[N][N];
int inv[N], fac[N], ifac[N], pw2[N];

inline int C(int a, int b) { return (ll)fac[a] * ifac[a - b] % MOD * ifac[b] % MOD; }

int main() {

    freopen("count.in", "r", stdin);
    freopen("count.out", "w", stdout);

    inv[1] = fac[0] = ifac[0] = pw2[0] = 1;
    for(int i = 2; i < N; i++) inv[i] = MOD - (ll)inv[MOD % i] * (MOD / i) % MOD;
    for(int i = 1; i < N; i++) fac[i] = (ll)fac[i - 1] * i % MOD;
    for(int i = 1; i < N; i++) ifac[i] = (ll)ifac[i - 1] * inv[i] % MOD;
    for(int i = 1; i < N; i++) pw2[i] = pw2[i - 1] * 2 % MOD;

    cin >> nn;
    for(int i = 0; i < nn; i++) cin >> w[i];

    f1[1][0] = 1;
    f[0] = g[0][0] = s[0][0] = h[0][0] = 1;
    f[1] = g[1][1] = h[1][1] = s[1][1] = w[0];
    for(int n = 2; n <= nn; n++) {
        for(int i = 0; i <= n - 1; i++) {
            for(int k1 = 0; k1 <= i; k1++) {
                int tmp;
                if(k1 & 1) tmp = MOD - (ll)g[i][k1] * qpow(n - i - 1, k1) % MOD;
                else tmp = (ll)g[i][k1] * qpow(n - i - 1, k1) % MOD;
                for(int k2 = 0; k2 <= n - 1 - i; k2++) {
                    add(f1[n][k1 + k2], (ll)tmp * s[n - 1 - i][k2] % MOD * C(n - 1, i) % MOD);
                }
            }
        }
        for(int i = 1; i <= n - 1; i++)
            for(int k1 = 1; k1 <= i; k1++)
                for(int k2 = 0; k2 <= n - i - 1; k2++)
                    add(f1[n][k1 + k2], MOD - (ll)f1[n - i][k2] * g[i][k1] % MOD * C(n - 1, i) % MOD);
        for(int i = 0; i < n; i++) add(f[n], (ll)f1[n][i] * w[i] % MOD);
        g[n][1] = h[n][1] = s[n][1] = f[n];
        g[n][1] = (ll)g[n][1] * n % MOD;
        s[n][1] = (ll)s[n][1] * (pw2[n] - 1) % MOD;
        for(int k = 2; k <= n; k++) {
            for(int i = k - 1; i <= n - 1; i++)
                add(g[n][k], (ll)g[i][k - 1] * f[n - i] % MOD * C(n - 1, i) % MOD * (n - i) % MOD);
            h[n][k] = (ll)g[n][k] * qpow(n, k - 2) % MOD;
            for(int i = 0; i <= n - 1; i++)
                for(int j = 0; j <= min(i, k); j++)
                    add(s[n][k], (ll)s[i][j] * h[n - i][k - j] % MOD * C(n - 1, i) % MOD * (pw2[n - i] - 1) % MOD);
        }
    }

    for(int i = 1; i <= nn; i++) cout << f[i] << '\n';

    return 0;
}

T3

没听懂。但是第一步转化是奇数位减偶数位等于 \(0\)，证明赛时的直觉是对的。