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;
}