傳送門

?

k < 20

k這么小，隨便dp一下就好了。。。

dp[i][j][k]表示從i到j(luò)經(jīng)過k個(gè)點(diǎn)的方案數(shù)

4重循環(huán)。。

?

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

把給定的圖轉(zhuǎn)為鄰接矩陣，即A(i,j)=1當(dāng)且僅當(dāng)存在一條邊i->j。令C=A*A，那么C(i,j)=ΣA(i,k)*A(k,j)，實(shí)際上就等于從點(diǎn)i到點(diǎn)j恰好經(jīng)過1個(gè)點(diǎn)的路徑數(shù)（枚舉k為中轉(zhuǎn)點(diǎn)）。類似地，C*A的第i行第j列就表示從i到j(luò)經(jīng)過2個(gè)點(diǎn)的路徑數(shù)。同理，如果要求經(jīng)過k步的路徑數(shù)，我們只需要二分求出A^k即可。

?

#include <cstdio> #include <cstring> #define p 1000int n, m, k, T;struct Matrix {int n, m;int a[21][21];Matrix(){n = m = 0;memset(a, 0, sizeof(a));} }ans;inline Matrix operator * (Matrix x, Matrix y) {int i, j, k;Matrix ans;ans.n = x.n;ans.m = y.m;for(i = 1; i <= x.n; i++)for(j = 1; j <= y.m; j++)for(k = 1; k <= y.n; k++)ans.a[i][j] = (ans.a[i][j] + x.a[i][k] * y.a[k][j]) % p;return ans; }inline Matrix operator ^ (Matrix x, int y) {int i;Matrix ans;ans.n = ans.m = n;for(i = 1; i <= n; i++) ans.a[i][i] = 1;for(; y; y >>= 1){if(y & 1) ans = ans * x;x = x * x;}return ans; }int main() {int i, x, y;while(~scanf("%d %d", &n, &m) && n + m){Matrix c;c.n = c.m = n;for(i = 1; i <= m; i++){scanf("%d %d", &x, &y);c.a[x + 1][y + 1] = 1;}scanf("%d", &T);for(i = 1; i <= T; i++){scanf("%d %d %d", &x, &y, &k);ans = c ^ k;printf("%d\n", ans.a[x + 1][y + 1]);}}return 0; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/zhenghaotian/p/7491366.html

總結(jié)

以上是生活随笔為你收集整理的[HDU2157]How many ways??（DP + 矩阵优化）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。