2020牛客暑期多校训练营Valuable Forests(动态规划,组合数学,prufer序列)

本文主要是介绍2020牛客暑期多校训练营Valuable Forests(动态规划,组合数学,prufer序列),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Valuable Forests

题目描述

在这里插入图片描述

输入描述:

在这里插入图片描述

输出描述:

在这里插入图片描述

示例1

输入

5 1000000007
2
3
4
5
107

输出

2
24
264
3240
736935633

题目大意

给定 n n n个节点,求这些节点组成的森林的所有可能中每个点的度的平方和。
要求答案 m o d mod mod给定的模数 M M M

分析

分析这题,发现难点在于,有很多很多的可能,比如说森林中树的个数、每棵树的节点分布情况、树的大小……那么,这些里面最重要的就是前两条,我们分别用数组存下。

d p [ i ] dp[i] dp[i]表示在森林中有 i i i个节点时的总方案数。
f [ i ] f[i] f[i]表示大小为 i i i的无根树的答案。

那么一看我定义的变量就知道是个 d p dp dp题。因为每次考虑最后一棵树就可以完成转移了。

  • 我们先考虑 d p [ i ] dp[i] dp[i]的转移。
    那么假如剩下 j j j个节点给最后一棵树,那么之前的方案是 d p [ i − j ] dp[i-j] dp[ij],然后对于每个方案, j j j个节点的可能是 j j − 2 j^{j-2} jj2,然后考虑节点的编号,由于没有说一定是顺序的,所以前 i i i个节点编号不一定是 1 ∼ i 1\sim i 1i,所以要乘上其组合数,运用隔板法,又因为第 i i i号节点一定要在最后一棵树,否则会重复,所以点数选择要减一,即 C i − 1 j − 1 C_{i-1}^{j-1} Ci1j1
    所以,枚举 j j j即可,如下:
    d p [ i ] = ∑ j = 1 i d p [ i − j ] ∗ j j − 2 ∗ C i − 1 j − 1 dp[i]=\mathop{\sum}\limits_{j=1}^idp[i-j]*j^{j-2}*C_{i-1}^{j-1} dp[i]=j=1idp[ij]jj2Ci1j1
  • 我们再考虑 f [ i ] f[i] f[i]的转移。
    这里要用到一个 p r u f e r prufer prufer序列,说的是一个无根树和一个序列是一一对应的。首先枚举每个节点 p p p,然后再枚举每个节点的度 j j j(度不会大于点数-1),那么答案中肯定是乘上一个 j 2 j^2 j2,然后考虑节点的编号,同上要乘上一个 C i − 2 j − 1 C_{i-2}^{j-1} Ci2j1,减二是因为在构造 p r u f e r prufer prufer的时候是剩下一条边,以防止有自环出现。然后是节点的顺序,乘上一个 ( i − 1 ) i − 1 − j (i-1)^{i-1-j} (i1)i1j
    所以枚举 p , j p,j p,j即可,如下:
    f [ i ] = ∑ p = 1 i ∑ j = 1 i − 1 j 2 ∗ C i − 2 j − 1 ∗ ( i − 1 ) i − 1 − j f[i]=\mathop{\sum}\limits_{p=1}^{i}\mathop{\sum}\limits_{j=1}^{i-1}j^2*C_{i-2}^{j-1}*(i-1)^{i-1-j} f[i]=p=1ij=1i1j2Ci2j1(i1)i1j
    然后发现 p p p在转移的时候并没有用,所以可以把那个 ∑ \sum 压掉。如下:
    f [ i ] = i ∗ ∑ j = 1 i − 1 j 2 ∗ C i − 2 j − 1 ∗ ( i − 1 ) i − 1 − j f[i]=i*\mathop{\sum}\limits_{j=1}^{i-1}j^2*C_{i-2}^{j-1}*(i-1)^{i-1-j} f[i]=ij=1i1j2Ci2j1(i1)i1j

然后就是把上面求出来的一起来算答案。设 a n s [ i ] ans[i] ans[i]表示有 i i i个节点的时候题目的答案。

  • 我们考虑 a n s [ i ] ans[i] ans[i]的转移
    首先枚举一个 j j j表示最后的一棵树有 j j j个节点,然后递推。那么显然前面的答案是 a n s [ i − j ] ∗ j j − 2 ans[i-j]*j^{j-2} ans[ij]jj2。然后是当前的答案是 d p [ j − i ] ∗ f [ j ] dp[j-i]*f[j] dp[ji]f[j]表示当前算出来的答案,然后加起来。最后一样的,要考虑节点编号的问题,乘上节点的组合数。
    所以枚举 j j j,可以得到:
    a n s [ i ] = ∑ j = 1 i C i − 1 j − 1 ∗ ( j j − 2 ∗ a n s [ i − j ] + f [ j ] ∗ d p [ i − j ] ) ans[i]=\mathop{\sum}\limits_{j=1}^{i}C_{i-1}^{j-1}*(j^{j-2}*ans[i-j]+f[j]*dp[i-j]) ans[i]=j=1iCi1j1(jj2ans[ij]+f[j]dp[ij])

做的时候先打表,然后直接输出即可,见代码,注意模。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=5010;
ll mod,C[MAXN][MAXN],dp[MAXN],f[MAXN],ans[MAXN],qp[MAXN][MAXN];//long long
ll ksm(ll a,ll p){if(p<0) return 1ll;else return qp[a][p];}//指数为负是1
int main()
{int T,nnn;scanf("%d%lld",&T,&mod);C[0][0]=1;for(int i=1;i<=5000;i++){C[i][0]=1;for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;}//用杨辉三角处理组合数for(int i=0;i<=5000;i++){qp[i][0]=1;for(int j=1;j<=5000;j++)qp[i][j]=qp[i][j-1]*i%mod;}//预处理快速幂,让你的快速幂成为O(1)dp[0]=1;for(int i=1;i<=5000;i++)for(int j=1;j<=i;j++)dp[i]=(dp[i]+dp[i-j]*ksm(j,j-2)%mod*C[i-1][j-1]%mod)%mod;//预处理dpfor(int i=1;i<=5000;i++){for(int j=1;j<i;j++)f[i]=(f[i]+j*j%mod*C[i-2][j-1]%mod*ksm(i-1,i-1-j)%mod)%mod;f[i]=f[i]*i%mod;}//预处理ffor(int i=1;i<=5000;i++)for(int j=1;j<=i;j++)ans[i]=(ans[i]+C[i-1][j-1]*(ksm(j,j-2)*ans[i-j]%mod+f[j]*dp[i-j]%mod)%mod)%mod;//算答案while(T--){scanf("%d",&nnn);printf("%lld\n",ans[nnn]);}//直接输出
}

END

要素 bug颇多……

这篇关于2020牛客暑期多校训练营Valuable Forests(动态规划,组合数学,prufer序列)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》:本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点:switch中的生成我们的label事件接着,

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

mybatis-plus 实现查询表名动态修改的示例代码

《mybatis-plus实现查询表名动态修改的示例代码》通过MyBatis-Plus实现表名的动态替换,根据配置或入参选择不同的表,本文主要介绍了mybatis-plus实现查询表名动态修改的示... 目录实现数据库初始化依赖包配置读取类设置 myBATis-plus 插件测试通过 mybatis-plu

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

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

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

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

前端 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动态组件动态