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 的相关文章

  • 三种寻找最长递增(减)子序列的方法【LIS】

    最长递增 减 子序列 LIS 三种解法 问题 给定一个序列data 1 6 2 5 7 9 求出他的的最长递增子序列 容易看出为 1 2 5 7 9 长度为5 同时这种问题还有一些衍生问法如 最长非递增 减 增子序列 最长递减子序列等解法都
  • Codeforces-1454E Number of Simple Paths(基环树-思维)

    题目大意 给你n个点 n条边 求图中简单路径的个数 题目思路 n个点n条边 那么图中一定有一个环 拿这个图来讲 我们将两点间的关系分为4种 1 两点都在环上 简单路径的个数为2 例如2与5 2 一个点在环上一个点不在环上 简单路径个数为2
  • 证明正定矩阵的充要条件:全部顺序主子式大于0

    定理 f x T A x f x TAx f xTAx 正定的充要条件是
  • 为什么样本方差里面要除以(n-1)而不是n?

    前段日子重新整理了一下这个问题的解答 跟大家分享一下 如果有什么错误的话希望大家能够提出来 我会及时改正的 话不多说进入正题 首先 我们来看一下样本方差的计算公式 刚开始接触这个公式的话可能会有一个疑问就是 为什么样本方差要除以 n 1 而
  • 哈夫曼编码最大编码长度

    概念 层数 叶子节点为待编码的数据 根为第0层 编码长度 第 L L L层数据编码后的长度为 L L L 节点概率 若节点为叶子节点 则概率为叶子所编码数据的频率
  • Dijkstra与Bellman-Ford算法对比

    文章目录 TOC Dijkstra Dijkstra 伪代码 Dijkstra 为什么不能有负权重 Dijkstra算法复杂度 Bellman Ford算法 Bellman Ford算法伪代码 Bellman Ford判断是否有负权 Bel
  • 线性代数 - 特征向量和特征值

    今天在看到这个马汉诺拉距离的时候 又看到了这个东西 就是利用特征值来进行协方差方向上的伸缩 突然感觉到了线性代数的作用了 但是实际上 我今天看到了非常多的内容 但是都没有吸收完 很多内容都是线性代数的东西 但是这些东西我都忘了 这里先挖个坑
  • 正定Hermiltian矩阵分解的两种方法

    对于正定Hermiltian矩阵 B B B 想要求解 D D D 使其满足
  • 2020年高教社建模国赛真题A题--炉温曲线

    2020年高教社杯全国大学生数学建模竞赛题目 请先阅读 全国大学生数学建模竞赛论文格式规范 A题 炉温曲线 在集成电路板等电子产品生产中 需要将安装有各种电子元件的印刷电路板放置在回焊炉中 通过加热 将电子元件自动焊接到电路板上 在这个生产
  • Summer Holiday HDU - 1827 强连通分量+缩点

    To see a World in a Grain of Sand And a Heaven in a Wild Flower Hold Infinity in the palm of your hand And Eternity in a
  • UVa 12504 Updating a Dictionary

    Problem uva onlinejudge org index php option com onlinejudge Itemid 8 page show problem problem 3948 题意 貌似是模拟 Source Cod
  • 2的31次方和3的21次方哪个大,123组成最大的数是多少?

    123这三个数字组成最大的数是什么数 面试官告诉小孙 123这三个数字组成最大的数是什么数 我希望你能够在5分钟之内回答出来 小孙当时连想都没有想 123组成的最大数字 当然就是123了 当小孙把这个答案告诉面试官的时候 面试官摇摇头 然后
  • 论文纠错(一)

    说说最近读的几篇论文的问题 果然有的论文还是不能细细地去读 一读就发现有问题 第一个是MSPCA里面的公式 7 到公式 8 那个Sr前面的2是不应该有的 也就是推导的时候出错了 第二个是GPUTENSOR里面的Gpu product的算法
  • 树状数组理论与实现

    理论 http www cnblogs com zhangshu archive 2011 08 16 2141396 html 今天听了大神的讲课 了解了点东西 发现是之前学过的 于是试着再写一遍 include
  • 矩阵求导常用公式

    矩阵求导常用公式 1 引言 2 向量的导数 2 1 向量对标量求导 Vector by scalar 2 2 标量对向量求导 Scalar by vector 2 3 向量对向量求导 Vector by vector 3 矩阵的导数 3 1
  • kuangbin的模板

    直接链接 间接链接
  • 美国大学生数学建模竞赛赛题特点

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

    复数转换 如下图复数 由于 所以 这个就是复数的三角形式 这里 是模 是辅角 在讨论音频频域 即stft变换后的复数时 分别称为幅值和相位 根据欧拉公式 其中i是虚数符号 可得 这个公式可以方便地把幅值和相位还原回复数 进而做istft 将
  • 什么是矩阵的范数

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

    1 二次不等式 2 分式不等式 最后的例题 是为了说明第三种情况 就是 不等号右边不为0时 要先进行移项操作 将右边化为0 这样 就转化成1 2两种情况了 3 其它复杂不等式 3 1 高次不等式 3 2 绝对值不等式 3 3 根式不等式 补

随机推荐

  • 【技巧】如何在 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 将一