T1 分段 DP

Description

给定长度为 $n$ 的单调不减序列 $\{a\}$ 。定义一个区间的权值为区间长度与区间最小值的乘积。求将该序列分成 $k\in [1,n]$ 段的权值和的最大值。
$1\leq n\leq 2\times 10^5,1\leq a_i\leq 8\times 10^3$

Solution

转移方程比较显然。设 f[i][j] 表示分成了 $i$ 段，最后一段的末尾为 $j$ 的最大乘积。则有

$f[i][j]=\min_{k=0}^{j-1} \{f[i-1][j]+a[k+1]\times (j-k)\}$

然后斜率优化可以做到 $\mathcal{O}(n^2)$ 。
实际上由于值域只有 $8000$ ，且数列保证单调，我们可以把相同的数合并，这并不会影响答案。
所以总复杂度 $\mathcal{O}(V^2)$ 。

Code

const int N=2e5+5;
using namespace std;
int n, m, q[N], buc[N];
int a[N], b[N], f[N], X[N], Y[N];
inline bool cmp (ll a, ll b, ll c, ll d){
    return a * d <= c * b;
}
int main(){

    r(n);
    for(int i = 1, x; i <= n; ++ i)
        r(x), ++ buc[x];
    for(int i = 1; i <= N; ++ i){
        buc[i] += buc[i - 1];
        if(buc[i] > buc[i - 1])
            ++ m, a[m] = i, b[m] = buc[i];
    }
    for(int i = 1; i <= m; ++ i)
        f[i] = 1ll * a[1] * b[i];
    w(f[m]);
    X[0] = a[1];
    for(register int i = 2; i <= m; ++ i){
        for(register int j = 1; j <= m; ++ j)
            Y[j] = - f[j] + 1ll * a[j + 1] * b[j], X[j] = a[j + 1]; 
        int l = 1, r = 1;
        for(register int j = 1; j <= m; ++ j){
            while (l < r && cmp(Y[q[l + 1]] - Y[q[l]], X[q[l + 1]] - X[q[l]], b[j], 1) ) ++l;
            int k = q[l]; f[j] = 1ll * a[k + 1] * b[j] - Y[k];
            while (l < r && cmp(Y[j] - Y[q[r]], X[j] - X[q[r]], Y[q[r]] - Y[q[r - 1]], X[q[r]] - X[q[r - 1]]) ) --r;
            q[++ r] = j;
        }
        w(f[m]);
    }
    for(int i = m + 1; i <= n; ++ i)
        w(f[m]);
    return 0; 
}

T2 虚树 DP

Description

对于一颗有根树，定义一个点集 $S$ 是虚树当且仅当 $S$ 内任意两点的最近公共祖先都属于 $S$ 。特别地，单个点构成的 $S$ 也算虚树，但是空集不构成虚树。
一个点集的权值定义为其包含的点的权值的乘积。
给定一颗 $n$ 个点的带点权无根树，$q$ 次询问，每次询问给出 $u\ x$ 表示：如果以 $u$ 作为树根，所有大小为 $x$ 的虚树的权值的和是多少？特别地，如果 $x=0$ ，则询问表示：如果以 $u$ 作为树根，所有虚树的权值的和是多少？
$1\leq n\leq 3\times 10^3,1\leq q\leq 10^5$ ，树的直径不超过 $10$ 。

Solution

暴力做法就是对于每个询问做一遍树形 DP 。设 f[p][i] 表示 $p$ 子树内大小为 $i$ 的虚树的权值和（ $p$ 点必选）；g[p][i] 表示 $p$ 子树内大小为 $i$ 的虚树权值和（ $p$ 点不必选 ）则

$f[p][k]=\sum_{i+j=k}f[u][i]\times g[p][j]\\ g[p][k]=\sum g[u][k]+\sum_{i+j=k} f[u][i]\times g[p][j]$

背包问题通过卡上下界复杂度可以做到 $\mathcal{O}(qn^2)$ 。
实际上正解就是先通过换根 DP 预处理出所有的 g[p][] 。这涉及到了背包的合并和分裂。
考虑所谓背包实际上可以抽象成多项式，设 $F_p(x)$ 为 g[p][] 的 OGF 。则：

$F_p(x)=v_px\prod_{p\rightarrow u}(1+F_u(x))+\sum_{p\rightarrow u}F_u(x)$

然后背包的合并和分裂分别视作卷积和除法。可以上多项式科技做到 $\mathcal{O}(n^2\log n)$ 。
实际上没有必要，注意到题目中的最后一个条件：直径不超过 $10$ 。实际上，本题的复杂度应该这个考虑：在换根 DP 时，我们需要用一个长度为 $n$ 的多项式除一个长度为 $\text{sz}_v$ 的多项式。每个点只会在父节点处做一次除法，那么复杂度为

