题目： https://ac.nowcoder.com/acm/problem/15077
每次你可以入栈一个新元素或者当栈非空时出栈一个元素， n n n个元素必须依次入栈，而 W Y F WYF WYF希望其中第 m m m个元素入栈之后，栈中恰好有 k k k个元素，现在他想知道一共有多少种入栈出栈顺序满足这个条件。
思路： 首先分成两个子问题
在第 m m m个元素入栈之前，有 m − 1 m-1 m−1个入栈， m − k m-k m−k个出栈，并且每一时刻入栈的个数不少于出栈的个数，方案为 ( 2 m − 1 − k m − 1 ) k m {2m-1-k\choose m-1}\frac{k}{m} (m−12m−1−k)mk在第 m m m个元素入栈之后，还有有 n − m n-m n−m个入栈， n − m + k n-m+k n−m+k个出栈，并且每一时刻出栈的个数减入栈的个数小于等于 k k k(栈里已经有 k k k个元素)，方案数为 ( 2 n − 2 m + k n − m ) k + 1 n − m + k + 1 {2n-2m+k\choose n-m}\frac{k+1}{n-m+k+1} (n−m2n−2m+k)n−m+k+1k+1 答案就是两式相乘注意： 算组合数有不合法的情况
#include<bits/stdc++.h> #define ll long long #define mod 1000000007 using namespace std; const int N=4000009; int T; ll p[N],p1[N]; ll qpow(ll a, ll b){ ll res=1; a%=mod; while(b){ if(b&1) res=res*a%mod; a=a*a%mod; b>>=1; } return res; } ll cal(ll a,ll b){ if(a<0||b<0||a-b<0)//不合法 return 0; return p[a]*p1[b]%mod*p1[a-b]%mod; } int main() { p[0]=1; for(int i=1;i<N;i++) p[i]=p[i-1]*i%mod; p1[N-1]=qpow(p[N-1],mod-2); for(int i=N-2;i>=0;i--) p1[i]=p1[i+1]*(i+1)%mod; cin>>T; while(T--){ ll n,m,k,tmp,tmp1; cin>>n>>m>>k; tmp=cal(2*m-1-k,m-1)*k%mod*qpow(m,mod-2)%mod; tmp1=cal(2*n-2*m+k,n-m)*(k+1)%mod*qpow(n-m+k+1,mod-2)%mod; cout<<tmp*tmp1%mod<<endl; } return 0; }