1 条题解

  • 0
    @ 2026-6-23 11:20:06

    考虑到最高的牛一定会被看到,所以以他为界限把左右分成两块。

    放个图看看:

    感谢图片原作者。

    我们把每个 (( 能看见的牛 \sim 左/右边所有被他遮住的牛 )) 视作一段,则一共有 A+B2A+B-2 个这样的段。

    分析一下这些段的性质:除了最高的元素,其余的元素可以任意排列,如 4 3 24 2 3 合法且不等价。

    此外,最高的元素要放在最左或最右,这时候我们考虑进行循环移位,例如把最后一个元素放到最前面,以此将最大元素移到两边。

    在这个限制下 4 3 22 4 3 其实是等价的。

    然后我们发明了圆排列

    sn,ks_{n,k}nn 个数分成 kk 个圆排列的方案数。

    给出递推公式:sn,k=sn1,k1+sn1,k×(n1)s_{n,k} = s_{n-1,k-1} + s_{n-1,k} \times (n-1)

    推导:从 n1n-1 个数的圆排列到 nn 个数的圆排列,要么第 nn 个自立门户,新开一个圆排列,要么加入之前的,有 n1n-1 种方案。

    然后我们又发明了第一类斯特林数!

    好!

    然后答案就很简单了,是一个斯特林数乘上一个计算左右分配方案的组合数。

    最终式子:

    Ans=sn1,A+B2×CA+B2A1Ans = s_{n-1,A+B-2} \times C_{A+B-2}^{A-1}

    CODE

    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    #define fi first
    #define se second
    int T,n,m;
    const int mod=1e9+7;
    int s[50100][210];
    int fac[1010],inv[1010];
    int qpow(int a,int b){
    	int r=1;
    	while(b){
    		if(b&1) r=r*a%mod;
    		a=a*a%mod,b>>=1;
    	}
    	return r;
    }
    signed main(){
    	ios::sync_with_stdio(0);
    	cin.tie(0),cout.tie(0);
    	s[0][0]=1;
    	for(int i=1;i<=50010;i++){
    		for(int j=1;j<=205;j++){
    			s[i][j]=(s[i-1][j-1]+(i-1)*s[i-1][j]%mod)%mod;
    		}
    	}
    	fac[0]=inv[0]=1;
    	for(int i=1;i<=1001;i++){
    		fac[i]=fac[i-1]*i%mod;
    		inv[i]=qpow(fac[i],mod-2);
    	}
    	cin>>T;
    	while(T--){
    		int x,y;
    		cin>>n>>x>>y;
    		cout<<s[n-1][x+y-2]*fac[x+y-2]%mod*inv[x-1]%mod*inv[y-1]%mod<<'\n';
    	}
    	return 0;
    }
    
    • 1

    信息

    ID
    758
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    (无)
    递交数
    1
    已通过
    1
    上传者