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)
blank

相关推荐

  • vue v-if 多条件_vue条件渲染

    vue v-if 多条件_vue条件渲染v-if在模板中,可以根据条件进行渲染。条件用到的是v-if、v-else-if以及v-else来组合实现的。示例代码如下:<divid="app"><p

  • mysql将字符转换成数字

    mysql将字符转换成数字在操作mysql时,经常需要将字符转换成数字,这一步虽然简单,但不常用的话也很容易忘记,现将在网上找到的方法记录如下:1.将字符的数字转成数字,比如’0’转成0可以直接用加法来实现例如:将pony表中的d进行排序,可d的定义为varchar,可以这样解决select*fromponyorderby(d+0)2.在进行ifnull处理时,比如ifnull(a/b,’0

  • unity drawcall怎么看_unity scrollview

    unity drawcall怎么看_unity scrollview在实际项目开发中,提起unity优化,肯定是有DrawCall的相关内容的,下面就讲解一下什么是DrawCall以及如何对DrawCall进行优化操作。一、什么是DrawCall?    在unity中,每次CPU准备数据并通知GPU的过程就称之为一个DrawCall。    具体过程就是:设置颜色–&gt;绘图方式–&gt;顶点坐标–&gt;绘制–&gt;结束…

  • msdos分区是什么_msdos_partition

    msdos分区是什么_msdos_partition硬盘分区及格式化本例要求熟悉硬盘分区结构,使用fdisk分区工具在磁盘/dev/vdb上按以下要求建立分区:采用默认的msdos分区模式1、第1个分区/dev/vdb1的大小为200MiB2、第2个分区/dev/vdb2的大小为2000MiB3、第3个分区/dev/vdb3的大小为1000MiB,完成分区后4、能够配置开机自动挂载/dev/vdb2分区…

  • Bootstrap开发框架界面的调整处理

    Bootstrap开发框架界面的调整处理

  • elasticsearch部署方案_elasticsearch安装配置

    elasticsearch部署方案_elasticsearch安装配置除非您使用Elasticsearch进行开发和测试,否则创建和维护Elasticsearch集群将是一项会占用您大量时间的任务。Elasticsearch是一个极其强大的搜索和分析引擎,其强大的部分在于能够对其进行扩展以获得更好的性能和稳定性。本教程将提供有关如何设置Elasticsearch集群的一些信息,并将添加一些操作技巧和最佳实践来帮助您入门。但应该强调的是,每个Elasticsearch设置可能会因多种因素而异,包括服务器上的工作负载、索引数据量、硬件规格,甚至操作员的经验。什么

    2022年10月10日

发表回复

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

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