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

P2151 HH 去散步

问题:

给定一个无向图,\(n\) 个点编号为 \([0,n-1]\)\(m\) 条边。从 \(s\) 出发,走 \(k\) 条边,其中相邻的两步不能走同一条边,求最后停在终点 \(t\) 的方案数。


放在 noip 模拟赛 T2 还多测卡常 (?)。考场思路,有点冗余,没有什么高妙的方法。

首先把编号变为 \([1,n]\)

先不考虑重边,考虑朴素 dp。

\(f_{u,i}\) 表示从 \(s\) 出发走 \(i\) 条边且符合题目要求,到达 \(u\) 的方案数。初始时 \(f_{s,0}=1\)

\(f_{u,i}=\sum_{v\in E_u}f_{v,i-1}\)

然后转移 \(k\) 轮,第 \(i\) 轮对每个 \(u\in[1,n]\)\(f_{u,i}\) 进行更新。

显然这个方程是错的,因为出现不符合题目要求的情况,考虑容斥,减去不合法情况。

不合法情况形如从 \(u\) 走到 \(v\) 又从同一条边走回 \(u\)

假设最后走回 \(u\) 共走了 \(x\) 条边。

\(u\) 转移到 \(v\)\(f_{v,x-1}\) 的贡献为 \(f_{u,x-2}\),而上述方程式将这多出来不合法的 \(f_{u,x-2}\) 又算进 \(f_{u,x}\) 了。

也就是说每有一个 \(u\) 可以转移的点 \(v\),也就是点 \(u\) 的度数记为 \(d_u\)\(f_{u,x}\) 都会算多一次 \(f_{u,x-2}\)

所以我们可以将方程式改为:

\(f_{u,i}=\sum_{v\in E_u}(f_{v,i-1}-f_{u,i-2})=\sum_{v\in E_u}f_{v,i-1}-d_u\cdot f_{u,i-2}\)

但是还是错的,发现答案少了很多

思考一下,假设有不合法路径 \(s\to \cdots \to v \to u\to v\to u\)

同样假设最后走回 \(u\) 共走了 \(i\) 条边。

会发现第二次走到 \(v\) 时,\(f_{v,i-1}\) 将从 \(v\to u\to v\) 贡献的不合法方案数 \(f_{v,i-3}\) 给除去了,也就是 \(u\) 并没有将完整的 \(f_{u,i-2}\) 转移给 \(f_{v,i-1}\)

但是第二次走回 \(u\) 时我们仍然认为 \(f_u\)\(f_v\) 多转移了 \(f_{u,i-2}\),于是就会多除去 \(f_{v,i-3}\) 的方案数。

然后就到了这题的关键

如果存在上述多除去了 \(f_{v,i-3}\) 的点那么必然满足 \(t_v<t-2\),其中 \(t\) 是当前的转移轮数,\(t_i\) 是从 \(s\) 走到 \(i\) 经过的最小边数。

但是其实可以看作所有与 \(u\) 相连的点 \(v\) 都多除去了 \(f_{v,i-3}\) 因为不满足上述条件的点,其 \(f_{v,i-3}\) 必定为 0。

假定经过转移所有 \(f_{v}\) 都不包含 \(v\to u\to v\) 的非法方案。

::::info[?]
因为 \(t_u\) 轮时转移 \(f_v\) 均不包含 \(v\to u\to v\) 的情况。而后按照上述思路可以保证每次转移后所有 \(v\to u\to v\) 的非法贡献在 \(f_v\) 中除去,所以这样假设是可行的。
::::

发现多除去的 \(\sum_{v\in son_u}f_{v,i-3}\) 刚好是 \(f_{u,i-2}\)

于是转移式变为:

\(f_{u,i}=\sum_{v\in E_u}f_{v,i-1}-d_u\cdot f_{u,i-2}+f_{u,i-2} \\=\sum_{v\in E_u}f_{v,i-1}-(d_u-1)\cdot f_{u,i-2}\)

有了这个转移式做法就显然了,看到 \(k\le 10^9\) 第一反应就是矩阵加速。

