题意简化
1—n-1个建筑物让他们排列起来,左边与右边分别可以看见A,B个建筑物,问建筑物排列的方案数?
算法一 – stirling_1+排列
思路
代码
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=50010,M=210;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll qmi(ll m,ll k, ll p=mod){int res=1%p,t=m;while(k){if(k&1)res=res*t%p;t=t*t%p;k>>=1;}return res;}
ll inv(ll a){return qmi(a,mod-2);}
ll f[N][M],c[M][M];
int main(){
f[0][0]=1;
//特殊情况 s(0,0)=1
//初始化第一类斯特林数
for(int i=1;i<N;i++)
for(int j=1;j<M;j++)
f[i][j]=(f[i-1][j-1]+(ll)(i-1)*f[i-1][j])%mod;
//组合数的处理
for(int i=0;i<M;i++)
for(int j=0;j<=i;j++)
if(!j)c[i][j]=1;
else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
int T;cin>>T;
while(T--){
ll n,a,b;cin>>n>>a>>b;
// s(a-1,a+b-2) * C(a+b-2,a-1)
cout<<(ll)(f[n-1][a+b-2]*c[a+b-2][a-1]%mod)<<endl;
}
return 0;
}
注释中的 s(a-1,a+b-2) 应该是 s(n-1,a+b-2)
收到 马上修改
很赞,箭头略有败笔之嫌。hh
手工画的 QAQ (
希望没有人注意可以买一个数位板hh