[hdu4372]counting buildings

解题关键：

n的环排列的个数与n-1个元素的排列的个数相等。

首先可以肯定，无论从最左边还是从最右边看，最高的那个楼一定是可以看到的，从这里入手。

假设最高的楼的位置固定，最高楼的编号为n，那么我们为了满足条件，可以在楼n的左边分x-1组，右边分y-1组，且用每组最高的那个元素代表这一组，那么楼n的左边，从左到右，组与组之间最高的元素一定是单调递增的，且每组中的最高元素一定排在该组的最左边，每组中的其它元素可以任意排列（相当于这个组中所有元素的环排列）。右边反之亦然。

最高的那个楼左边一定有x-1个组，右边一定有y-1个组，且每组是一个环排列，这就引出了第一类Stirling数（$n$个人分成$k$组，每组内再按特定顺序围圈的分组方法的数目）。我们可以先把n-1个元素分成x-1+y-1组，然后每组内部做环排列。再在所有组中选取x-1组放到楼n的左边。所以答案是Stirling[n-1][x-1+y-1]*C[x-1+y-1][x-1](组合数);

预处理$O(N^2)$。对于每组询问$O(1)$解决。

第一类stirling数是环之间是无顺序的

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cstdlib>

 #include<cmath>

 #include<iostream>

 using namespace std;

 typedef long long ll;

 const int maxn=;

 const int mod=1e9+;

 ll comb1[maxn][maxn],stir[maxn][maxn];//2w*2w会爆掉

 void init1(){

     comb1[][]=stir[][]=;

     for(int i=;i<maxn;i++){

         comb1[i][i]=comb1[i][]=;

         stir[i][]=;stir[i][i]=;

         for(int j=;j<i;j++){

             comb1[i][j]=(comb1[i-][j-]+comb1[i-][j])%mod;

             stir[i][j]=((i-)*stir[i-][j]+stir[i-][j-])%mod;

         }

     }

 }

 int main(){

     int t,f,b,n;

     init1();

     cin>>t;

     while(t--){

         cin>>n>>f>>b;

         ll ans=;

         if(f+b-<=) ans=(1ll*stir[n-][b+f-]*comb1[b+f-][b-]+mod)%mod;

         else ans=;

         cout<<ans<<"\n";

     }

     return ;

 }

巴特西

[hdu4372]counting buildings

最新文章

热门文章