[HDU2157]How many ways??（DP + 矩阵优化）

传送门

k < 20

k这么小，随便dp一下就好了。。。

dp[i][j][k]表示从i到j经过k个点的方案数

4重循环。。

但是如果k很大就不好弄了

把给定的图转为邻接矩阵，即A(i,j)=1当且仅当存在一条边i>j。令C=A*A，那么C(i,j)=ΣA(i,k)*A(k,j)，实际上就等于从点i到点j恰好经过1个点的路径数（枚举k为中转点）。类似地，C*A的第i行第j列就表示从i到j经过2个点的路径数。同理，如果要求经过k步的路径数，我们只需要二分求出A^k即可。

#include <cstdio> #include <cstring> #define p 1000 int n, m, k, T; struct Matrix }ans; inline Matrix operator * (Matrix x, Matrix y) inline Matrix operator ^ (Matrix x, int y) return ans; } int main() scanf("%d", &T); for(i = 1; i <= T; i++) } return 0; }

　　

上一篇：链接

下一篇：[luoguP3068] [USACO13JAN]派对邀请函Party Invitations（stl大乱交）

---

DP 矩阵