HDU 4658 Integer Partition(整数拆分)

时间:2021-11-15 00:44:16

题目链接: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(整数拆分)的更多相关文章

  1. hdu 4651 Partition &amp&semi;&amp&semi; hdu 4658 Integer Partition——拆分数与五边形定理

    题目:http://acm.hdu.edu.cn/showproblem.php?pid=4651 参考:https://blog.csdn.net/u013007900/article/detail ...

  2. HDU 4658 Integer Partition (2013多校6 1004题)

    Integer Partition Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others ...

  3. hdu 4658 Integer Partition

    五角数定理!!可以参考这个http://www.cnblogs.com/xin-hua/p/3242428.html  代码如下: #include<iostream> #include& ...

  4. hdu 4651 Partition&lpar;整数拆分&plus;五边形数&rpar;

    Partition Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total ...

  5. &lbrack;LeetCode&rsqb; Integer Break 整数拆分

    Given a positive integer n, break it into the sum of at least two positive integers and maximize the ...

  6. HDU-4651 Partition 整数拆分&comma;递推

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4651 题意:求n的整数拆为Σ i 的个数. 一般的递归做法,或者生成函数做法肯定会超时的... 然后要 ...

  7. 343 Integer Break 整数拆分

    给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化. 返回你可以获得的最大乘积.例如,给定 n = 2,返回1(2 = 1 + 1):给定 n = 10,返回36(10 = 3 ...

  8. &lbrack;LeetCode&rsqb; 343&period; Integer Break 整数拆分

    Given a positive integer n, break it into the sum of at least two positive integers and maximize the ...

  9. HDU 1398 Square Coins 整数拆分变形 母函数

    欢迎参加——BestCoder周年纪念赛(高质量题目+多重奖励) Square Coins Time Limit: 2000/1000 MS (Java/Others)    Memory Limit ...

随机推荐

  1. iOS 之UITextFiled&sol;UITextView小结

    一:编辑被键盘遮挡的问题 参考自:http://blog.csdn.net/windkisshao/article/details/21398521 1.自定方法 ,用于移动视图 -(void)mov ...

  2. jndi配置数据源

    jndi(java Naming and DirectoryInterface,java命名和目录接口)是一组在Java应用中访问命名和目录服务的API. 命名服务将名称和对象联系起来,使得我们可以用 ...

  3. 什么是Elasticsearch

    一个采用Restfull API 标准的高扩展性和高可用性的实时数据分析的全文搜索工具 Elasticsearch 涉及到的一些概念: 1.Node(节点): 单个的装有Elasticsearch服务 ...

  4. (中级篇 NettyNIO编解码开发)第八章-Google Protobuf 编解码-2

    8.1.2    Protobuf编解码开发 Protobuf的类库使用比较简单,下面我们就通过对SubscrjbeReqProto进行编解码来介绍Protobuf的使用. 8-1    Protob ...

  5. IDL 结构体

    1.创建结构体 (1) 命名结构体 创建具有两个成员变量A.B的命名为str1的结构体 IDL> struct1={str1,a:1,b:2} IDL> help,struct1,/str ...

  6. pflag如何使用

    1 为何我对这个库感兴趣呢? 因为我想看看Kubernetes的源码,Kubernetes,Hugo啥的都是那这个解析的命令行参数 2 安装 go get github.com/spf13/pflag ...

  7. TRIO-basic指令--MOVEMODIFY

    Syntax: MOVEMODIFY(position) Parameters: position: Absolute position for the current move to complet ...

  8. istio-jaeger-spring boot调用链配置

    istio-jaeger-spring boot调用链配置 虽然,istio ingress controller已经生成了jaeger 记录所需要的信息,但是多个分布式之间没法清晰记录相互之间的依赖 ...

  9. FactoryMethod工厂方法模式&lpar;创建型模式&rpar;

    1.工厂方法模式解决的问题 现在有一个抽象的游戏设施建造系统,负责构建一个现代风格和古典风格的房屋和道路. 前提:抽象变化较慢,实现变化较快(不稳定) 整个抽象的游戏设施建造系统相对变化较慢,本例中只 ...

  10. stuff函数(转)

    在上篇博文中提到了stuff函数 在这篇博文中对stuff函数进行了详解 本片博文系转载,但对原文顺序做了下调整 示例 以下示例在第一个字符串 abcdef 中删除从第 2 个位置(字符 b)开始的三 ...