P5999 kangaroo 题解

_lxy_ · 2023-01-09 16:40:57 · 题解

更好的阅读体验

分析

一个妙妙的 trick。

首先原题可以转化成求有多少 1 \sim n 的排列 p 满足 \forall i\in(1,n)，p_i 两边的数同时小于或大于 p_i，且 p_1=s,p_n=t。这类题都可以采用插入法 dp。

首先设状态，dp_{i,j} 表示前 i 个数，分成 j 段的方案数。从小到大加入每一个数，考虑现在枚举到 i，若 i \neq s 且 i\neq t，则可以分三种情况讨论：

1. 新开一段

   由于后加入的一定比 i 大，所以以后插入在 i 两边的数一定比 i 大，所以总是合法。此时上一步操作完有 j-1 段，所以有 (j-1)+1=j 个空可以放。但是如果 i>s 说明头不能放，同理 i>t 说明尾不能放。因此有转移：

   dp_{i,j}=(j-[i>s]-[i>t]) \times dp_{i-1,j-1}

2. 接在某一段头/尾

   这样的话以后一定会有一个 >i 的数接在 i 另一侧，i 两侧就有一个大于它的和一个小于它的，与题意不符，所以不会有这种情况。

3. 将两段连起来

   此时 i 两侧的都比它小，与题意相符。上一步操作完有 j+1 段，有 j+1-1=j 个空可以插，因此有转移：

   dp_{i,j}=j\times dp_{i-1,j+1}

最后一定是整体一段，故答案为 dp_{n,1}。

核心代码

const int MAXN=2e3+7;
const int mod=1e9+7;
int n,s,t,dp[MAXN][MAXN];
signed main(){
    qread(n,s,t);int i,j;dp[1][1]=1;
    for(i=2;i<=n;i++){
        for(j=1;j<=i;j++){
            if(i!=s&&i!=t) dp[i][j]=(j*(dp[i-1][j+1])%mod+(j-(i>s)-(i>t))*dp[i-1][j-1]%mod)%mod;
            else dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
        }
    }printf("%lld\n",dp[n][1]);
    return 0;
}