$T(n)=\sum_u \mathcal{O}(n\times \text{sz}_u)=\mathcal{O} (n\sum_u \text{sz}_u) = \mathcal{O}(n^2h)$

其中 $h$ 是树高。树高不会超过直径。

Code

const int N = 3e3 + 5, mod = 1e9 + 7;
using namespace std;
template<typename tp>inline void Plus(tp &a,tp b){a = (a + b >= mod)? a + b - mod : a + b;}
inline int Q(long long b, int t){
    long long ret = 1;
    for(int i = 1;i <= t;i <<= 1, b = b * b % mod)
        if(i & t) ret = ret * b % mod;
    return ret;
}
int n, q, num;
int v[N], head[N], to[N<<1], nt[N<<1];
int ans[N][N];
struct BAG{
    int a[N], sz;
}f[N], sum[N], pro[N];
long long tmp[N];
inline void operator *= (BAG &A, const BAG &B){
    for(int i = 0;i <= A.sz + B.sz;i++) tmp[i] = 0;
    for(int i = 0;i <= A.sz;i++)
    for(int j = 0;j <= B.sz;j++)
        if ((tmp[i + j] += 1ll * A.a[i] * B.a[j]) >= mod)
			tmp[i + j] %= mod;
    A.sz += B.sz;
    for(int i = 0;i <= A.sz;i++)
        A.a[i] = tmp[i] % mod;
}
inline void operator /= (BAG &A, const BAG &B){
    for(int i = 0;i <= A.sz;++i) 
        tmp[i] = A.a[i], A.a[i]=0;
    A.sz -= B.sz;
    int inv = Q(B.a[B.sz],mod - 2);
    for(int i = A.sz;i >= 0;--i){
        A.a[i] = 1ll * tmp[i + B.sz] * inv % mod;
        for(int j = 0;j <= B.sz;++j)
            ((tmp[i + j] += 1ll * (mod - A.a[i]) * B.a[j])) %= mod;
    }
}
inline void operator += (BAG &A, const BAG &B){
    for(int i = 0;i <= B.sz;++i)
        Plus(A.a[i], B.a[i]);
    if(A.sz < B.sz) A.sz = B.sz;
}
inline void operator -= (BAG &A, const BAG &B){
    for(int i = 0;i <= B.sz;++i)
        Plus(A.a[i], mod - B.a[i]);
    while(A.sz and A.a[A.sz] == 0) --A.sz;
}
void Add(int x,int y){
    ++num;nt[num] = head[x];head[x] = num;to[num] = y;
    ++num;nt[num] = head[y];head[y] = num;to[num] = x;
}
void dp(int p, int fa){
    for(int i = head[p];i;i = nt[i]) 
        if(to[i] ^ fa) dp(to[i], p);
    pro[p].a[1] = v[p], pro[p].sz = 1;
    for(int i = head[p];i;i = nt[i]){
        int v = to[i];if(v == fa) continue;
        pro[p] *= f[v];
        sum[p] += f[v];
    }
    (f[p] = pro[p]) += sum[p],f[p].a[0] = 1;
}
void rdp(int p, int fa){
    if(fa) pro[p] *= f[fa], sum[p] += f[fa];
    (f[p] = pro[p]) += sum[p];f[p].a[0] = 1;
    long long tot = 0;
    for(int i = 1;i <= f[p].sz;++i)
        tot += (ans[p][i] = f[p].a[i]);
    ans[p][0] = tot % mod;
    BAG tp = pro[p], ts = sum[p];
    for(int i = head[p];i;i = nt[i]){
        int v = to[i];if(v == fa) continue;
        pro[p] = tp; pro[p] /= f[v];
        sum[p] = ts; sum[p] -= f[v];
        (f[p] = pro[p]) += sum[p]; f[p].a[0] = 1;
        rdp(v,p);
    }
}
int main(){

    r(n);
    for(int i = 1;i <= n;++i) r(v[i]);
    for(int i = 1, x, y;i < n;++i)
        r(x,y),Add(x,y);
    dp(1,0);
    rdp(1,0);
    r(q);int u,v;
    while(q--)
        r(u,v),w(ans[u][v]);
    return 0;
}

T3 区间 DP

Description

给定 $m$ 个区间 $[l_i,r_i,v_i]$ 。定义一个区间集合的权值为区间权值之积。若一个区间集合的并集完整地覆盖了 $[1,n]$ ，则称这个集合合法。求所有合法集合的权值之和。
$1\leq m\leq 2\times 10^5,1\leq l_i\leq r_i\leq n\leq 10^5$

Solution

若干个区间上的 DP 有两种，要么对区间 DP ，要么对值域 DP 。
本题做法是对值域 DP 。设 f[i] 表示精确覆盖 $[1,i]$ 时区间集合的权值之和。
可能有多个区间的右端点在 $i$ 这个位置，我们按照 $l$ 从大到小的顺序依次枚举区间 $[l,i]$ 来转移。那么有

