首先想过n^3的组合方法,即f(i,j,k)=f(i-1,j,k)*(i-2)+f(i-1,j-1,k)+f(i-1,j,k-1),肯定搞不定
然后想了好久没有效果,就去逛大神博客了,结果发现需要用到第一类stirling数
第一类stirling数S(n,m)表示的是n个数排成m个非空环排列的数目
每个环排列中必然有一个是可以看见的,然后再对这m个环求组合数
不难理解,但是很难想到
#include <stdio.h> #include <string.h> #define mod 1000000007 #define LL long long int C[2050][2050]; LL S[2050][2050]; void init() { memset(C,0,sizeof(C)); memset(S,0,sizeof(S)); C[0][0]=1; for(int i=1;i<=2000;i++) { C[i][0]=1; for(int j=1;j<=2000;j++) { C[i][j]=C[i-1][j-1]+C[i-1][j]; C[i][j]%=mod; } } for(int i=1;i<=2000;i++) S[i][i]=1; for(int i=1;i<=2000;i++) S[i][0]=0; for(int i=1;i<=2000;i++) { for(int j=1;j<i;j++) { S[i][j]=(i-1)*S[i-1][j]+S[i-1][j-1]; S[i][j]%=mod; } } } int main() { int T,n,f,b; init(); scanf("%d",&T); while(T--) { scanf("%d%d%d",&n,&f,&b); LL ans=S[n-1][f+b-2]*C[f+b-2][f-1]; printf("%I64d ",ans%mod); } return 0; }