Atcoder Educational DP Contest R Walk 题解

题目链接：Atcoder Educational DP Contest R Walk

题意：

给一张 $N$ 个结点的有向简单图，给出邻接矩阵 $A$ ，求长度为 $K$ 的路径条数，答案对 $10^9+7$ 取模。

$1 \le N \le 50,1\le K \le 10^{18}$ ， $a_{i,j}$ is 0 or 1 ，$a_{i,i}=0$

设 $f_{k,i,j}$ 表示 $i$ 到 $j$ 路径长为 $k$ 的方案数，则

$$f_{k,i,j}=\sum_{(s,j) \in E} f_{k-1,i,s}$$

之所以不从 $k-t$ 转移，而从 $k-1$ 转移，是因为可能存在重复计数

比如这张图

就可能重复计数

上面的式子可以进一步化简

$$f_{k,i,j} = \sum_{1\le s \le n} f_{k-1,i,s}\times A_{s,j}$$

这个形式是不是很熟悉？

$$f^{0}_{i,j} = A_{i,j} \\f^{k}_{i,j}=\sum f^{k-1}_{i,t}\times A_{t,j}$$

考虑矩阵快速幂优化dp

关于为什么可以用矩阵快速幂，这里解释一下

由于矩阵乘法的定义为

$$(AB)_{i,j}=\sum_{k=1}^{m}A_{i,k}B_{k,j}\quad i\in[1,n],j\in[1,p]$$

而这里的形式和矩阵乘法的定义完全一致

因此我们可以看作三个矩阵的关系，即

$$f^k=f^{k-1}\times A$$

稍微化一化柿子，可得

$$f^k = f^{k-2} A^2 = \dots = A^k$$

至此可知，答案就是

$$\sum_{1\le i,j \le n}f^{k}_{i,j} = \sum_{1\le i,j \le n}A^{k}_{i,j}$$

时间复杂度 $O(n^3 \log k)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef vector< vector<int> > mat;
#define N (int)()

const int mod=1e9+7;
void add(int &x,int y){x+=y; if(x>=mod) x-=mod;}
mat mul(mat A,mat B)
{
    int n=A.size(),m=A[0].size(),p=B[0].size();
    mat C(n,vector<int>(p));
    for(int k=0; k<m; k++)
        for(int i=0; i<n; i++)
            for(int j=0; j<p; j++)
                add(C[i][j],A[i][k]*B[k][j]%mod);
    return C;
}
mat qpow(mat A,int k)
{
    int n=A.size();
    mat B(n,vector<int>(n));
    for(int i=0; i<A.size(); i++) B[i][i]=1;
    while(k)
    {
        if(k&1) B=mul(B,A);
        A=mul(A,A); k>>=1;
    }
    return B;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n,k; cin >> n >> k;
    mat a(n,vector<int>(n));
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            cin >> a[i][j];
    int res=0; a=qpow(a,k);
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            add(res,a[i][j]);
    cout << res << '\n';
    return 0;
}