题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4658
题意:给出n、k。求n的拆分方案数。要求拆分中每个数不超过k。
i64 f[N];
void init()
{
f[0]=f[1]=1; f[2]=2;
int i,j,k,t;
for(i=3;i<N;i++) for(j=1;;j++)
{
FOR0(k,2)
{
if(!k) t=(3*j*j-j)/2;
else t=(3*j*j+j)/2;
if(t>i) break;
if(j&1) f[i]=(f[i]+f[i-t])%mod;
else f[i]=(f[i]-f[i-t])%mod;
}
if(t>i) break;
}
}
int n,m;
i64 cal()
{
i64 ans=f[n];
int i,j=-1,k;
for(i=1;;i++,j=-j)
{
k=(3*i*i-i)/2*m;
if(k>n) break;
ans=(ans+f[n-k]*j)%mod;
k=(3*i*i+i)/2*m;
if(k>n) break;
ans=(ans+f[n-k]*j)%mod;
}
if(ans<0) ans+=mod;
return ans;
}
int main()
{
init();
rush()
{
RD(n,m);
PR(cal());
}
}
HDU 4658 Integer Partition(整数拆分)的更多相关文章
-
hdu 4651 Partition &;&; hdu 4658 Integer Partition——拆分数与五边形定理
题目:http://acm.hdu.edu.cn/showproblem.php?pid=4651 参考:https://blog.csdn.net/u013007900/article/detail ...
-
HDU 4658 Integer Partition (2013多校6 1004题)
Integer Partition Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others ...
-
hdu 4658 Integer Partition
五角数定理!!可以参考这个http://www.cnblogs.com/xin-hua/p/3242428.html 代码如下: #include<iostream> #include& ...
-
hdu 4651 Partition(整数拆分+五边形数)
Partition Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total ...
-
[LeetCode] Integer Break 整数拆分
Given a positive integer n, break it into the sum of at least two positive integers and maximize the ...
-
HDU-4651 Partition 整数拆分,递推
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4651 题意:求n的整数拆为Σ i 的个数. 一般的递归做法,或者生成函数做法肯定会超时的... 然后要 ...
-
343 Integer Break 整数拆分
给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化. 返回你可以获得的最大乘积.例如,给定 n = 2,返回1(2 = 1 + 1):给定 n = 10,返回36(10 = 3 ...
-
[LeetCode] 343. Integer Break 整数拆分
Given a positive integer n, break it into the sum of at least two positive integers and maximize the ...
-
HDU 1398 Square Coins 整数拆分变形 母函数
欢迎参加——BestCoder周年纪念赛(高质量题目+多重奖励) Square Coins Time Limit: 2000/1000 MS (Java/Others) Memory Limit ...
随机推荐
-
iOS 之UITextFiled/UITextView小结
一:编辑被键盘遮挡的问题 参考自:http://blog.csdn.net/windkisshao/article/details/21398521 1.自定方法 ,用于移动视图 -(void)mov ...
-
jndi配置数据源
jndi(java Naming and DirectoryInterface,java命名和目录接口)是一组在Java应用中访问命名和目录服务的API. 命名服务将名称和对象联系起来,使得我们可以用 ...
-
什么是Elasticsearch
一个采用Restfull API 标准的高扩展性和高可用性的实时数据分析的全文搜索工具 Elasticsearch 涉及到的一些概念: 1.Node(节点): 单个的装有Elasticsearch服务 ...
-
(中级篇 NettyNIO编解码开发)第八章-Google Protobuf 编解码-2
8.1.2 Protobuf编解码开发 Protobuf的类库使用比较简单,下面我们就通过对SubscrjbeReqProto进行编解码来介绍Protobuf的使用. 8-1 Protob ...
-
IDL 结构体
1.创建结构体 (1) 命名结构体 创建具有两个成员变量A.B的命名为str1的结构体 IDL> struct1={str1,a:1,b:2} IDL> help,struct1,/str ...
-
pflag如何使用
1 为何我对这个库感兴趣呢? 因为我想看看Kubernetes的源码,Kubernetes,Hugo啥的都是那这个解析的命令行参数 2 安装 go get github.com/spf13/pflag ...
-
TRIO-basic指令--MOVEMODIFY
Syntax: MOVEMODIFY(position) Parameters: position: Absolute position for the current move to complet ...
-
istio-jaeger-spring boot调用链配置
istio-jaeger-spring boot调用链配置 虽然,istio ingress controller已经生成了jaeger 记录所需要的信息,但是多个分布式之间没法清晰记录相互之间的依赖 ...
-
FactoryMethod工厂方法模式(创建型模式)
1.工厂方法模式解决的问题 现在有一个抽象的游戏设施建造系统,负责构建一个现代风格和古典风格的房屋和道路. 前提:抽象变化较慢,实现变化较快(不稳定) 整个抽象的游戏设施建造系统相对变化较慢,本例中只 ...
-
stuff函数(转)
在上篇博文中提到了stuff函数 在这篇博文中对stuff函数进行了详解 本片博文系转载,但对原文顺序做了下调整 示例 以下示例在第一个字符串 abcdef 中删除从第 2 个位置(字符 b)开始的三 ...