$f_i=\sum_{[l,i]\in S} w \sum_{j=l-1}^{i-1}f_jv(j+2,i)$

其中 $S$ 是当前枚举的右端点在 $i$ 的区间集合。$w$ 是已经考虑过的 $[l,i]$ 对当前 $[l,i]$ 的贡献。设 $T$ 表示已经考虑过的区间，则后面的 $v$ 函数表示

$v(l,r)=\prod_{[L,R]\in T\cap l\leq L\leq R\leq r}(1+v_i)$

也就是枚举一个转移点，转移点内的区间任意选。然后注意带上右端点相同时的贡献。
考虑如何优化。我们设 $g_j=f_j\times v(j+2,i)$ 。在线段树上维护 $g$ 即可。

Code

const int N = 5e5 + 5, mod = 998244353;
using namespace std;
int n, m, num;
int to[N], nt[N], val[N], head[N];
void Add(int x,int y,int z){
    nt[++num] = head[x];head[x] = num;to[num] = y;val[num] = z;
}
namespace SEG{
#define mid (l+r>>1)
#define Ls p<<1,l,mid
#define Rs p<<1|1,mid+1,r
    int t[N<<2], tag[N<<2];
    void update(int p){
        t[p] = 1ll * (t[p<<1] + t[p<<1|1]) % mod * tag[p] % mod;
    }
    void add(int p, int l, int r, int pos, int v){
        t[p] = (t[p] + v) % mod;
        if(l == r) return;
        if(mid >= pos) add(Ls, pos, v);
        else add(Rs, pos, v); 
    }
    void mul(int p, int l, int r, int nl, int nr, int v){
        if(l > nr || r< nl) return;
        if(l >= nl && r <= nr){
            t[p] = 1ll * t[p] * v % mod;
            tag[p] = 1ll * tag[p] * v % mod;
            return;
        }
        mul(Ls, nl, nr, v);
        mul(Rs, nl, nr, v);
        update(p);
    }
    int query(int p, int l, int r, int nl, int nr){
        if(l > nr || r < nl) return 0;
        if(l >= nl && r <= nr) return t[p];
        return 1ll * (query(Ls, nl, nr) + query(Rs, nl, nr)) % mod * tag[p] % mod;
    }
}
using namespace SEG;

int main(){

    r(n, m);
    for(int i = 1, x, y, v; i <= m; ++i)
        r(x, y, v), Add(y, x, v);
    for(int i = 1;i <= n * 4; ++i)
        tag[i] = 1;
    add(1, 0, n, 0, 1);
    for(int i = 1; i <= n; ++i)
    for(int j = head[i];j;j = nt[j]){
        int s = query(1, 0, n, to[j] - 1, i);
        add(1, 0, n, i, 1ll * s * val[j] % mod);
        if(to[j] >= 2)
            mul(1, 0, n, 0, to[j] - 2, val[j] + 1);
    }
    w(query(1, 0, n, n, n));
    return 0;
}

T4 计数 DP

Description

有 $n$ 个可区分的球和一个无限长的颜色序列，初始时颜色序列每个位置都是白色的。
K 闲着没事干，于是玩起了染色游戏。
K 在颜色序列上从左到右依次染色，每次有三种选择：

• 染红色。此后 K 会选出 $m$ 个球将它们扔掉。如果球数不足 $m$ ，不能染红色。
• 染蓝色。此后 K 会选出 $m - 1$ 个球将它们扔掉。如果球数不足 $m - 1$ ，不能染蓝色。
• 染白色。此后游戏结束。

K 玩了 $+\infty$ 局染色游戏，游戏结束后的局面各种各样，现在 K 想知道，最终有多少种可能的局面？
两个局面不同，当且仅当以下条件至少一个成立：

• 存在一个球，它在一个局面被扔掉而在另一个局面被保留了下来。
• 颜色序列存在一个位置，它在两个局面中的颜色不同。

Solution

先给出结论式子

$\sum_{i=0}\binom{n+i}{m\times i}$

考虑如何从组合意义下手得到它：

• 一开始时，我们有 $n$ 个白色球。
• 染红色：选出来 $m$ 个球染黑色，再追加一个白球。
• 染蓝色：选出来 $m-1$ 个球染黑色，再追加一个黑球。

追加的球可以视作颜色序列。枚举最终有多少次染色，可以得到上述式子。
接下来考虑如何求解这个式子。带组合数的式子可以从组合数的递推公式来考虑：

$\sum_{i=0}\binom{n+i}{m\times i}=\sum_{i=0}\binom{n+i-1}{m\times i}+\sum_{i=0}\binom{n+i-1}{m\times i-1}$

