hdu 1028 Ignatius and the Princess III

2023-10-30

Problem

acm.split.hdu.edu.cn/showproblem.php?pid=1028

Reference

母函数(Generating function)详解 — TankyWoo
ACM 母函数专题

Meaning

将一个正整数 n 拆成若干个正整数的和,问有多少种拆分方法。

Analysis

相当于有 n 个无差别的球,放到 n 个无差别的盒里,允许空盒,也允许一个盒放多个球,问多少种放法。
一个组合数学的问题吧,母函数这个东西不知道怎么就把加法和幂的乘积对应起来了…很神奇(没有这方面基础…)。只是学习一下拆数的模版。

Code

#include <cstdio>
using namespace std;
const int N = 120;

int c[N+1]; // c[i]:i 的拆数方案数(拆分数)
int tmp[N+1];

void table()
{
    for(int i = 0; i <= N; ++i)
    {
        c[i] = 1;
        tmp[i] = 0;
    }
    for(int exp = 2; exp <= N; ++exp)
    {
        for(int i = 0; i <= N; ++i)
            for(int j = 0; j <= N - i; j += exp)
                tmp[i+j] += c[i];
        for(int i = 0; i <= N; ++i)
        {
            c[i] = tmp[i];
            tmp[i] = 0;
        }
    }
}

