洛谷P3352 [ZJOI2016]线段树题解

题目链接：P3352 [ZJOI2016]线段树

题意：

cxy 遇到了一个题目：有一个序列 $a_1,a_2,\ldots,a_n$，$m$ 次操作。每次操作把一个区间内的数改成区间内的最大值，问最后每个数是多少。 cxy 很快地就使用了线段树解决了这个问题。

于是充满智慧的 cxy 想，如果操作是随机的，即在这 $m$ 次操作中每次等概率随机地选择一个区间 $[l,r]$（$1 \leq l \leq r \leq n$），然后将这个区间内的数改成区间内最大值（注意这样的区间共有 $\frac{n(n+1)}{2}$ 个），最后每个数的期望大小是多少呢？

cxy 非常热爱随机，所以她给出的输入序列也是随机的（随机方式见数据规模和约定）。

对于每个数，输出它的期望乘 $\left(\frac{n(n+1)}{2} \right)^m$ 再对 $10^9+7$ 取模的值。

输入格式：

第一行包含两个正整数 $n,m$，表示序列里数的个数和操作的个数。

接下来一行，包含 $n$ 个非负整数 $a_1,a_2,\ldots,a_n$。

输出格式：

输出共一行，包含 $n$ 个整数，表示每个数的答案。

数据范围：

$n \le 400,m\le 400$ 。

对于所有的测试数据，保证序列中数的大小不超过 $10^9$，并且每个数是 $0$ 到 $10^9$ 之间的随机整数。

~~中秋节晚上颓颓颓，Ravenfield装了十几个mod~~

期望dp+组合数神题。

因为答案乘以了 $\left(\frac{n(n+1)}{2} \right)^m$ ，所以最后就是求所有方案中每个数的和。

首先考虑 $01$ 序列怎么做。

我们可以统计每一个位置最终为 $0$ 的方案数

如果 $a_i$ 初始为 $1$ ，则无论如何最终都不会变成 $0$ 。
如果 $a_i$ 初始为 $0$ ，则设它左边最近的 $1$ 在 $l$ ，右边最近的 $1$ 在 $r$ 。

显然每次操作只会使 $l,r$ 缩小（也可能不变）。

因此我们对每个初始为 $0$ 的极长子段做一遍dp，然后把总贡献减去它。

也就是把 $\left(\frac{n(n+1)}{2} \right)^m$ 减去「最终为 $0$ 的方案数」（因为是 $01$ 序列，所以贡献等于方案数）

设 $f_{x,l,r}$ 表示 $x$ 次操作后，区间缩到 $(l,r)$ 的方案数，则

$f_{x,l,r} = f_{x-1,l,r} \times g_{l,r} + \sum_{0\le t < l}f_{x-1,t,r} + \sum_{r < t\le n+1}f_{x-1,l,t}$

注意这里是开区间，即
$\forall i \in(l,r),~h^x(a_i) = 0,h^x(a_l) = h^x(a_r)=1$
其中 $h^x(a_i)$ 表示第 $x$ 操作后 $a_i$ 的值。

其中 $g_{l,r}$ 表示无用操作的数量，有

$\begin{aligned} g_{l,r} &= \left[\binom{l+1}{2} + \binom{r-l}{2} + \binom{n-r+2}{2} \right] \\&= \frac{1}{2}\left[l(l+1)+(n-r+1)(n-r+2)+(r-l-1)(r-l)\right] \end{aligned}$

注：这里涉及了可重组合，即 $n$ 个不同元素选 $m$ 个可重元素组合的方案数为 $\dbinom{n+m-1}{m}$ 。

不难发现上面的 $\sum\limits_{1\le t < l}f_{x-1,t,r} + \sum\limits_{r < t\le n}f_{x-1,l,t}$ 可以前缀和优化。

因此 $01$ 序列时间复杂度 $\mathcal{O}(n^2m)$ 。

然后考虑原题怎么做。不难发现，最终序列的某个数 $x$ 可以拆分为（记 $M=\max\{a_i\}$ ）

$x \Leftrightarrow M - \sum_{i=0}^{M} [i > x]$

注：（来自参考文献[2]）

不拆分为 $\sum_{i=0}^{M} [i < x]$ 的原因是统计贡献时与 $l,r$ 有关，很麻烦，不利于下文中的整体dp。

我们枚举这个 $i$ ，然后把所有 $\ge i$ 的位置标为 $1$ ，所有 $< i$ 的标记为 $0$ ，这样就可以求出每个位置 $<i$ 的方案数。（相当于做 $M$ 次 $01$ 的情况）

但是这个枚举的过程不会爆炸吗？注意到 $i$ 从 $0$ 到 $M$ 扫的过程中， $01$ 序列其实只会变化 $\mathcal{O}(n)$ 次，因此实际不用做 $M$ 次。

因此复杂度为 $\mathcal{O}(n^3m)$ ，但因为随机数据可以卡过。

不过其实是存在稳定 $\mathcal{O}(n^2m)$ 的算法的。

注意到每一层的dp方程是一样的，根据期望的线性性质，

我们可以一次性把初值全加进去，然后跑一次整体的dp就可以算出来了，~~是不是很神奇？~~

实现的时候把所有数从大到小依次添加贡献，每次加的方案数就是与前一次的差值（具体可以看代码）

时间复杂度 $\mathcal{O}(n^2m)$ ，空间的话滚一下数组就好了。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)(555))
const int mod = 1e9+7;

bool vis[N];
struct node{int id,w;} a[N];
int n,m,ans[N],f[N][N],s1[N][N],s2[N][N];
bool cmp(node x,node y){return x.w < y.w; }
void Add(int &x,int y) { (x += y) >= mod ? x-=mod : 0;}
int add(int x,int y) { return (x += y) < mod ? x : x-mod;}
int qpow(int a,int b)
{int ans=1,base=a%mod;while(b){if(b&1)ans=ans*base%mod;base=base*base%mod;b>>=1;}return ans;}
int g(int l,int r) {return ( l*(l+1)+ (n-r+1)*(n-r+2) + (r-l-1)*(r-l) ) / 2;}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m; vis[n+1]=1;
    for(int i=1; i<=n; i++) { cin >> a[i].w; a[i].id = i; } sort(a+1, a+1+n, cmp);
    for(int i=n,last; i; i--)
    {
        last = 0; vis[a[i].id]=1;
        for(int j=1; j<=n+1; j++) if(vis[j]) { f[last][j] += a[i].w-a[i-1].w; last = j; }
    }
    ans[1] = a[n].w * qpow(n*(n+1)/2,m) % mod; for(int i=2; i<=n; i++) ans[i] = ans[1];
    for(int i=1; i<=m; i++)
    {
        for(int j=0; j<=n; j++) for(int k=n+1; k>j+1; --k)
        {
            s1[j][k] = add(j ? s1[j-1][k] : 0, f[j][k] * j % mod);
            s2[j][k] = add(k <= n ? s2[j][k+1] : 0, f[j][k] * (n-k+1) % mod);
        }
        for(int j=0; j<=n; j++) for(int k=j+2; k<=n+1; k++)
        {
            f[j][k] = f[j][k] * g(j,k) % mod;
            if(j) Add(f[j][k], s1[j-1][k]); 
            if(k<=n) Add(f[j][k], s2[j][k+1]);
        }
    }
    for(int i=0; i<=n; i++) for(int j=i+2; j<=n+1; j++)
        for(int k=i+1; k<j; k++) Add(ans[k], (mod-f[i][j])%mod);
    for(int i=1; i<=n; i++) cout << ans[i] << " \n"[i==n];
    return 0;
}