缘起
日常浪费生命~ sdutoj 3911 指定长度路径数
分析
1 | Time Limit: 1000 ms Memory Limit: 65536 KiB |
令
1 | dp[u][v][k]是从u到v长度为k的路径的条数. 答案是\Sigma_{u,v}{dp[u][v][k]} |
令G_{k}[u[v] 为矩阵{dp[u][v][k]} u,v是有向图中所有顶点. 则
1 | Gk=G_{k-x}*G_{x} |
其中
1 | G0是单位矩阵,G1=邻接矩阵 |
注意, 为什么不对x求和? 例如4=1+3=2+2,因为一条路是1+3,一条路是2+2,那么后面的2+2其实就是一条1+3啊(从一个2挪一个顶点到2去就变成了1+3了)~ 这样就会重复计算了. 所以不需要对x求和.
其实本题的模型好像当时我自学组合数学的时候见过~
所以
1 | Gk=G1^k |
复杂度是 O(N^3*logk). 最后的答案就是Gk中所有元素的和.
注意下面代码的 #pragma 编译选项. 不然爆栈, 应该可以将其置为全局变量. 但是懒的搞了,直接暴力过
1 | //#include "stdafx.h" |
ac情况
RunID | Nick Name | Problem | Result | Time | Memory | Language | Code Len | Submission Time |
---|---|---|---|---|---|---|---|---|
6556229 | yfs | 3911 | Accepted | 92 ms | 3144 KiB | g++ | 1183 B | 2019-09-20 10:26:37 |
Powered By Valine
v1.5.2
v1.5.2