还有一点要注意,就是对于起点 \(s\) 的前两次转移要特殊处理,
因为对于除 \(s\) 外的任意点 \(u\),第二次走到 \(u\) 时必定会出现 \(s\to\cdots\to v\to u\to v\to u\) 也就是上文多除去了 \(f_{u,i-3}\) 的情况。

但第二次走到 \(s\) 时只会出现 \(s\to u\to s\) 所以时不会出现多除去的情况的,也就是

\(f_{s,2}=\sum_{v\in E_s}f_{v,1}-d_s\cdot f_{s,0}=\sum_{v\in E_s}f_{v,1}-d_s\)

仅有当转移轮数 \(\ge 4\) 时才会对起点 \(s\) 出现多除去的情况。所以前两轮对于起点 \(s\) 的转移会有所不同,而后转移式跟其余点相同(第三轮 \(f_{s,1}\) 必定为 0 所以没影响)。

这是没有考虑重边的情况,考虑重边。

变化不大,直接相当于多了一个点转移过来。

\(f_{u,i}=\sum_{v\in E_u}cnt_{u,v} f_{v,i-1}-(d-1)\cdot f_{u,i-2}\)

其中 \(d_u=\sum_{v\in E_u}cnt_{u,v},cnt_{u,v}\) 表示 \(u,v\) 这条边出现了几次,对 \(s\) 特殊转移的方程也相应稍作修改即可。

下面矩阵加速的部分应该就很好推了:

因为要用到前两轮的状态,于是构造转移到第 \(i\) 轮的矩阵:

\[A_i= \begin{bmatrix} f_{1,i},f_{1,i-1},f_{2,i},f_{2,i-1},\cdots \end{bmatrix} \]

表示转移到当前轮各个状态的值,初始( \(i=0\) ):

\[A_0= \begin{bmatrix} 0,0,0,0,\cdots 1,0,0,\cdots \end{bmatrix} \]

仅有 \(f_{s,0}\) 位置上为 1。

每次转移就相当于乘上 \(2n\times 2n\) 的矩阵:

\[B= \begin{bmatrix} 0,1,0,0,0,0,\cdots\\ (1-d_1),0,0,0,0,0,\cdots\\ 0,0,0,1,0,0,\cdots\\ 0,0,(1-d_2),0,0,0,\cdots \end{bmatrix} \]

假设当前为第 \(i\) 轮转移。

形式化的,将所有 \(u\in[1,n],(2u-1,2u)\) 的位置置为 1,表示将 \(f_{u,i-1}\) 处置为 \(f_{u,i}\)

\(u\in[1,n],(2u,2u-1)\) 的位置置为 \(1-d_u\) 表示从 \(f_{u,i}\) 除去多余的 \((d_u-1)\cdot f_{u,i-2}\)

\(u,v\) 有边相连,将 \((u,v)\)\((v,u)\) 置为 \(cnt_{u,v}\),表示将 \(\sum_{v\in son_u}cnt_{u,v}f_{v,i-1}\) 转移到 \(f_{u,i}\)

因为上面说前两轮转移起点 \(s\) 要特殊处理,所以定义矩阵 \(C\) 为在矩阵 \(B\) 的基础上将 \((2s,2s-1)\) 置为 \(-d_s\)

最后答案就是:

