主页
搜索
最近更新
数据统计
申请密钥
批量保存
开发版网站（新前端）
系统公告
1
/
1
请查看完所有公告
题解：CF1467D Sum of Paths
最后更新于 2025-08-27 18:48:05
作者
qwqerty
分类
题解
题解
CF1467D
复制 Markdown
查看原文
转到新前端
删除文章
更新内容
duel 时通过本题。 不难发现只需要快速处理出每个点的经过次数就与权值无关了，可以 $O(1)$ 完成单点修改。 考虑对每个点统计贡献，若一条路径经过了该点，则该点会把路径分为前后两部分。 令当前点为 $i$，起点为 $s$，终点为 $e$。根据路径的可逆性，容易转化为起点为 $s$，终点为 $i$ 的方案数乘上起点为 $e$，终点为 $i$ 的方案数。 现在问题转化为已知终点求路径数，若终点为 $i$，则上一步的终点要么在 $i-1$ 要么在 $i+1$，容易列出递推式 $a_{i,j}=a_{i-1,j-1}+a_{i-1,j+1}$。 最后就是统计经过次数了，枚举第一段的长度然后与第二段相乘即可。 [提交记录](https://codeforces.com/contest/1467/submission/335488554)。
正在渲染内容...
点赞
0
收藏
0
