AGC067D Unique Matching 题解

隔壁泞2的如心 · 2024-10-14 20:15:22 · 题解

虽然我似乎已经做出来过 O(n) 道 AT 3000+了，但是事实上我会的也只是 n 道中的 O(1) 道……

首先很显然，我们只需求出只能匹配成 p_i=i 的区间集数量，然后乘上 n! 即可。这样有 l_i\le i\le r_i，我们就可以把 l_i 和 r_i 分开计算了。

我们可以在平面上绘制 2n 条线段连接 (i,i),(r_i,i) 和 (i,i),(i,l_i)。合法的充要条件就是这 2n 条线段互相不在 (i,i) 以外的地方相交（不然交换某两项就也能匹配上了）。考虑把横向的线段画完后，每个竖线都不能触碰类似下图的白色区域：

所以我们不妨直接针对白色区域的形态进行计数。固定白色区域形态后，横线和竖线的方案数都可以简单算出。而对于白色区域而言，只要枚举白色区域的最靠右的空列就可以简单地转移。这个 dp 有很多种方法，就不细说了（

dp[1][0]=1;dp[0][0]=1; 
for(int i=2;i<=n;i++){
    for(int j=1;j<i;j++){
        add(dp[i][1],mut({dp[i-j][1]+dp[i-j][0],dp[j][0],i-j+1}));
        add(dp[i][2],mut({dp[i-j][1]+dp[i-j][0],dp[j][0],1}));
    }
    for(int j=1;j<i;j++)add(dp[i][0],mut({dp[i-j][0],dp[j-1][2]+dp[j-1][0],i}));
}
printf("%lld",(dp[n][0]+dp[n][2])*fac[n]%mod);

——主要是因为我这十行不到的 dp 调了两个多小时！！现在我知道我其实不会 dp 了……