• 如果喜欢本站,您可以按CTRL+D收藏本站,方便下次访问。

  • 欢迎来自五湖四海的朋友,期待为您分享有价值的资源 :oops:

POJ 3088-Push Botton Lock 斯特灵数

POJ解题 第四度 10年前 (2010-08-21) 41次浏览 0个评论 扫描二维码

file

读半天不解其意,傻算了半天才把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 %I64dn“,i+1,in,ans[in]);
    }

    return 0;
}

本网站采用BY-NC-SA 4.0协议进行授权 | 转载请注明原文链接:https://www.disidu.com/post/1011.html
如果觉得本文对您有帮助或者您心情好~可以微信打赏支持一下本站:↓↓↓
喜欢 (0)
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址