int main()
{
    table();
    for(int n; scanf("%d", &n) != EOF; )
        printf("%d\n", c[n]);
    return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

hdu 1028 Ignatius and the Princess III 的相关文章

  • HDU1007(最近点对问题)

    题意不难理解 就是找到最近的两个点 计算其距离 除以2就是所求的圆的半径 思路很简单 运用分治的思想 先划分区间 分别找到左右区间中的最近点对 再合并区间 找到区间间的最近点对 注意如果用qsort 进行排序可能会超时 include
  • 基础算法题——炎炎消防队(取巧、三分)

    炎炎夏日 题目描述 夏天的重庆格外地炎热 很容易起火 消防士们都全副武装 一旦发生险情就立马赶往救火 森罗是消防队中的一员 他在灭火的过程中突发奇想 如果能用退火的原理求解函数求最小值 那不就可以很容易计算了吗 翌日 森罗来到即将高考的弟弟
  • hdu 5792 World is Exploding 2016 Multi-University 5

    Problem acm hdu edu cn showproblem php pid 5792 题意 给一个序列 V 问有多少个由下标组成的四元组 a b c d 满足 a b c d a lt b c lt d Va lt Vb Vc g
  • 数的划分(递归)

    整数划分是另外的问题 题目描述 Description 将整数n分成k份 且每份不能为空 任意两种划分方案不能相同 不考虑顺序 例如 n 7 k 3 下面三种划分方案被认为是相同的 7 1 1 5 7 1 5 1 7 5 1 1 问有多少种
  • 奇异值分解方法求解最小二乘问题的原理

    文章目录 一 奇异值分解 SVD 原理 1 1 回顾特征值和特征向量 1 2 SVD的定义 1 3 求出SVD分解后的U V矩阵 1 4 SVD计算举例 1 5 SVD的一些性质 二 线性最小二乘问题 2 1 最小二乘问题复习 2 2 奇异
  • [ACM] 1016 Prime Ring Problem (深度优先搜索)

    Prime Ring Problem Problem Description A ring is compose of n circles as shown in diagram Put natural number 1 2 n into
  • hduoj 2010

    水仙花数 Problem Description 春天是鲜花的季节 水仙花就是其中最迷人的代表 数学上有个水仙花数 他是这样定义的 水仙花数 是指一个三位数 它的各位数字的立方和等于其本身 比如 153 1 3 5 3 3 3 现在要求输出
  • 5 insanely great books about mathematics you should read.

    本文转载至 http wp kjro se 2013 12 27 5 insanely great books about mathematics you should read 翻译请参考 http blog jobbole com 55
  • LaTeX 数学公式大全!

    LaTeX 数学公式大全 这里是来自一篇教程的截图 很全面
  • 数学篇(二) 方差、标准差、协方差

    1 均值 均值就是将所有的数据相加求平均 求得一个样本数据的中间值 2 标准差 标准差也被称为标准偏差 公式如下所示 简单来说 标准差是一组数平均值分散成都的一种度量 一个较大的标准差 代表大部分数值和其平均值之间差异较大 一个较小的标准差
  • 三角函数常见基本公式

    定义式 图形 正弦 sin 余弦 cos 正切 tan或tg 余切 cot或ctg 正割 sec 余割 csc 函数关系 商数关系 倒数关系 平方关系 和差角公式 二角和差公式 三角和公式 积化和差公式 倍角公式 二倍角公式 三倍角公式 四
  • hdu 3966 Aragorn's Story

    Problem acm hdu edu cn showproblem php pid 3966 Reference 树链剖分 树链剖分原理 树链剖分详解及模板 HDU3966 树链剖分 Meaning 一棵 n 个点的树 每给结点有个值 三
  • GYM-102920-L. Two Buildings(决策单调性+分治)

    题目链接 题目大意 求一段序列的 h i h j j i 的最大值 step1 转化一下题意 h i h j j i h j h i j i 令a i h i b i h i 然后全部转化为两种坐标 i a i i b i 这样题目就转化成
  • UVa 12504 Updating a Dictionary

    Problem uva onlinejudge org index php option com onlinejudge Itemid 8 page show problem problem 3948 题意 貌似是模拟 Source Cod
  • 防止sigmoid和tanh激活函数溢出的C++实现

    引言 上一期 我们介绍了softmax函数的C 实现 但是考虑到sigmoid和tanh函数也是带 e e e的次幂 所以现在我们来考虑该函数的防止溢出实现 sigmoid函数 原理 该函数的公式为 1 1
  • 先验概率及后验概率等解释

    20201010 0 引言 在学习统计学的时候 在概率估计的部分 经常会遇到最大似然估计 最大后验估计等名词 这些似然和后验 都跟贝叶斯准则中的一些名词定义有关 这里参考书籍 Think Bayes 这部书 来记录这些名词 1 由糖果例子来
  • 美国大学生数学建模竞赛赛题特点

    美国大学生数学建模竞赛赛题特点 赛题灵活度高 内容广泛 反恐 防灾 环境 健康医疗 交通 新能源等等 开放性大 评价类问题多且复杂 离散型优化问题多 除A题 如 2016B太空碎片的处理 2018D电动车充电桩的优化 2019D卢浮宫疏散路
  • 【华为OD机试真题 python】数字加减游戏【2022 Q4

    题目描述 数字加减游戏 小明在玩一个数字加减游戏 只使用加法或者减法 将一个数字s变成数字t 在每个回合中 小明可以用当前的数字加上或减去一个数字 现在有两种数字可以用来加减 分别为a b a b 其中b没有使用次数限制 请问小明最少可以用
  • 什么是矩阵的范数

    原文地址 在介绍主题之前 先来谈一个非常重要的数学思维方法 几何方法 在大学之前 我们学习过一次函数 二次函数 三角函数 指数函数 对数函数等 方程则是求函数的零点 到了大学 我们学微积分 复变函数 实变函数 泛函等 我们一直都在学习和研究
  • Gauss_Seidel method with python

    Gauss Seidel method with python from wikipedia https en wikipedia org wiki Gauss E2 80 93Seidel method import numpy as n

随机推荐

  • 【技巧】如何在 GitHub 上高效阅读源码?

    在 GitHub 上高效阅读源码的方法有以下几种 方法一 github项目页面 按键盘上的 句号 方法二 github项目页面地址栏github com 改为 github dev 方法三 github项目页面地址栏github com 改
  • 信息学奥赛一本通 1176:谁考了第k名

    题目链接 http ybt ssoier cn 8088 problem show php pid 1176 include
  • Operator ‘+‘ cannot be applied to ‘java.lang.String‘, ‘void‘的解决方法

    刚开始报下图错 是因为我在另一个类中定义有返回值void的方法 如图二 一个想要调用另一个的方法 且是字符串的类型的需要将void换成string 并将输出语句换成return 如图 记得最后一行的分号去掉
  • python循环写入excel中的不同sheet_python实现跨excel的工作表sheet之间的复制方法

    python 将test1的Sheet1通过 跨文件 复制到test2的Sheet2里面 包括谷歌没有能搜出这种问题答案 我们贴出代码 我们加载openpyxl这个包来解决 from openpyxl import load workboo
  • Java项目数据脱敏常用技术及Jasypt实战

    数据脱敏在Java项目中是一项非常重要的任务 它可以保护敏感数据 同时符合法规和隐私保护要求 在本篇博客中 我们将介绍数据脱敏的概念以及在Java项目中常用的开源框架和工具的实战应用 什么是数据脱敏 数据脱敏是指将敏感数据进行处理 使其在保
  • styled-components的配置和使用

    在react中 正常的给组件引入css文件 该css文件会直接作用于全局 使用styled components可以有效控制好css作用域 1 安装 yarn add styled components 2 配置并设置全局样式 新建一个js
  • Java实现CNN

    Java实现CNN 算法介绍 CNN的优势 卷积操作 池化操作 网络结构 训练过程 前向传播 反向传播 代码实现 数据模型类Dataset 矩阵尺寸类Size 核心操作类MathUtils Operator OperatorOnTwo接口下
  • 零基础学习Vue: 第21课 Vue 单向数据流父组件的属性值子组件如何更改:

    零基础学习Vue 第21课 Vue定义子组件template的常见3种写法 单向数据流原理 子组件不能直接修改父组件中传递的数据 如需间接改变父组件传递的数据 解决方法 可以在子组件data选项中存储父组件传递的数据之后修改子组件中的数据
  • 解决httpServletRequest.getParameter获取不到参数

    用httpServletRequest getParameter接收post请求参数 发送端content Type必须设置为application x www form urlencoded 否则会接收不到 RequestMapping
  • go语言各种hash哈希算法使用汇总(超详细代码)

    目录 前言 一 首先以md4为例 一 16进制字符串的md4 二 字符串的md4 三 16进制字符串 字符串封装 二 md4 md5 sha1 ripemd160 sha256 sha512 一 导包 二 单个使用 三 md4 md5 sh
  • 使用jsoup选择器来查找元素

    一 用途 使用jsoup解析网页 抓取手机型号和系统信息 二 获取方式 例子 获取终端制造商链接列表 return public List
  • 话题作文汇总

    一 前言 在备考的过程中 研读和学习了多篇英语话题作文 在此将其记录下来 以便加深印象 二 作文列表 Public Role Model s Rights Internet Kills Conversation Generation Gap
  • form表单的对象

    这个是关于表单 表单在HTML中是很重要的一个部分 关于表单的使用 里面的属性和方法不算很多 这里就介绍一下表单的信息 用法 document forms 是一个数组 包含了文档中所有的表单
  • Python学习之------retry(异常重试)

    在做数据抓取的时候 经常遇到由于网络问题导致的程序保存 先前只是记录了错误内容 并对错误内容进行后期处理 原先的流程 def crawl page url pass def log error url pass url try crawl
  • cocos2dx opengl入门系列四-显示图片

    运行环境 mac 10 12 2 xcode Version 8 2 1 cocos2dx x 3 13 1 代码 新建cocos2dx项目 具体操作官网有教程 新建好后 新建Test cpp 代码如下 Test cpp Texture C
  • Shell脚本编程--grep命令详解

    grep简介 grep global search regular expression RE and print out the line 全面搜索正则表达式并把行打印出来 是一种强大的文本搜索工具 它能使用正则表达式搜索文本 并把匹配的
  • window服务器端口短时间使用完导致oracle监听报错

    接到操作人员反馈系统无法登陆 然后连接到服务器 引用服务器检查服务的cpu 内存 磁盘资源都正常 从应用服务器远程数据库服务器发现不能远程 从应用服务器连接数据库连接报TNS超时 怀疑是数据库服务器的问题 从阿里云的控制台连接到数据库服务器
  • 二叉树学习笔记之B树、B+树、B*树

    动态查找树主要有二叉查找树 Binary Search Tree 平衡二叉查找树 Balanced Binary Search Tree 红黑树 Red Black Tree 都是典型的二叉查找树结构 查找的时间复杂度 O log2 N 与
  • Recyclerview列表item设置成等宽高的正方形,通过计算宽度动态赋值

    首先是效果图 然后是关键代码 onBindViewHolder 给Item元素赋值 Override public void onBindViewHolder ViewHolder holder int position 获取内容layou
  • hdu 1028 Ignatius and the Princess III

    Problem acm split hdu edu cn showproblem php pid 1028 Reference 母函数 Generating function 详解 TankyWoo ACM 母函数专题 Meaning 将一