题目链接:http://lightoj.com/volume_showproblem.php?problem=1326
题意:有n匹马赛跑。问有多少种不同的排名结果。可以有多匹马的排名相同。
思路:排名相同的算作一组,那么最后的排名有1、2……n组,都有可能。那么对于有m组的,首先我们需要计算出n匹马分成m组有多少种分法,这就是第二类Stirling数,设为S(n,m),设a[m]表示m!,那么最后答案就是ans=sum(S(n,i)*a[i])(1<=i<=n)。
第二类Stirling数:S(n,0)=0,S(n,1)=1,S(n,2)=2^(n-1)-1,S(n,n-1)=C(n,2),S(n,n)=1,S(n,m)=m*S(n-1,m)+S(n-1,m-1)。
int n,m;
int S[N][N],Pow[N],a[N];
void init()
{
Pow[0]=1;
int i;
for(i=1;i<=1000;i++) Pow[i]=Pow[i-1]*2%mod;
a[0]=1;
for(i=1;i<=1000;i++) a[i]=a[i-1]*i%mod;
}
int DFS(int n,int m)
{
if(m==0) return 0;
if(m==1) return 1;
if(m==2) return Pow[n-1]-1;
if(m==n-1) return n*(n-1)/2%mod;
if(m==n) return 1;
if(S[n][m]!=-1) return S[n][m];
S[n][m]=(m*DFS(n-1,m)%mod+DFS(n-1,m-1))%mod;
return S[n][m];
}
int cal()
{
if(n==1) return 1;
if(n==2) return 3;
int i,ans=0;
for(i=1;i<=n;i++)
{
ans+=DFS(n,i)*a[i]%mod;
ans%=mod;
}
return ans;
}
int main()
{
init();
clr(S,-1);
int num=0;
rush()
{
RD(n);
printf("Case %d: ",++num);
PR(cal());
}
}