题解：AT_agc067_d [AGC067D] Unique Matching

· · 题解

似乎之前没有和该做法一样的题解。

本文中，为了保护视力 (*^_^*)，将用中括号包裹部分索引。

对于一个区间序列 S=\{[l_1,r_1],[l_2,r_2],\dots,[l_n,r_n]\} 和一个 1 到 n 的排列 P，定义

当且仅当 P[1]\in [l_1,r_1],P[2]\in [l_2,r_2],\dots,P[n]\in [l_n,r_n]。

这题要我们做的就是，对所有长为 n 的、**仅对应唯一排列的**区间序列计数。

排列很烦，先把排列强制为 \{1,2,\dots,n\}，答案最后再乘上 n!。这是不会算重的（如果算重了，就说明一个区间序列对应了多个排列）。

这样，问题就变成了

现在来考虑一个问题，假设我们已经获得了一个区间序列 S，如何判断它是否唯一对应排列 \{1,2,\dots,n\}。

不妨画一个方阵 \mathbf M 来辅助思考。这个方阵是 n\times n 的，每个位置是 0 或 1。对于坐标为 (x,y) 的位置，

\mathbf{M}[x][y]=[y\in [l_x,r_x]]

（对于命题 p，若 p 为真，则 [p]=1，否则 [p]=0）

例如，区间序列为 \{[1,3],[2,2],[3,3],[2,4]\}，那么画出的方阵为：（坐标 (1,1) 的位置在左下角）

\begin{matrix} 0 & 0 & 0 & 1\\ 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1\\ 1 & 0 & 0 & 0 \end{matrix}

容易发现，区间序列和方阵是一一对应的。

对于一个区间序列 S，画出方阵 \mathbf M，我们能找到一个让 S 唯一对应排列 \{1,2,\dots,n\} 的冲要条件：

正确性是容易验证的。这个条件是递归性的，并且可以 dp。

但是，如果存在多个可以第一次删除的坐标怎么办呢？考虑容斥，钦定一些位置可以在第一次删除。

设 i\times i 且满足要求的方阵有 g[i] 个，则可写出如下容斥计数式子：（其中 (v_1,v_1),(v_2,v_2),\dots,(v_m,v_m) 就是被钦定可以第一次删除的位置）

g[i]=\sum_{m=1}^i\sum_{1\leq v_1<v_2<\cdots<v_m\leq n} (-1)^{m+1}v_1\left(\prod_{i=2}^m(v_i-v_{i-1})^2\right)(n-v_m+1)g[v_1-1]\left(\prod_{i=2}^m g[v_i-v_{i-1}-1]\right)g[n-v_m]

然后可以用“辅助数组” h 帮助转移：

\begin{gathered} h[i]=ig[i-1]+(-1)\sum_{j=1}^{i-1}h[j](i-j)^2g[i-j-1]\\ g[i]=\sum_{j=1}^ih[j](i-j+1)g[i-j] \end{gathered}

当然，有初始值 g[0]=1，而答案就是 n!g[n]。

直接 dp 空间复杂度为 O(n)，时间复杂度为 O(n^2)。

代码：

#include<bits/stdc++.h>
using std::cerr; using std::setw; using std::endl;
using std::cin; using std::cout;
template<typename Tp>
bool tomax(Tp &x,const Tp &y){if(x<y){x=y; return 1;} return 0;}
template<typename Tp>
bool tomin(Tp &x,const Tp &y){if(y<x){x=y; return 1;} return 0;}
using ll=long long; using ui=unsigned; using lf=double;
using ull=unsigned long long;
constexpr ll MAXN=5000;
ll N,P;
ll mo(ll x){return x>=P?x-P:x;}
void n_add(ll &x,ll y){x=mo(x+y); return ;}
void n_sub(ll &x,ll y){x=mo(x+P-y); return ;}
ll pow2(ll x){return x*x%P;}
ll fac[MAXN+5];
ll g[MAXN+5],h[MAXN+5];
int main(){
    std::ios::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);
    cin>>N>>P;
    fac[0]=1ll; for(ll i=1;i<=N;i++) fac[i]=i*fac[i-1]%P;
    g[0]=1ll;
    for(ll i=1;i<=N;i++){
        h[i]=i*g[i-1]%P;
        for(ll j=1;j<i;j++){
            n_sub(h[i],h[j]*pow2(i-j)%P*g[i-j-1]%P);
        }
        for(ll j=1;j<=i;j++){
            n_add(g[i],h[j]*(i-j+1)%P*g[i-j]%P);
        }
    }
    ll ans=g[N]*fac[N]%P;
    cout<<ans<<'\n';
    return 0;
}