\[A_k= \left\{\begin{array}{lr}A_0\cdot C^k(k\le 2)\\A_0\cdot C^2\cdot B^{k-2}(k>2)\end{array} \right.\]

\(A_k\) 中对应的 \(f_{t,k}\)

矩阵快速幂优化一下,就可以做到 \(O(n^3\log k)\) 常数较大可以通过本题。

::::info[多组询问的优化]

对于 加强版 的多组询问,可以先预处理 \(B\)\(2^i\) 次幂的矩阵 \(B'_i\),然后对 \(k-2\) 做二进制拆分,先计算 \(A=A_0\cdot C^2\),拆出来每一位就是 \(A\cdot B'_i\) 就变为向量乘矩阵的形式,于是单次乘法复杂度降为 \(O(n^2)\) 总复杂度 \(O(qn^2\log k)\)

::::

呃呃,然后就结束了吧。写的有点丑,不过有了思路手推一遍也不难。

http://www.hskmm.com/?act=detail&tid=32091

相关文章:

  • 2025年钢结构建材厂家最新推荐排行榜,彩钢瓦,镀锌板,折弯件,C型钢,Z型钢,压型瓦,楼承板,钢结构安装,次檩条公司推荐
  • 2025年发电机组厂家最新权威推荐榜:柴油/燃气/船用/静音箱式/移动拖车/集装箱发电机组,上柴/玉柴/潍柴/康明斯/沃尔沃/道依茨/帕金斯/MTU品牌全覆盖
  • 2025年铣刀厂家最新权威推荐榜:雕刻机铣刀/金刚石铣刀/木工铣刀/绝缘材料铣刀/碳纤维铣刀/亚克力铣刀/金属加工铣刀/铝合金铣刀/石墨铣刀/不锈钢铣刀/金属切削铣刀/电木铣刀/塑胶铣刀/PC铣刀
  • 2025年下半年权威信息公布:西安学区房/书包房/五大名校/交大书包新楼盘口碑推荐榜前十强出炉,高得房率/推荐好房/地铁口/小高层/低总价/低单价/高性价比/高赠送/四代宅
  • 第六届大数据、人工智能与物联网工程国际会议(ICBAIE 2025)
  • .NET 10中GC(垃圾收集器)更新
  • 【转】扫盲:Windows桌面应用开发框架:原生、跨平台、云桌面
  • vxe-table v4版本使用注意事项
  • ​​电容瞬态放电原理:大电流的产生机制深度解析​
  • Chrome浏览器离线版下载,谷歌(Google)浏览器离线安装包下载,手机版,Mac版,window版都有,不上网也可以安装
  • 基于Java+Springboot+Vue开发的在线摄影预约管理系统源码+运行步骤
  • 2025 年超微粉碎机厂家最新推荐榜:聚焦企业专利技术、品质管控及知名客户合作案例的权威解析
  • 若干树形dpの总结
  • 2025 年最新推荐!国内冷库厂商综合实力排行榜出炉,涵盖冷冻 / 装配式 / 超低温等多类型冷库解决方案
  • 2025 年景观石厂家最新推荐榜单:千层石 / 泰山石 / 鹅卵石等各类石材企业全面盘点,助力客户精准选择优质景观石品牌
  • python之函数
  • 剑指offer-35、数组中的逆序对
  • 2025 年最新推荐!西宁种植牙医院推荐榜单:助您精准选靠谱口腔机构
  • 2025 年太阳能厂家最新推荐:全场景系统企业综合实力榜,含热水 / 发电 / 光伏热等领域优质品牌测评
  • 苦逼,通宵肝了两个月!测试开发导航网站终于上线了!
  • 鸿蒙应用开发从入门到实战(二十三):一文搞懂ArkUI弹性布局
  • 2025 金属复合板厂家最新推荐排行榜:实力厂家产能定制服务全景解析,选购指南必备
  • CCPC2024成都 游记(VP) 未完成以及一些找补的话
  • CF1439C Greedy Shopping
  • 完整教程:AI应用生成平台:数据库、缓存与存储
  • CCPC2022绵阳 游记(VP)
  • 2025 年电缆桥架生产厂家最新推荐排行榜:含北方 / 河北 / 瓦楞 / 防火 / 模压 / 镀锌桥架品牌及合作案例盘点
  • 2025 年胰岛素泵厂家最新推荐排行榜:国产实力厂家技术、口碑及全场景适配方案全景解析软针植入/平衡式留置针/无异物感胰岛素泵厂家推荐
  • 2025 年国内磨床厂家最新推荐榜:聚焦平面磨床外圆磨床等品类,助力企业精准选优质设备
  • 2025 年加工中心厂家最新推荐榜:覆盖立式、卧式、龙门及 850 等多规格设备,帮采购方高效选实力厂商