Push Botton Lock poj 3088斯特灵数

读半天不解其意,傻算了半天才把sample凑出来.其实很简单,连高精度都没有.第一类斯特灵数S(n,m)就是把n元集合分成m部的个数,有递推关系S(n,m)=S(n-1,m-1)+mS(n-1,m).所求还要全排列一下.再乘以m!就可以了累加1~B个数全部用上,就是结果.F(B)=sum(C(B,i)*(Sum(Stir( i,j )* j ! ) ) )就是结果.其中下标i从1变到B,j从1变到i.
/*Source CodeProblem: 3088        User: y09shendazhi
Memory: 164K        Time: 0MS
Language: C++        Result: Accepte/

Source Code
*/

#include 
<iostream>
using namespace std;
// /n\
// | |
// \m/
__int64 comb(__int64 m,__int64 n)
{
    
if(n<m)
        
return 0;
    __int64 result
=1;
    m
=m<n-m?m:n-m;
    
for(__int64 i=1;i<=m;i++)
        result
=(result*(n-m+i))/i;    
    
return result;
}

__int64 fun(__int64 n)
{
    __int64 ans
=1;
    
for(__int64 i=1;i<=n;i++)
        ans
*=i;
    
return ans;
}

int main(__int64 argc, char *argv[])
{
    __int64 i,j,k;
    __int64 stir[
15][15]={0};
    
for(i=1;i<12;i++)
    
{
        stir[i][
1]=1;
        
for(j=2;j<i;j++)
        
{
            stir[i][j]
=stir[i-1][j-1]+j*stir[i-1][j];
        }

        stir[i][i]
=1;
    }

    __int64 ans[
12]={0,1};
    
for(i=2;i<12;i++)
    
{
        
        
for(j=1;j<=i;j++)
        
{
            __int64 temp
=0;
            
for(k=1;k<=j;k++)
            
{
                temp
+=stir[j][k]*fun(k);
            }

            ans[i]
+=temp*comb(j,i);
        }

    }

    __int64 
in=0;
    __int64 t
=0;
    scanf(
"%d",&t);
    
for(i=0;i<t;i++)
    
{
        scanf(
"%d",&in);
        printf(
"%I64d %I64d %I64d\n",i+1,in,ans[in]);
    }



    
    
return 0;
}

posted on 2010-08-21 18:20 若余 阅读(374) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2010年8月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

统计

常用链接

留言簿

随笔档案(16)

搜索

最新随笔

最新评论

评论排行榜