题解：P15015 If

Circle_Table · 2026-07-06 15:48:49 · 题解

这边是题目传送门喵！

欢迎来博客园阅读！

:::info[如果]

生まれた意味も　死ねない理由も

降生于世的意义无法死去的理由

未だにわからないけど

尽管心中对此依旧不解

この命に価値がないとしても

就算这条生命没有任何价值

世界は美しいんだから

世界依旧美丽

生きていこう

一起活下去吧！ :::

题意

给定四种字符 \texttt{L},\texttt{I},\texttt{F},\texttt{E} 的个数，要求讲这些字符排列并保证有且仅有一个子序列是 \texttt{IF}，一个子序列是 \texttt{LIE}。

思路

针对两个约束条件分别考虑。

有且仅有一个子序列是 \texttt{IF}，等价于有且仅有一个 \texttt{F} 在有且仅有一个 \texttt{I} 的右边。如果只考虑这两种字符，也就可以等价于在一个 \texttt{IF} 左边全部是 \texttt{F}，右边全部是 \texttt{I}。也就是这个样子：
\texttt{FF}\dots\texttt{FFIFII}\dots\texttt{II}
显而易见地，这只有一种可能性，就是把 \texttt{F} 全部摆出来再把 \texttt{I} 全部摆出来，然后交换一下最中间交界处的两个即可。
有且仅有一个子序列是 \texttt{LIE}，这个时候其实已经不受 \texttt{F} 的影响了。第一个约束条件已经处理好了，剩下的 \texttt{I} 都挤在一起。如果只考虑这三种字符，也就可以等价于在一个全部由 \texttt{I} 组成的字符串 \texttt{III}\dots\texttt{II} 中间插入 \texttt{L},\texttt{E}，同时保证只有一个子序列是 \texttt{LIE}。

约束条件一中我们说有且仅有一个 \texttt{F} 在有且仅有一个 \texttt{I} 的右边，那么现在就应该是：有且仅有一个 \texttt{L} 在某一个 \texttt{I} 的左边，同时有且仅有一个 \texttt{E} 在这个 \texttt{I} 的右边。于是我们想到只要中间有一个 \texttt{LIE} 就可以了，剩下的 \texttt{E} 随便放左边，\texttt{L} 随便放右边。

对于两种条件分析清楚了，就差不多可以写代码了。

先提一下，将 n 个字符向 m 个字符里插入的方案数，这里记为为 f(n,m)：等价于将总共的 n+m 个字符，选择 n 个出来作为这一次插入的字符，方案数 f(n,m)=\binom{n+m}{n}。

将两种条件融合，条件一相当于会把 \texttt{I} 分为三类，再在条件二中分类讨论：

对于第一个 \texttt{I}：
- 对于 \texttt{I} 左边，是 C-1 个 \texttt{F}，有 C 个空，\texttt{L} 有 C 种放发；还要将剩下的 D-1 个插入这 C-1 个 \texttt{F} 和 1 个 \texttt{L} 之间。所以左边的方案数为 C \times f(D-1,C)。
- 对于 \texttt{I} 右边，是 1 个 \texttt{F} 和 B-1 个 \texttt{I}，\texttt{E} 可以放在 \texttt{F} 左边也可以在 \texttt{F} 右边，有 2 种放发；剩下 A-1 个 \texttt{L} 插入在这 B-1 个 \texttt{I}，1 个 \texttt{F} 和 1 个 \texttt{E} 之间。所以右边的方案数为 2 \times f(A-1,B+1)。
- 综上，由乘法原理，此时对答案的贡献为 2C \times f(D-1,C) \times f(A-1,B+1)。
对于第二个 \texttt{I}：
- 对于 \texttt{I} 左边，是这个样子：\texttt{FF}\dots\texttt{FFIF}，于是 \texttt{L} 可以放在 \texttt{F} 左边也可以在 \texttt{F} 右边，有 2 种放发；还有 D-1 个 E插入在 \texttt{FF}\dots\texttt{FFIF} 和新加进来的 \texttt{L} 这 C+2 个字母中。所以左边的方案数为 2 \times f(D-1,C+2)。
- 对于 \texttt{I} 右边，是 B-2 个 \texttt{I}。这个时候 \texttt{E} 就只有一种放发了，剩下的 A-1 个 \texttt{L} 要插入到这 B-2+1 个字符中。所以右边的方案数为 1 \times f(A-1,B-1)。
- 综上，由乘法原理，此时对答案的贡献为 2 \times f(D-1,C+2) \times f(A-1,B-1)。
对于第 i(3\leq i\leq B) 个 \texttt{I}：
- 对于 \texttt{I} 左边，\texttt{L} 只有一种放法了。于是左边就是这个样子：\texttt{FF}\dots\texttt{FFIFII}\dots\texttt{ILI}，其中最后一个 \texttt{I} 是第 i 个 \texttt{I}，其左边有 C+1+(i-1) 个字符，要放入 D-1 个 \texttt{E}，所以左边的方案数为 1 \times f(D-1,C+i)。
- 对于 \texttt{I} 右边，\texttt{E} 也是只有一种放法了。于是右边就是 B-i 个 \texttt{I}，加上一个 \texttt{E}，所以是在 B-i+1 个字符里插入 A-1 个 \texttt{L}。所以右边的方案数为 1 \times f(A-1,B-i+1)。
- 综上，由乘法原理，此时对答案的贡献为 f(D-1,C+i)\times f(A-1,B-i+1)。

对于每一个 \texttt{I} 进行一次计算，时间复杂度为 \Theta(\sum B)。

预处理到 4\times 10^7 发现爆空间了，发现我们要求的最大的一个东西是 f(D-1,C+i)，i=B，最大计算组合数的时候会到 3\times 10^7，然后就过了。

:::success[代码]

#include <bits/stdc++.h>
#define loop(i,a,b) for(int i=(a);i<=(int)(b);i++)
#define rloop(i,a,b) for(int i=(a);i>=(int)(b);i--)
using namespace std;
typedef long long ll;

const int N=3e7+5,maxn=3e7;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;

int a,b,c,d;
ll fac[N+5],inv[N+5];

ll qmi(ll a,int k){
    ll res=1;
    while(k){
        if(k&1)res=res*a%mod;
        a=a*a%mod;
        k>>=1;
    }
    return res;
}

void init(){
    fac[0]=1;
    loop(i,1,maxn)fac[i]=fac[i-1]*i%mod;
    inv[maxn]=qmi(fac[maxn],mod-2);
    rloop(i,maxn,1)inv[i-1]=inv[i]*i%mod;
    return;
}

ll C(int m,int n){
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}

ll f(int n,int m){return C(n,m+n);}

ll solve(){
    cin>>a>>b>>c>>d;
    ll ans=0;
    loop(i,1,b){
        if(i==1)ans=(ans+c*f(d-1,c)%mod*2*f(a-1,b+1)%mod)%mod;
        else if(i==2)ans=(ans+2*f(d-1,c+2)%mod*1*f(a-1,b-1)%mod)%mod;
        else ans=(ans+1*f(d-1,c+i)*1*f(a-1,b-i+1)%mod)%mod;
    }
    return ans;
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    init();
    int T; cin>>T;
    while(T--)cout<<solve()<<'\n';
    return 0;
}

:::