题解 CF367E

传送门

首先 \(n>m\) 时显然无解。由原题的数据范围可得 \(n\le \sqrt{10^5}\) 。

考虑如何构造出满足条件的 \(n\) 个区间。不难发现对于任意两个不同区间 \([l_i,r_i],[l_j,r_j]\) ，都有 \(l_i<l_j,r_i<r_j\) 即可。那么我们如果选取了 \(n\) 个左端点和 \(n\) 个右端点，有且仅有一种满足题意的构造方式，也就是将左右端点分别排序后按序号匹配。

下面考虑如何计算总方案数。定义 \(dp[i][j][k]\) 为考虑完前 \(i\) 个位置，目前有 \(j\) 个左端点被选择，\(k\) 个右端点被选择。而右端点总是要与左端点匹配，所以需要保证 \(j\ge k\) 。注意到关键点时只能考虑向 \(k+1\) 转移。

时间复杂度：\(O(mn^2)\)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N=1e5+5,P=1e9+7;
int n,m,x,fac[N];
inline void Add(int &x,const int &y){x+=y;if(x>P)x-=P;}
int main(){
    n=read(),m=read(),x=read();
    if(n>m)return puts("0"),0;
    int dp[2][n+5][n+5];
    memset(dp,0,sizeof(dp));
    dp[0][0][0]=1;
    rep(i,1,m){
        int now=i&1,pre=now^1;
        memset(dp[now],0,sizeof(dp[now]));
        rep(j,0,n)rep(k,0,j){//第i个位置，j个左括号，k个右括号
            if(j>k&&i!=x)Add(dp[now][j][k+1],dp[pre][j][k]);
            Add(dp[now][j+1][k],dp[pre][j][k]);
            Add(dp[now][j+1][k+1],dp[pre][j][k]);
            if(i!=x)Add(dp[now][j][k],dp[pre][j][k]);
        }
    }
    fac[0]=1;
    rep(i,1,n)fac[i]=1ll*fac[i-1]*i%P;
    printf("%lld\n",1ll*dp[m&1][n][n]*fac[n]%P);
    return 0;
}

Comments