P4609 [FJOI2016]建筑师 第一类斯特林数

题意:

戳这里

分析:

枚举一下 \(n\) 的位置,分成左右两段,然后将每一个能看见的建筑物和它会挡住的建筑物分成一组,然后每一组内部就是一个圆排列,因为默认最大的那个建筑是分割点,所以每一组内部就是一个圆排列

按照第一类斯特林数的递推公式 \(s[i][j]=s[i-1][j-1]+(i-1)*s[i-1][j]\)

这就是每一个圆排列的方案数之和,然后我们从这 \(a+b-2\) 个圆排列选出 \(a-1\) 个放在左边,也就是再乘上一个组合数

\(ans=s[n-1][a+b-2]*C(a+b-2,a-1)\)

复杂度 \(O(n^2)\)

代码:

#include<bits/stdc++.h>

using namespace std;

namespace zzc
{
    int read()
    {
        int x=0,f=1;char ch=getchar();
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
        while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
        return x*f;
    }

    const int maxn = 5e4+5;
    const int maxs = 205;
    const int mod = 1e9+7;
    long long s[maxn][maxs],fac[maxn],inv[maxn];
    int t,n,a,b;

    void init()
    {
        fac[0]=fac[1]=inv[0]=inv[1]=1;
		s[0][0]=s[1][1]=1;
        for(int i=2;i<=50000;i++)
        {
            fac[i]=fac[i-1]*i%mod;
            inv[i]=inv[mod%i]*(mod-mod/i)%mod;
            for(int j=1;j<=min(i,200);j++) s[i][j]=(s[i-1][j-1]+s[i-1][j]*(i-1))%mod;
        }
        for(int i=1;i<=50000;i++) inv[i]=inv[i]*inv[i-1]%mod;
    }

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

    void work()
    {
        init();
        t=read();
        while(t--)
        {
            n=read();a=read();b=read();
            printf("%lld\n",s[n-1][a+b-2]*C(a+b-2,a-1)%mod);
        }
    }

}

int main()
{
    zzc::work();
    return 0;
}
上一篇:Core Python | 2 - Core Python: Getting Started | 2.2 - Installing and Starting Python | 2.2.6 - The


下一篇:2/27 练习赛总结