当前位置: 首页 > 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;
}
http://www.lryc.cn/news/198986.html

相关文章:

  • CImageList 图像列表
  • 【OpenGL】四、坐标系统和摄像机
  • 使用vcpkg管理依赖第三库
  • Android渲染一个列表的过程,并提供动态改变样式
  • Leetcode—260.只出现一次的数字III【中等】
  • Mysql 约束,基本查询,复合查询与函数
  • web前端基础CSS------美化页面“footer”部分
  • 在中国,技术到底有多有用?
  • 《动手学深度学习 Pytorch版》 9.2 长短期记忆网络(LSTM)
  • 计算机操作系统-第十一天
  • Flutter视图原理之StatefulWidget,InheritedWidget
  • 观察者模式-对象间的联动
  • Webpack十大缺点:当过度工程化遇上简单的静态页面
  • 新手指南|如何快速参与Moonbeam Ignite
  • VR航天科普主题公园模拟太空舱体验馆vr航天模拟体验设备
  • Spring Boot OAuth 2.0整合详解
  • 安装visual studio报错“无法安装msodbcsql“
  • webGL编程指南 第三章 矩阵平移三角形.translatedTriangle_Matrix
  • 修改echarts的tooltip样式 折线图如何配置阴影并实现渐变色和自适应
  • [论文笔记] SurroundOcc: Multi-Camera 3D Occupancy Prediction for Autonomous Driving
  • 辅助驾驶功能开发-功能对标篇(16)-NOA 城市辅助系统-毫末智行
  • H3C的IRF堆叠互联关系说明
  • 货物摆放(蓝桥杯)
  • 3782: 【C3】【穷举】弹珠游戏
  • leetcode 5
  • centos中nacos设置开机自启动
  • 双指针——移动零
  • WPF中在MVVM模式下实现导航功能
  • SpringBoot面试题2:SpringBoot与SpringCloud 区别?SpringBoot和Spring、SpringMVC的区别
  • Practical Deep Raw Image Denoisingon Mobile Devices