hdu 4472 Count (递推)「建议收藏」

hdu 4472 Count (递推)

大家好,又见面了,我是全栈君。

Count

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1756    Accepted Submission(s): 1133




Problem Description
Prof. Tigris is the head of an archaeological team who is currently in charge of an excavation in a site of ancient relics.

This site contains relics of a village where civilization once flourished. One night, examining a writing record, you find some text meaningful to you. It reads as follows.

“Our village is of glory and harmony. Our relationships are constructed in such a way that everyone except the village headman has exactly one direct boss and nobody will be the boss of himself, the boss of boss of himself, etc. Everyone expect the headman is considered as his boss’s subordinate. We call it relationship configuration. The village headman is at level 0, his subordinates are at level 1, and his subordinates’ subordinates are at level 2, etc. Our relationship configuration is harmonious because all people at same level have the same number of subordinates. Therefore our relationship is …”

The record ends here. Prof. Tigris now wonder how many different harmonious relationship configurations can exist. He only cares about the holistic shape of configuration, so two configurations are considered identical if and only if there’s a bijection of n people that transforms one configuration into another one.

Please see the illustrations below for explanation when n = 2 and n = 4.



hdu 4472 Count (递推)「建议收藏」


The result might be very large, so you should take module operation with modules 10
9 +7 before print your answer.
 


Input
There are several test cases.

For each test case there is a single line containing only one integer n (1 ≤ n ≤ 1000).

Input is terminated by EOF.
 


Output
For each test case, output one line “Case X: Y” where X is the test case number (starting from 1) and Y is the desired answer.
 


Sample Input
   
   
1 2 3 40 50 600 700

 


Sample Output
   
   
Case 1: 1 Case 2: 1 Case 3: 2 Case 4: 924 Case 5: 1998 Case 6: 315478277 Case 7: 825219749

 

对于每一个合法图形。记最底层个数为j,则再添加一层添加的个数必须是j的倍数。能够用dp[i][j]表示i个点最底层为j个时的个数,对于数据范围内的N遍历得到答案。(属于“我为人人”型的递推关系)

dp[i][j]–>dp[i+j*k][j*k](k=1…N)

#include <iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
#define N 1010
#define LL __int64
const int mod=1000000007;
int f[N][N],ans[N];
void inti()
{
    int i,j,k;
    memset(f,0,sizeof(f));
    f[1][1]=1;
    for(i=1;i<=1000;i++)
    {
        for(j=1;j<=1000;j++)
        {
            if(f[i][j]==0)     //由当前合法状态推得其它状态
                continue;
            for(k=1;k<=1000;k++)
            {
                int t1=j*k;
                int t2=t1+i;
                if(t2>1000)
                    break;
                f[t2][t1]+=f[i][j];
                if(f[t2][t1]>=mod)
                    f[t2][t1]%=mod;
            }
        }
    }
    for(i=1;i<=1000;i++)
    {
        int tmp=0;
        for(j=1;j<=i;j++)
            tmp=(tmp+f[i][j])%mod;
        ans[i]=tmp;
    }
}
int main()
{
    int n,cnt=1;
    inti();
    while(scanf("%d",&n)!=-1)
    {
        printf("Case %d: %d\n",cnt++,ans[n]);
    }
    return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116626.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • db2codepage作用_dbcc checktable

    db2codepage作用_dbcc checktable1、db2变量查看  db2set-all  (connecttodbanme)getdbcfg  db2pd-osinfo这个命令很强大哦  2、db2c变量的设置用命令  db2set变量=value  可以参考一下:  客户端:  db2codepage=1386(简体中文)  db2country

  • Solr使用入门指南

    Solr使用入门指南

  • Python画图爱心_python语言画爱心

    Python画图爱心_python语言画爱心都说程序员不浪漫,上次看到一个程序员小哥给自己老婆开发了一个专属的APP。其实程序员还有更多美好的事情可以做,比如,给你喜欢的妹纸,用代码的方式去表白(当然可能还有一些前戏啥的,自己结合实际场景再渲染下),直接上代码:print’\n’.join([”.join([(‘loveyou'[(x-y)%8]if((x*0.05)**2+(y*0.1)**2-1)**3-(x*0.05)**2*(y…

  • web.xml中listener作用及使用

    web.xml中listener作用及使用

  • matlab如何随机选颜色,Matlab 画图修饰-随机线条和随机颜色

    matlab如何随机选颜色,Matlab 画图修饰-随机线条和随机颜色转载自:http://www.zhaoyanpeng.cn/archives/237当需要对同一曲线不同参数下进行模拟时需要不同的颜色来加以区分:上例根据RGB颜色,来实现不同颜色曲线的组合,考虑到matlab画图中,颜色分量是以1/255的步长变化的,但是相邻颜色过于接近,因此我们可以选取rand随机数的形式,来实现颜色的随机变化;延伸:MATLAB有一个叫颜色映象的数据结构来代表颜色值。颜色映…

  • SQL嵌套查询_sql嵌套查询返回多个字段

    SQL嵌套查询_sql嵌套查询返回多个字段说到嵌套查询,首先得理解嵌套查询是什么意思,简单来说就是,一个查询语句可以嵌套在另外一个查询语句的where子句中。外层的查询称为父查询(主查询),内层的查询称为子查询(从查询)。嵌套查询的工作方式是由内向外的,即先进行内层查询,外层查询则利用内层查询的结果集作为条件进行查询。当然,嵌套查询不仅仅是select语句的专属,它还可以用在update、insert、delete语句中。如(update…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号