题解 | #路径数量#

学过离散数学的都应该知道这题怎么做，然后我用的是矩阵快速幂，复杂度
，就算是遇到 值很大的情况下也可以解。

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
typedef long long ll;
const int maxn=40;

int n,k;
struct node{
    ll f[maxn][maxn];
    inline node operator*(const node&x)const{
        node y; memset(y.f,0,sizeof(y.f));
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                for(int k=1;k<=n;k++)
                {
                    y.f[i][j]+=f[i][k]*x.f[k][j];
                }
            }
        }
        return y;
    }
}a;

node qpow(node a,int b)
{
    node ans; memset(ans.f,0,sizeof(ans.f));
    for(int i=1;i<=n;i++)ans.f[i][i]=1;
    while(b)
    {
        if(b&1)ans=ans*a;
        b>>=1; a=a*a;
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a.f[i][j];
        }
    }
    node ans=qpow(a,k);
    cout<<ans.f[1][n]<<endl;
    return 0;
}