AGC059F

Rainbow_qwq · 2023-01-22 17:02:58 · 题解

anton 题，恐怖红黑蜜蜂不是人类！！！

下面有很多自己的思考，所以和官方题解不太一样（

Part 1

看到 LIS(P)+LDS(P)，可以想到用杨表来刻画一个排列 P.

根据 wiki，一个排列 P 可以双射到两个形态相同的标准杨表，具体方法如下（其实就是 RSK 算法，建议自行了解）：

维护两个杨表 A,B，每次向 A 插入 P 的第 i 个元素 P_i=x。从第一行开始：

• 找到本行最小的比 x 大的数，设为 y。如果找不到这样的 y，则把 x 放在本行末尾并结束。
• 否则交换 x,y，将 y 插入下一行。

最后 A 的某一行会多一个位置出来，在 B 中的那个位置放一个 i。最终得到的 A,B 是形态相同的标准杨表。

回到本题。LIS(P)+LDS(P)=n+1 的条件是苛刻的，要求杨表只有第一行和第一列组成（一个 L 形），否则就小于 n+1 了。

算一下总符合的排列个数，枚举第一行的长度，可得到总个数为 \sum_{i=0}^{n-1}\binom{n-1}{i}^2=\sum_{i=0}^{n-1}\binom{n-1}{i}\binom{n-1}{n-1-i}=\binom{2n-2}{n-1}.

根据打表的结果，符合的总排列个数是 \binom{2n-2}{n-1}，这两个结果相同。

Part 2

但我们还要求 P_{pos}=val，考虑从杨表形态倒推限制。

在只有一行一列的杨表中，对于后面 n-1 次插入每次插入都只有两种情况：

• 大于第一行末尾，直接在 A 表第一行 push_back（此时在 B 表第一行后面 push_back）
• 从第一行换出来一个元素，并且换出来的元素比以前换出来的都小。（此时在 B 表最后新增一行）

倒着考虑这个过程，就是以下两种操作：

• 从第一行结尾删一个元素。
• 把第一列第二个元素 x 放回第一行中，找到第一行中最后一个比 x 小的元素 y，把 y 用 x 替换掉，删除 y。

令 pos\to n-pos（其实不变也行），我们要求第 pos 个删掉的元素是 val。

把杨表 A 中第一行的元素都看成“黑球”，其他的看做“红球”。那就变成了下面的过程：

一开始 2\sim n-1 球颜色任意，1 为黑球。每次可以执行两种操作：

• 删掉最后一个黑球（删黑操作）
• 删掉第一个红球前的一个黑球，把这个球变黑（删红操作）

这样一个好排列可以双射到一个删球过程，要求第 pos 个删掉的球是 val。

Part 3

但这还是不好数，我们再加一个时间轴。（接下来这步可能过于抽象）

发现整个删球的过程有两部分：一开始删黑球时一开始会删最后一个，后来删的时候会恰好在下一步删前面的一个。删红球也有类似的过程。可以用下面的结构来描述：

画一张 n\times n 个格子的网格图，n-1 条竖线表示球的颜色，n-1 条横线表示删球的操作。（注意格子的数量是 n\times n，线的数量是 n-1！）

每次删黑操作就在最后一条黑竖线上标一个黑点，删红操作就在第一条红竖线上标一个红点。

接下来把每步真实删去的球是哪个编号涂上颜色：

我们发现每步真实删去的球的编号满足如下规律：

• 对于每个黑点：如果它的右上方没有红点，就把右上方的格子涂黑；如果它的左下方没有红点，就把左下方的格子涂黑；
• 对于每个红点：如果它的左上方没有黑点，就把左上方的格子涂红；如果它的右下方没有黑点，就把右下方的格子涂红；
• 最后所有被涂上颜色的格子代表了每步真实删去的球的编号，也就对应了这个排列。

当然也有一种特殊情况，只涂色了 n-1 个格子，这时把剩下的没有颜色的一行一列交点涂上色就可以了。

于是我们完成了好排列到选交点方案的双射，我们要求的就是格子 (pos,val) 最终被涂色的方案数。

Part 4

首先计算某个红点向右下方涂色涂到了 (x,y) 的方案数，其他三个方向是对称的。

枚举这是从上到下的第 i 个红色交点，那左上方就是在前 x-2 与 y-2 中各选 i-1 个坐标，可以用组合数计算。

接下来推一下会发现至少还要选 n+1+i-x-y 个红色交点，才能符合右下方没有黑点，并且也是充要条件，于是可以通过算组合数前缀和来计算右下的方案数。

接下来计算特殊情况被涂色的方案数，发现特殊情况只有在上面那张图的左上右下加一对红点，和左下右上加一对黑点，经过若干次这两种操作后得到。于是枚举加红点对子的个数，就可以组合数计算。

时间复杂度线性。

// 代码式子改的不太一样
int n,x,y;
modint res,sum[maxn];

void F(int x,int y){
    For(i,0,n)sum[i]=C(n-x-1,i)*C(n-y-1,i);
    Rep(i,n-1,0)sum[i]+=sum[i+1];
    For(i,0,n){
        int t=n+1+i-x-y;
        t=max(t,0),t=min(t,n);
        res+=C(x-1,i)*C(y-1,i)*sum[t];
    //  For(j,t,n)res+=C(x-1,i)*C(y-1,i)*C(n-x-1,j)*C(n-y-1,j);
    }
}

signed main()
{
    n=read(),x=read(),y=read(),initC(n+5);
    F(x-1,y-1),F(x-1,n-y),F(n-x,y-1),F(n-x,n-y);
    For(i,0,min(x,y)-1){
        int j=(y-1-i),k=(x-1-i);
        res+=C(x-1,i)*C(n-x,j)*C(y-1,i)*C(n-y,k);
    }
    cout<<res.x;
    return 0;
}