SSL 2386 序列#线性动态规划#

2024-02-11 06:38

本文主要是介绍SSL 2386 序列#线性动态规划#,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

比赛


题目

这里写图片描述
这里写图片描述


分析

dp,状态转移方程: f [ i ] [ j ] 表 示 第 j 位 的 数 字 是 i 的 方 案 f[i][j]表示第j位的数字是i的方案 f[i][j]ji
f [ i ] [ j ] + = f [ ( i 的 因 数 ) ] [ j − 1 ] ( 逆 推 ) f[i][j]+=f[(i的因数)][j-1](逆推) f[i][j]+=f[(i)][j1]
f [ i ∗ ( 1 t o n / j ) ] [ j ] + = f [ i ] [ j − 1 ] ( 顺 推 ) f[i*(1 _{to}n/j)][j]+=f[i][j-1](顺推) f[i(1ton/j)][j]+=f[i][j1]()


逆推代码

#include <cstdio>
#include <cstring>
using namespace std;
struct node{int x,y,next;}e[100001];
int f[2002][2002],n,m,k,ans,ls[2001];
int main(){scanf("%d%d",&n,&k);for (int i=1;i<=n;i++) f[i][1]=1;for (int i=1;i<=n;i++)for (int j=1;j<=i;j++)if (i%j==0) e[++m].x=i,e[m].y=j,e[m].next=ls[e[m].x],ls[e[m].x]=m;//邻接表优化for (int j=2;j<=k;j++)for (int i=1;i<=n;i++){int t=ls[i];while (t){f[i][j]=(f[i][j]+f[e[t].y][j-1])%1000000007;t=e[t].next;}}for (int i=1;i<=n;i++) ans=(ans+f[i][k])%1000000007;printf("%d",ans);return 0;
} 

顺推代码

#include <cstdio>
#include <cstring>
#define p 1000000007
using namespace std;
int f[2002][2002],n,m,ans;
int main(){scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) f[i][1]=1;for (int j=2;j<=m;j++)for (int i=1;i<=n;i++)for (int k=1;k<=n/i;k++) f[i*k][j]=(f[i][j-1]+f[i*k][j])%p;for (int i=1;i<=n;i++) ans=(ans+f[i][m])%p;printf("%d",ans);return 0;
} 

这篇关于SSL 2386 序列#线性动态规划#的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/699093

相关文章

基于Canvas的Html5多时区动态时钟实战代码

《基于Canvas的Html5多时区动态时钟实战代码》:本文主要介绍了如何使用Canvas在HTML5上实现一个多时区动态时钟的web展示,通过Canvas的API,可以绘制出6个不同城市的时钟,并且这些时钟可以动态转动,每个时钟上都会标注出对应的24小时制时间,详细内容请阅读本文,希望能对你有所帮助...

Vue中动态权限到按钮的完整实现方案详解

《Vue中动态权限到按钮的完整实现方案详解》这篇文章主要为大家详细介绍了Vue如何在现有方案的基础上加入对路由的增、删、改、查权限控制,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、数据库设计扩展1.1 修改路由表(routes)1.2 修改角色与路由权限表(role_routes)二、后端接口设计

nginx生成自签名SSL证书配置HTTPS的实现

《nginx生成自签名SSL证书配置HTTPS的实现》本文主要介绍在Nginx中生成自签名SSL证书并配置HTTPS,包括安装Nginx、创建证书、配置证书以及测试访问,具有一定的参考价值,感兴趣的可... 目录一、安装nginx二、创建证书三、配置证书并验证四、测试一、安装nginxnginx必须有"-

前端 CSS 动态设置样式::class、:style 等技巧(推荐)

《前端CSS动态设置样式::class、:style等技巧(推荐)》:本文主要介绍了Vue.js中动态绑定类名和内联样式的两种方法:对象语法和数组语法,通过对象语法,可以根据条件动态切换类名或样式;通过数组语法,可以同时绑定多个类名或样式,此外,还可以结合计算属性来生成复杂的类名或样式对象,详细内容请阅读本文,希望能对你有所帮助...

Nginx实现动态封禁IP的步骤指南

《Nginx实现动态封禁IP的步骤指南》在日常的生产环境中,网站可能会遭遇恶意请求、DDoS攻击或其他有害的访问行为,为了应对这些情况,动态封禁IP是一项十分重要的安全策略,本篇博客将介绍如何通过NG... 目录1、简述2、实现方式3、使用 fail2ban 动态封禁3.1 安装 fail2ban3.2 配

Vue3中的动态组件详解

《Vue3中的动态组件详解》本文介绍了Vue3中的动态组件,通过`component:is=动态组件名或组件对象/component`来实现根据条件动态渲染不同的组件,此外,还提到了使用`markRa... 目录vue3动态组件动态组件的基本使用第一种写法第二种写法性能优化解决方法总结Vue3动态组件动态

Android 悬浮窗开发示例((动态权限请求 | 前台服务和通知 | 悬浮窗创建 )

《Android悬浮窗开发示例((动态权限请求|前台服务和通知|悬浮窗创建)》本文介绍了Android悬浮窗的实现效果,包括动态权限请求、前台服务和通知的使用,悬浮窗权限需要动态申请并引导... 目录一、悬浮窗 动态权限请求1、动态请求权限2、悬浮窗权限说明3、检查动态权限4、申请动态权限5、权限设置完毕后

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列(LCS)问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动

关于最长递增子序列问题概述

《关于最长递增子序列问题概述》本文详细介绍了最长递增子序列问题的定义及两种优化解法:贪心+二分查找和动态规划+状态压缩,贪心+二分查找时间复杂度为O(nlogn),通过维护一个有序的“尾巴”数组来高效... 一、最长递增子序列问题概述1. 问题定义给定一个整数序列,例如 nums = [10, 9, 2

python实现简易SSL的项目实践

《python实现简易SSL的项目实践》本文主要介绍了python实现简易SSL的项目实践,包括CA.py、server.py和client.py三个模块,文中通过示例代码介绍的非常详细,对大家的学习... 目录运行环境运行前准备程序实现与流程说明运行截图代码CA.pyclient.pyserver.py参