注意到最后项的组合数的下面是 $i-1$ 而非 $i$ 。为了方便，我们设

$f_{n,m,k}=\sum_{i=0}\binom{n+i}{m\times i-k}$

于是有递推式

$f_{n,m,k}=f_{n-1,m,k}+f_{n-1,m,k+1}$

我们发现 $m$ 维没甚么用，就把它省掉了。观察 $f_{n,k}$ 的性质

$\begin{aligned} f_{n,k}&=f_{n-1,k}+f_{n-1,k+1}\\ &=\sum \binom{n-1+i}{m\times i-k}+\binom{n-1+i}{m\times i-k-1} \end{aligned}$

我们令 $k=m$ ，可以得到递推式

$f_{n,m}=f_{n,0}+f_{n,1}$

再设 $f_{a,b}=g_{am+b}$ ，那么有

$g_{nm+m}=g_{nm}+g_{nm+1}$

更一般地，$g$ 的递推式实际上就是

$g_{n}=g_{n-m}+g_{n-m+1}$

而我们需要求的就是 $f_{n,0}=g_{nm}$ 。观察到 $g_n$ 的递推形式是常系数齐次线性递推，于是可以用多项式科技优化到 $\mathcal{O}(m\log n\log nm)$ 。
$g$ 的初值可以手算，只有当 $i=0$ 或者 $i=m-1$ 的时候 $g_i=1$ ，其余均为 $0$ 。

Code

const int N = 1e6 + 5, mod = 998244353, G = 3;
using namespace std;
long long n, m;
int a[N], b[N], _a[N], _b[N], rev[N];
int len, cnt;
template<typename tp>inline void Plus(tp &a, tp b){a = a + b - mod; a = a + ((a>>31) & mod);}
int Q(long long b, int t){
    long long ret = 1;
    for(int i = 1;i <= t; i <<= 1, b = b * b % mod)
        if(i & t) ret = ret * b % mod;
    return ret;
}
void NTT(int *a, int len, int type){
    for(int i = 1;i < len; ++i)
        if(i < rev[i]) swap(a[i], a[rev[i]]);
    for(int i = 1;i < len; i <<= 1){
        int wn = Q(G, (mod - 1) / (i << 1));
        for(int j = 0;j < len; j += (i << 1)){
            int w = 1, t1, t2;
            for(int k = 0;k < i; ++k, w = 1ll * w * wn % mod)
                t1 = a[k + j], t2 = 1ll * a[i + j + k] * w % mod,
                a[k + j] = (t1 + t2) % mod, a[i + j + k]=(t1 + mod - t2) % mod;
        }
    }
    if(type) return;
    int inv = Q(len, mod - 2);
    reverse(a + 1, a + len);
    for(int i = 0;i < len; ++i)
        a[i] = 1ll * a[i] * inv % mod;
}
void Getmul(int *a, int *b, int *c, int la, int lb){
    for(int i = 0;i < len; ++i)
        _a[i] = i < la ? a[i] : 0,
        _b[i] = i < lb ? b[i] : 0;
    NTT(_a, len, 1),NTT(_b, len, 1);
    for(int i = 0;i < len; ++i)
        c[i] = 1ll * _a[i] * _b[i] % mod;
    NTT(c, len, 0);
    for(int i = len - 1;i >= m; --i)
        Plus(c[i - m], c[i]), Plus(c[i - m + 1], c[i]), c[i] = 0;
}
int main(){

    r(n, m);

    a[0] = 1;
    b[1] = 1;
    long long k = n * m;
    len = 1, cnt = 0;
    for(int l = m + m; len <= l;len <<= 1, ++cnt);
    for(int i = 0; i < len;++i) 
        rev[i] = (rev[i>>1] >> 1) | ((i & 1) << cnt - 1);
    for(long long i = 1; i <= k; i <<= 1, Getmul(b, b, b, m, m))
        if(i & k) Getmul(a, b, a, m, m);
    w((a[0] + a[m - 1]) % mod);
    return 0;
}

Analysis

Kewth yyds ！
这场考试收获颇丰。T2 T3 T4 都是我十分薄弱之处，趁机巩固了不少。
T2 直接挑明了背包和多项式的关系。做这种树形背包时我的思路还不够清晰，应该先在草稿上写出完整的转移方程再敲。敲的过程中发现的问题要在草稿上改然后再进行。只有方程足够清晰，才能看出来如何优化。将背包和多项式结合在一起后，无论是合并还是分裂都深刻了许多。
T3 若干个区间上的 DP 也是我的薄弱之处。这方面的 DP 一方面要考虑强制选择的转移，一方面要考虑任意选择的贡献。
T4 推式子+多项式科技。学习了如何更好地应对带组合数的式子。可以转递推再套多项式科技。