首页 > 其他分享 >codeforces 414B B. Mashmokh and ACM(dp)

codeforces 414B B. Mashmokh and ACM(dp)

时间:2023-04-23 21:32:51浏览次数:47  
标签:题目 int MAX LL codeforces ACM include dp


题目链接:

codeforces 414B


题目大意:

定义一个序列,前一项能够整除后一项,给定这个序列中数的取值范围和序列的长度,问有多少种构造方法。


题目分析:

  • 我们定义状态dp[i][j]为前i项已经确定且第i项为j的方案数。
  • 转移方程 dp[i][j]=∑k|jdp[i−1][k]
  • 复杂度O(n⋅k)

AC代码:

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#define MAX 2007

using namespace std;

typedef long long LL;

int n,k;
const LL mod=1e9+7;
LL dp[MAX][MAX];

int main ( )
{
    while ( ~scanf ( "%d%d" , &n , &k ) )
    {
        memset ( dp , 0 , sizeof ( dp ) );
        for ( int i = 1 ; i <= n ; i++ )
            dp[1][i] = 1;
        for ( int i = 2 ; i <= k ; i++ )
            for ( int j = 1 ; j <= n ; j++ )
                for ( int k = 1 ; k*k<=j ; k++ )
                {
                    if ( j%k ) continue;
                    dp[i][j] += dp[i-1][k];
                    dp[i][j] %= mod;
                    int x = j/k;
                    if ( x == k ) continue;
                    dp[i][j] += dp[i-1][x];
                    dp[i][j] %= mod;
                }
        int ans = 0;
        for ( int i = 1 ; i <= n ; i++ )
        {
            ans += dp[k][i];
            ans %= mod;
        }
        printf ( "%d\n" , ans );
    }
}


标签:题目,int,MAX,LL,codeforces,ACM,include,dp
From: https://blog.51cto.com/u_7936627/6218756

相关文章

  • codeforces 573B B. Bear and Blocks(线段树+dp)
    题目链接:codeforces573B题目大意:给出n个连续塔,每个塔有高度hi,每次取走最外层的块,问需要多少次操作能够拿光所有的块。题目分析:首先我们可以知道第一次操作时,对于每个塔的变化满足如下的公式:hi=min(hi−1,hi−1,hi+1)每次操作都满足如下的递推式,我们递推一下得到第k次操作第i......
  • codeforces 267A A. Subtractions(辗转相除)
    题目链接:codeforces267A题目大意:给出一个数对,(a,b)每次用较大的减较小的,直到出现0为止,问要进行多少次操作。题目分析:大的减小的操作,可以利用取模优化过程,也就是辗转相除,商是操作次数,余数是下一段与之前较小的数继续进行操作的数,水题不做赘述。AC代码:#include<iostream>#include......
  • codeforces 225B B. Well-known Numbers(数论+二分+贪心+构造)
    题目链接:codeforces225B题目大意:定义f(k,n)为类似菲波那契数推导,只不过变为前k项的和,然后给出一个数s,利用k-菲波那契数构造出一个不重复的集合的元素和为s,集合的规模大于1题目分析:首先因为菲波那契数的增长速度快的吓人,所以给的数据范围109很快就能达到,我们得到O(n)的构造出所有的......
  • 插头dp
    插头dp是什么,这里只有插头在状态压缩动态规划中,有一类是需要记录若干个元素的联通情况,称之为基于连通性状态压缩的动态规划,也就是插头dp在大部分棋盘状压dp中,状态划分可以依据行或列进行划分,行列之间相对独立,但有时却不行,例如让你在棋盘中对联通块进行操作,下图的联通块是无......
  • m基于BP译码算法的QC-LDPC误码率matlab仿真,对比不同译码迭代次数的误码率性能
    1.算法仿真效果matlab2022a仿真结果如下: 2.算法涉及理论知识概要       LDPC码是麻省理工学院RobertGallager于1963年在博士论文中提出的一种具有稀疏校验矩阵的分组纠错码。几乎适用于所有的信道,因此成为编码界近年来的研究热点。它的性能逼近香农极限,且描述和实现......
  • m基于BP译码算法的QC-LDPC误码率matlab仿真,对比不同译码迭代次数的误码率性能
    1.算法仿真效果matlab2022a仿真结果如下:2.算法涉及理论知识概要LDPC码是麻省理工学院RobertGallager于1963年在博士论文中提出的一种具有稀疏校验矩阵的分组纠错码。几乎适用于所有的信道,因此成为编码界近年来的研究热点。它的性能逼近香农极限,且描述和实现简单,易于进行理论分......
  • Quasi Binary---codeforces
    #QuasiBinary##题面翻译**题目描述**给出一个数n,你需要将n写成若干个数的和,其中每个数的十进制表示中仅包含0和1。问最少需要多少个数**输入输出格式**输入格式:一行一个数n(1≤n≤10^6)输出格式:最少的数的个数,并给出一种方案。##题目描述Anumberiscalledquasib......
  • IPV6-NDP邻居发现协议
    概述 NDP(NeighborDiscoveryProtocol,邻居发现协议)是IPv6的一个关键协议,它组合了IPv4中的ARP、ICMP路由器发现和ICMP重定向等协议,并对它们作了改进。   IPv6ND(IPv6NeighborDiscovery,IPv6邻居发现)协议使用五种类型的ICMPv6消息,实现下面一些功能:地址解析、验证邻居是否......
  • 云原生之部署wordpress博客及设置圣诞主题风格
    (云原生之部署wordpress博客及设置圣诞主题风格)一、前言1.本次实践目的1.使用docker部署wordpress网站2.配置圣诞主题风格2.wordpress介绍WordPress是使用PHP语言开发的博客平台,用户可以在支持PHP和MySQL数据库的服务器上架设属于自己的网站。也可以把WordPress当作一个......
  • Codeforces Round 866 (Div. 2)(A~C)
    目录A.Yura'sNewName题意思路代码B.JoJo'sIncredibleAdventures题意思路代码C.ConstructiveProblem题意思路代码A.Yura'sNewName题意在字符串\(s\)中添加"_"或者"^",使得\(s\)中的任意字符都必须为"_"或者"^^"的一部分,求最少要添加的字符数量思路当字符串......