当前位置: 首页 > news >正文

atcoder [Road of the King] 题解(DP好题)

题面

简要题意:有一个 n n n 个点的图,目前一条边都没有。有一个人在 1 1 1 号点要进行 m m m 次移动, 终点不必是 1 1 1 号点。加入第 i i i 次的从 u u u 移动到了 v v v, 那么 u u u v v v 之间出现一条有向边。问一共有多少序列满足最后 n n n 个点组成的图 是一个强联通图。答案对 1 0 9 + 7 10^9 + 7 109+7 取模。 1 ≤ n , m ≤ 300 1 \leq n,m \leq 300 1nm300

分析:
        注意到一个性质,就是如果要形成强联通图,那么所有的点都要和 1 1 1 能够相互到达。因为是从 1 1 1 出发,所以序列里所有的点 1 1 1 都可以到达,只要这 n n n 个点都能到达 1 1 1 ,那么这 n n n 个点组成的图就一定是一个强联通图。 我们根据这条性质来划分状态。

        设 d p i , j , k dp_{i, j, k} dpi,j,k 表示当前已经走了 i i i 步,涉及到的点有 j j j 个, 跟 1 1 1 形成强联通的点有 k k k 个。注意当前点可以看做是没有跟 1 1 1 形成强联通的点。我们考虑转移:

        如果下一步走到了一个没有跟 1 1 1 形成强联通但是已经设计的点,那么有 ( j − k ) × d p i , j , k → d p i + 1 , j , k (j - k) \times dp_{i,j, k} \rightarrow dp_{i+1, j, k} (jk)×dpi,j,kdpi+1,j,k

        如果下一步走到了一个跟 1 1 1 形成强联通的点,那么所有涉及到的点都会和 1 1 1 形成强联通,有 k × d p i , j , k → d p i + 1 , j , j k \times dp_{i, j, k} \rightarrow dp_{i+1, j, j} k×dpi,j,kdpi+1,j,j

        如果下一步走到了一个还未涉及到的点,那么有 ( n − j ) × d p i , j , k → d p i + 1 , j + 1 , k (n-j) \times dp_{i,j, k} \rightarrow dp_{i+1,j+1,k} (nj)×dpi,j,kdpi+1,j+1,k

        最后输出 d p m , n , n dp_{m,n,n} dpm,n,n 就好了。

#include<bits/stdc++.h>
#define N 310
#define LL long long
#define mod 1000000007
using namespace std;
int n, m;
LL dp[N][N][N];// dp[i][j][k] 表示走了i步,已经拓展了j个点, 能与1形成强联通的点数为k 的方案数 
int main(){cin >> n >> m;dp[0][1][1] = 1LL;for(int i = 0; i <= m; i++){for(int j = 1; j <= n; j++){for(int k = 1; k <= j; k++){dp[i + 1][j + 1][k] = (dp[i + 1][j + 1][k] + dp[i][j][k] * (1LL * (n - j))) % mod;dp[i + 1][j][k] = (dp[i + 1][j][k] + dp[i][j][k] * (1LL * (j - k))) % mod;dp[i + 1][j][j] = (dp[i + 1][j][j] + dp[i][j][k] * (1LL * k)) % mod;}}}cout << dp[m][n][n] << endl;return 0;
}

相关文章:

atcoder [Road of the King] 题解(DP好题)

题面 简要题意&#xff1a;有一个 n n n 个点的图&#xff0c;目前一条边都没有。有一个人在 1 1 1 号点要进行 m m m 次移动&#xff0c; 终点不必是 1 1 1 号点。加入第 i i i 次的从 u u u 移动到了 v v v&#xff0c; 那么 u u u 到 v v v 之间出现一条有向边。问…...

CImageList 图像列表

一、CImageList类Create函数参数解析 BOOL Create(int cx,int cy,UINT nFlags,int nInitial,int nGrow ); 1.1&#xff09; cx,cy&#xff1a;图片的实际像素宽与高&#xff1b; nFlags&#xff1a;创建图像列表的类型,包括4/8/16/24/32/位色&#xff1b; nFlags确定建立图…...

【OpenGL】四、坐标系统和摄像机

