最短路径树上分层dp的一类套路吧
题目大意
幽香这几天学习了魔法,准备建造一个大型的时空传送阵。
幽香现在可以在幻想乡的n个地点建造一些传送门,如果她建造了从地点a与地点b之间的传送门,那么从a到b和从b到a都只需要单位1的时间。
同时这些地点之间在地理上是非常遥远的,因此来往他们必须使用传送门。
现在幽香想要问你,有多少种建造传送门的方案,使得地点1和地点n之间的最短距离恰好为k?两个方案不同当且仅当建造的传送门的集合不同。不能建造节点到自身的传送门,两个点之间也最多造一个传送门。
$n,k \le 100$
题目分析
特殊性质在于每条边长度都为1,这点让人联想到bfs;而看到最短路则自然想起最短路径树。
那么我们就考虑按照bfs序dp这张图的最短路径树,也就是分层往下dp。在分层dp的树中,跨层的点不能连边;邻层及同层的点可以随意连边,最终目标是把$n$号点安排在$k+1$层,如果还有剩下的点则接下去随意安排。
不过这里有一种省去分类讨论的小trick:我们不计标号地计算剩下$n-1$个点的方案数,而由于这$n-1$个点是完全等价的,相当于最后再把总方案数乘以$(n-1)^{-1}$即可。
用$f_{i,t,l}$表示构造了$i$层,总共使用了$t$个节点(包括1号点),当前层有$l$个节点的方案数。转移时枚举上一层有$p$个节点。边界条件$f_{1,1,1}=1$
大致形状如上所示。
考虑p到l的转移:首先从$n-(t-l)$个点中取出$l$个点,取出的每个点向$p$个点连边有$2^p-1$种方案;$l$个点同层连边有$2^{l\choose 2}$种方案。
最后再枚举所有情况统计一趟即可。
#include<bits/stdc++.h>
#define MO 1000000007
typedef long long ll;
const int maxn = ; int n,k,fac[maxn],facinv[maxn],mi[maxn];
ll f[maxn][maxn][maxn],ans; int qmi(ll a, ll b)
{
int ret = ;
for (a%=MO; b; b>>=,a=1ll*a*a%MO)
if (b&) ret = 1ll*ret*a%MO;
return ret;
}
int C(int n, int m)
{
if (n < m) return ;
return 1ll*fac[n]*facinv[n-m]%MO*facinv[m]%MO;
}
int main()
{
scanf("%d%d",&n,&k);
facinv[] = facinv[] = fac[] = mi[] = ;
for (int i=; i<=; i++)
facinv[i] = MO-1ll*MO/i*facinv[MO%i]%MO;
for (int i=; i<=; i++)
mi[i] = 2ll*mi[i-]%MO, fac[i] = 1ll*fac[i-]*i%MO, facinv[i] = 1ll*facinv[i-]*facinv[i]%MO;
f[][][] = ;
for (int i=; i<=k+; i++)
for (int t=i; t<=n; t++)
for (int l=; l<=t-i+; l++)
for (int p=; p<=t-l-i+; p++)
f[i][t][l] = (f[i][t][l]+1ll*f[i-][t-l][p]*qmi(mi[p]-, l)%MO*C(n-t+l, l)%MO*qmi(, C(l, ))%MO)%MO;
for (int i=; i<=n; i++)
for (int j=; j<=n; j++)
if (f[k+][i][j])
ans = (ans+1ll*f[k+][i][j]*j%MO*qmi(, C(n-i, ))%MO*qmi(, 1ll*j*(n-i)%MO))%MO;
printf("%lld\n",1ll*ans*qmi(n-, MO-)%MO);
return ;
}
END
【bfs分层图 dp】hihocoder#1147 : 时空阵的更多相关文章
-
BZOJ_1195_[HNOI2006]最短母串_AC自动机+BFS+分层图
BZOJ_1195_[HNOI2006]最短母串_AC自动机+BFS+分层图 Description 给定n个字符串(S1,S2,„,Sn),要求找到一个最短的字符串T,使得这n个字符串(S1,S2, ...
-
codeforces 677D(分层图dp)
Codeforces 677D 传送门:https://codeforces.com/contest/677/problem/D 题意: 给你一个n*m的方格图,每个点有一个权值val,现在要求你从坐 ...
-
「hdu 4845 」拯救大兵瑞恩 [CTSC 1999](状态压缩bfs &; 分层图思想)
首先关于分层图思想详见2004的这个论文 https://wenku.baidu.com/view/dc57f205cc175527072208ad.html 这道题可以用状态压缩,我们对于每一把钥匙 ...
-
POJ3635 Full Tank? 优先队列BFS or 分层图最短路 or DP?
然而我也不知道这是啥啊...反正差不多...哪位大佬给区分一下QWQ.. 好的,我把堆的<写反了..又调了一个小时..你能不能稳一点.... 记录状态:所在位置u,油量c,花费w 扩展状态: 1 ...
-
POJ 3635 Full Tank? 【分层图/最短路dp】
任意门:http://poj.org/problem?id=3635 Full Tank? Time Limit: 1000MS Memory Limit: 65536K Total Submis ...
-
BZOJ_1916_[Usaco2010 Open]冲浪_分层图+拓扑排序+DP
BZOJ_1916_[Usaco2010 Open]冲浪_分层图+拓扑排序+DP Description 受到秘鲁的马丘比丘的新式水上乐园的启发,Farmer John决定也为奶牛们建 一个水上乐园. ...
-
[luogu1073 Noip2009] 最优贸易 (dp || SPFA+分层图)
传送门 Description C 国有n 个大城市和m 条道路,每条道路连接这n 个城市中的某两个城市.任意两个 城市之间最多只有一条道路直接相连.这m 条道路中有一部分为单向通行的道路,一部分 为 ...
-
线性dp,分层图思想
题目大意:给你一串数字,一串运算符,求递推用完运算符时答案的最大值----->线性dp dp[i][j] i表示所用数字的个数 j表示所用字符的个数 分层图思想 所有字符必须用完 所以取最后 ...
-
一本通 高手训练 1782 分层图 状压dp
LINK:分层图 很精辟的一道题 写的时候没带脑子 导致搞了半天不知道哪错了. 可以想到状压每次到某一层的状态 然后这个表示方案数 多开一维表示此时路径条数的奇偶即可. 不过显然我们只需要知道路径条数 ...
随机推荐
-
带你快速进入.net core的世界
[申明]:本人.NET Core小白.Linux小白.MySql小白.nginx小白.而今天要说是让你精通Linux ... 的开机与关机.nginx安装与部署.Core的Hello World .. ...
-
python selenium无法最大化窗口
问题原因:报错提示cannot get automation extension根据各种调试,发现是对应版本不对,上图发现selenium的版本是57.0.2987.133,需要driver为2.29 ...
-
章节十、7-Xpath---Xpath中绝对路径相对路径的区别
以下演示操作以该网址中的内容为例:https://learn.letskodeit.com/?_ga=2.143454972.85111248.1555037144-697706367.1554889 ...
-
tornado关于AsyncHTTPClient的使用笔记
先来一段同步的httpclient使用代码 url = 'https://www.baidu.com/' http_client = HTTPClient() response = http_clie ...
-
WCF 基于 WinForm 宿主 发布
ServiceHost Host = new ServiceHost(typeof(ServiceHTTP)); //绑定 System.ServiceModel.Channels.Binding h ...
-
flex中的注释
flex 2.5.35论文写到此处,遇到点麻烦,随手翻了本书,说下flex中的注释问题.中文版的35页有点问题,所以纠正下. 下面是p31示例 fb2_2.l /* 读取多个文件 */ %option ...
-
如何正确的把 Java 数组 Array 转为列表 List
最近想把 java 数组转成 List,网上普遍的答案都是 Arrays.asList: String[] a = new String[] {"hello", "wor ...
-
windows环境下封装条件wait和signal
linux 环境有提供好的pthread_cond_wait() 和 phread_signal().pthread_broadcast() windows需要自己封装,利用semophore控制线程 ...
-
LOJ #6277. 数列分块入门 1-分块(区间加法、单点查询)
#6277. 数列分块入门 1 内存限制:256 MiB时间限制:100 ms标准输入输出 题目类型:传统评测方式:文本比较 上传者: hzwer 提交提交记录统计测试数据讨论 2 题目描述 给出 ...
-
神勇的产品经理之路系列-10 PD三板斧
一.三板斧的来源及理解 三板斧 古代长兵器的一种,又名“马战斧”.相传为程咬金所用.斧阔五寸,柄长七尺.用法有劈.砍.剁.搂.截.撩.云.片.推.支等. 比喻义:解决问题的方法不多,但却非常管用. ...