【HDU 4372】 Count the Buildings (第一类斯特林数)

【分析】

---

对于斯特林数：

　　第一类斯特林数和第二类斯特林数的分组都不是排列，就是说组是没有编号的，如果加上编号，乘上k！即可，或者在递推公式里面乘。

　　比如：  s(p,k)=(p-1)*s(p-1,k)+s(p-1,k-1)*k (表示如果有一个新的组，要考虑它的位置对答案影响)

　　第一类斯特林数的n个物品循环排列方案事实上等于n-1个物品的排列方案，因为n!/n=(n-1)!

　　所以如果你要分组，组内一个元素位置要固定，那么就等于循环排列。（如本题）

　　

　　斯特林数长这样：

　　

　　第一类斯特林数有以下性质：

　　

 

---

代码如下：

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<queue>

 #include<cmath>

 using namespace std;

 #define Mod 1000000007

 #define LL long long

 #define Maxn 2010

 LL s[Maxn][Maxn],c[Maxn][Maxn];

 void init()

 {

     memset(s,,sizeof(s));

     memset(c,,sizeof(c));

     s[][]=;

     for(int i=;i<=Maxn-;i++) c[i][]=;

     for(int i=;i<=Maxn-;i++)

       for(int j=;j<=Maxn-;j++)

       {

           s[i][j]=(s[i-][j-]+(i-)*s[i-][j])%Mod;

           c[i][j]=(c[i-][j]+c[i-][j-])%Mod;

       }

 }

 int main()

 {

     init();

     int T;

     scanf("%d",&T);

     while(T--)

     {

         int n,x,y;

         scanf("%d%d%d",&n,&x,&y);

         printf("%lld\n",(s[n-][x+y-]*c[x+y-][x-])%Mod);

     }

     return ;

 }

[HDU 4372]

2016-09-22 13:50:59