题解：AT_agc067_d [AGC067D] Unique Matching

· · 题解

大牛人题。给一个不一样的做法。

首先我们把这个问的东西反过来，也就是计算对于所有可能的排列，所对应的合法区间组的个数之和，容易发现排列不影响答案，所以可以默认 x_i=i。然后答案乘一个 n! 就行。

然后我们考虑一下合法区间组的条件，不难发现条件可以转化为：

我们来尝试一下固定一下 r，那么条件相当于 l_i \leq i,\forall 1 \leq i \leq n,i < j \leq r_i,l_j > i。

也就是我们给 l 一个上下界，第二个可以看成区间取 max。那么每个点的 max 设为 M_i，那么 l 的方案数可以看成 \prod{(i-M_i)}。

然后你发现有点卡住，因为这个区间取 max 没有什么很好的性质，我们考虑固定 M，来算合法的 r。

然后你发现非常的顺利啊，你发现每个 r 的取值范围都是一个区间。

我们先来推一下 M，从左往右扫描，那么 M 相当于维护一个集合，在时刻 i+1，如果 r_i>i，那么给集合加入 i，然后把所有 r_j=i 的 j 删了，然后取集合最大值。

那么 r_i 的这个下界就很明显了，就是 i 在 M 中最后一次出现的位置，没有出现过视为 i。

上界呢？我们想一下什么时候会有上界的影响，就是这个 r_i 最后一次出现过后，一定是被一个更大的数替换了，或者自己被删了，直到那个 M 变得比它更小的时候，它就肯定被淘汰了，也就是 M 第一次比 i 小的时刻的前一刻。

看起来很完美了吧，我们有一个 M 和两个乘积式，看起来只要能 dp 这个 M 就做完了。但是很遗憾，这个内容很难维护。

接下来需要一些非人类观察了。我们发现 0 \leq M_i < i。考虑建树，连边 (M_i,i)。那么我们改写一下刚刚这些量。

完美的变成了一个树形结构，考虑类似区间 dp，因为答案只取决子树大小，所以状态是一维的。

我们定义 f_n 表示大小为 n 的子树（根不为 0），算上所有点的贡献之和（不包括根的 i-M_i）。

定义 g_n 表示大小为 n 的森林的所有点的贡献之和（包括所有点的 i-M_i）。

易知 f_1=1,g_0=1。

写出 g 的式子，枚举最后一个树大小 s，那么它的编号是 n-s+1，则 g_n = \sum_{s=1}^{n}{g_{n-s}f_s(n-s+1)}。

来看 f，仍然枚举最后一个树大小 s，那么它的编号是 n-s+1，父亲编号是 1，然后父亲的 b_i-a_i+1 就是 s，所以 f_n=\sum_{s=1}^{n-1}{g_{n-1-s}f_s(n-s)s}。

答案为 g_nn!。

#include<bits/stdc++.h>
#define int long long
using namespace std;
char buf[1<<21],*p1,*p2;
#define gc() getchar()
template <typename T>
inline void read(T& x){
    x = 0;
    int f = 1;
    char ch = gc();
    while(!isdigit(ch)){
        if(ch == '-') f = -1;
        ch = gc();
    }
    while(isdigit(ch)){
        x = (x << 1) + (x << 3) + ch - '0';
        ch = gc();
    }
    x *= f;
}
template <typename T>
inline void write(T x){
    if(x < 0) putchar('-'),x = -x;
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
const int INF = 1e18 + 7;
/*
struct edge{
    int to,nxt;
}e[200010];
int nE = 0,hd[200010];
void add(int u,int v){
    e[++nE] = (edge){v,hd[u]};
    hd[u] = nE;
}
int fa[200010],cnt;
int Find(int i){
    return fa[i] == i ? i : fa[i] = Find(fa[i]);
}
void Unite(int u,int v){
    u = Find(u),v = Find(v);
    if(u == v) return;
    fa[u] = v;
    cnt--;
}
int bit[200010];
int LSB(int i){
    return i & (-i);
}
void upd(int i,int v){
    while(i <= n){
        bit[i] += v;
        i += LSB(i);
    }
}
int psq(int i){
    int res = 0;
    while(i){
        res += bit[i];
        i -= LSB(i);
    }
    return res;
}
*/
int n,MOD;
int f[5010],g[5010];
signed main(){
    read(n),read(MOD);
    f[1] = g[0] = g[1] = 1;
    for(int i = 2; i <= n; i++){
        for(int s = 1; s < i; s++) (f[i] += g[i - 1 - s] * f[s] % MOD * (i - s) % MOD * s) %= MOD;
        for(int s = 1; s <= i; s++) (g[i] += g[i - s] * f[s] % MOD * (i - s + 1)) %= MOD;
    }
    for(int i = 1; i <= n; i++) (g[n] *= i) %= MOD;
    printf("%lld",g[n]);
    return 0;
}