题解：P15015 If / [SNOW] - 14

· · 题解

这题，D？

Swap B & D please.

只看 \texttt{I,F} 的话，显然为了满足条件得到的串必然是 \texttt{FFF\dots FIFI\dots III} 状物。

考虑插入 \texttt{L,E}。

值域明示做法，考虑枚举构成 \texttt{L\red IE} 的那个 \texttt{\red I}。

假设这个 \texttt I 我们知道了，那么显然必须得保证 \texttt I 左边有且仅有一个 \texttt L，右边同理有且仅有一个 \texttt E。

然后这两个 \texttt{L,E} 之间显然只能有一个 \texttt I。

于是这两个 \texttt{L,E} 出产的贡献是好求的，分类讨论即可。

剩下的，\texttt E 在左边任意插，\texttt L 在右边任意插。

我们知道把 m 个字符插入 n 个字符的串中的组合数计算方式是：

\binom{n+m}{m}

解释：插入后的字符串长度为 n+m，其中有 m 个是新来的，显然得到插入的位置就能得到一个对应的方案，那么就是从 n+m 个点中选择 m 个点的方案数。

把上面的情况一个个扔到这个式子里算就做完了。

注意组合数要预处理到三倍值域。

#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
#define N 30000000
using namespace std;
int qpow(int a,int b=mod-2){
    int ans=1;
    while(b){
        if(b&1)ans=ans*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ans;
}
int A[N+5];
int inv[N+5];
int C(int n,int m){
    return A[n]*inv[m]%mod*inv[n-m]%mod;
}
void solve(){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    int ans=0;
    for(int i=1;i<=b;i++){
        if(i==1)
        ans=(ans+2*c%mod*C(c+d-1,d-1)%mod*C(a+b+c+d-(c+d-1)-1,a-1))%mod;
        else if(i==2)
        ans=(ans+2*C(c+d+1,d-1)%mod*C(a+b+c+d-(c+d+1)-1,a-1)%mod)%mod;
        else
        ans=(ans+C(c+i+d-1,d-1)*C(a+b+c+d-(c+i+d-1)-1,a-1)%mod)%mod;
    }
    cout<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    A[0]=1;
    for(int i=1;i<=N;i++)A[i]=A[i-1]*i%mod;
    inv[N]=qpow(A[N]);
    for(int i=N;i;i--)inv[i-1]=inv[i]*i%mod;
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}
// 茫然旅行中的我，是在滞留第一天于面包店买完面包时，受到这个国家的政.府官员约见。
// 只要具有魔女的身分，就时常会被请去解决国家的麻烦事。