坐标转换 文章目录 坐标转换坐标系统的转换局部空间(Local Space&#xff09;->世界空间(World Space)世界空间(World Space)->观察空间&#xff08;View Space/View Space&#xff09;裁剪空间(Clip Space)MVP矩阵 坐标系统的转换 了解坐标系统和空间变换之前需要先了解…...

使用vcpkg管理依赖第三库

文章目录 使用vcpkg管理依赖第三库vcpkg安装vcpkg经典模式使用从仓库列表搜索依赖项从某个基线版本的列表中查询某个依赖项信息安装依赖库 vcpkg清单模式的使用vcpkg清单模式的使用例子说明 使用vcpkg管理依赖第三库 vcpkg 有两种操作模式&#xff1a;经典模式和清单模式。 在…...

Android渲染一个列表的过程,并提供动态改变样式

1、index.xml 布局文件&#xff0c;我省略了其他代码&#xff0c;我们需要recyclerview保证在规定范围内&#xff0c;如果列表元素过多可以滑动 <LinearLayoutandroid:layout_width"match_parent"android:layout_height"match_parent"android:layout_…...

Leetcode—260.只出现一次的数字III【中等】

2023每日刷题&#xff08;三&#xff09; Leetcode—260.只出现一次的数字III 借助lowbit的解题思想 参考的灵茶山艾府大神的题解 实现代码 /*** Note: The returned array must be malloced, assume caller calls free().*/ int* singleNumber(int* nums, int numsSize, in…...

Mysql 约束,基本查询,复合查询与函数

文章目录 约束空属性约束默认值约束zerofill主键约束自增长约束唯一键约束外键约束 查询select的执行顺序单表查询排序 updatedelete整张表的拷贝复合语句group by分组查询 函数日期函数字符串函数数学函数其他函数 复合查询合并查询union 约束 空属性约束 两个值&#xff1a…...

web前端基础CSS------美化页面“footer”部分

一&#xff0c;实验代码 <!DOCTYPE html> <html><head><meta charset"utf-8"><title>关于我们</title><style type"text/css">#footer{margin: 10px 0px;background: #f5f5f5;border: top 1px solid #eee ;}#f…...

在中国,技术到底有多有用?

&#x1f64c;秋名山码民的主页 &#x1f602;oi退役选手&#xff0c;Java、大数据、单片机、IoT均有所涉猎&#xff0c;热爱技术&#xff0c;技术无罪 &#x1f389;欢迎关注&#x1f50e;点赞&#x1f44d;收藏⭐️留言&#x1f4dd; 获取源码&#xff0c;添加WX 目录 前言1.…...

《动手学深度学习 Pytorch版》 9.2 长短期记忆网络(LSTM)

解决隐变量模型长期信息保存和短期输入缺失问题的最早方法之一是长短期存储器&#xff08;long short-term memory&#xff0c;LSTM&#xff09;。它与门控循环单元有许多一样的属性。长短期记忆网络的设计比门控循环单元稍微复杂一些&#xff0c;却比门控循环单元早诞生了近 2…...

计算机操作系统-第十一天

目录 1、进程的状态 创建态与就绪态 运行态 终止态 新建态 结束态 进程状态的转换 进程的组织方式 链接方式&#xff08;常见&#xff09; 索引方式&#xff08;少见&#xff09; 本节思维导图 1、进程的状态 创建态与就绪态 1、进程正在被创建时&#xff0c;处于…...

Flutter视图原理之StatefulWidget,InheritedWidget

目录 StatefulElement1. 构造函数2. build3. _firstBuild3. didChangeDependencies4. setState InheritedElement1. Element类2. _updateInheritance3. InheritedWidget数据向下传递3.1 dependOnInheritedWidgetOfExactType 4. InheritedWidget的状态绑定4.1. ProxyElement 在f…...

观察者模式-对象间的联动

有个商城小程序&#xff0c;用户希望当有新品上市的时候能通知他们。这样用户就可以不要时刻盯着小程序了。在这个场景中&#xff0c;用户向小程序订阅了一个服务——发送新品短信。小程序在有新品上线时负责向订阅客户发出这个消息。 这就是发布-订阅模式&#xff0c;也称观察…...

Webpack十大缺点:当过度工程化遇上简单的静态页面

&#x1f90d; 前端开发工程师&#xff08;主业&#xff09;、技术博主&#xff08;副业&#xff09;、已过CET6 &#x1f368; 阿珊和她的猫_CSDN个人主页 &#x1f560; 牛客高级专题作者、在牛客打造高质量专栏《前端面试必备》 &#x1f35a; 蓝桥云课签约作者、已在蓝桥云…...

新手指南|如何快速参与Moonbeam Ignite

Moonbeam Ignite是社区熟悉的有奖链上交互活动&#xff0c;将有300万枚GLMR作为生态激励注入Moonbeam生态系统&#xff0c;体验MoonbeamMoonbeam生态的应用即可获取相应Token奖励。Beamex/Beamswap、Moonwell和Gamma作为首批参与Moonbeam Ignite的三家项目方&#xff0c;将在活…...

VR航天科普主题公园模拟太空舱体验馆vr航天模拟体验设备

VR航天航空体验馆巡展是一项非常受欢迎的展览活动&#xff0c;可以让公众在现场体验到航天飞行的乐趣。 普乐蛙VR展览组织者会设计一个航天航空主题的VR体验馆&#xff0c;并在馆内设置各种航天航空相关的展示内容&#xff0c;如太空舱、火箭发射、星际航行等。 其次&#xff0…...

Spring Boot OAuth 2.0整合详解

目录 一、Spring Boot 2.x 示例 1、初始化设置 2、设置重定向URI 3、配置 application.yml 4、启动应用程序 二、Spring Boot 2.x 属性映射 二、CommonOAuth2Provider 三、配置自定义提供者&#xff08;Provider&#xff09;属性 四、覆盖 Spring Boot 2.x 的自动配置…...

安装visual studio报错“无法安装msodbcsql“

在安装visual studio2022时安装完成后提示无法安装msodbcsql, 查看日志文件详细信息提示&#xff1a;指定账户已存在。 未能安装包“msodbcsql,version17.2.30929.1,chipx64,languagezh-CN”。 搜索 URL https://aka.ms/VSSetupErrorReports?qPackageIdmsodbcsql;PackageActi…...

webGL编程指南 第三章 矩阵平移三角形.translatedTriangle_Matrix

我会持续更新关于wegl的编程指南中的代码。 当前的代码不会使用书中的缩写&#xff0c;每一步都是会展开写。希望能给后来学习的一些帮助 git代码地址 &#xff1a;git 接着 上一节 中 我们使用矩阵进行旋转&#xff0c;这次我们使用矩阵实现位移 <!DOCTYPE html> <…...

修改echarts的tooltip样式 折线图如何配置阴影并实现渐变色和自适应

图片展示 一、引入echarts 这里不用多解释 vue里使用 import echarts from “echarts”; html页面引用js文件或用script标签引用 二、定义一个具有宽高的dom div <div id"echart-broken" style"width:400px;height: 200px;"></div>三、定义…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习

禁止商业或二改转载&#xff0c;仅供自学使用&#xff0c;侵权必究&#xff0c;如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

Spring Boot + MyBatis 集成支付宝支付流程

Spring Boot MyBatis 集成支付宝支付流程 核心流程 商户系统生成订单调用支付宝创建预支付订单用户跳转支付宝完成支付支付宝异步通知支付结果商户处理支付结果更新订单状态支付宝同步跳转回商户页面 代码实现示例&#xff08;电脑网站支付&#xff09; 1. 添加依赖 <!…...

麒麟系统使用-进行.NET开发

文章目录 前言一、搭建dotnet环境1.获取相关资源2.配置dotnet 二、使用dotnet三、其他说明总结 前言 麒麟系统的内核是基于linux的&#xff0c;如果需要进行.NET开发&#xff0c;则需要安装特定的应用。由于NET Framework 是仅适用于 Windows 版本的 .NET&#xff0c;所以要进…...

FOPLP vs CoWoS

以下是 FOPLP&#xff08;Fan-out panel-level packaging 扇出型面板级封装&#xff09;与 CoWoS&#xff08;Chip on Wafer on Substrate&#xff09;两种先进封装技术的详细对比分析&#xff0c;涵盖技术原理、性能、成本、应用场景及市场趋势等维度&#xff1a; 一、技术原…...