正題

題目鏈接:https://jzoj.net/senior/#main/show/3847

---

題目大意

$n$個點$m$條邊，第$i$個點要求$h_i$時才可以到達。求經(jīng)過$t$時從點1到點$n$的方案數(shù)。

---

解題思路

因為$h_i$較小，設(shè)$z_{i,k}$表示$i$時到$k$的方案數(shù)，轉(zhuǎn)移到最大的$h_i$后就用矩陣乘法處理。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=75,XJQ=10086; struct matrix{ll a[N][N]; }f; ll n,m,t,h[N],z[N][N],ans,maxs; matrix operator*(matrix &a,matrix &b){matrix c;memset(c.a,0,sizeof(c.a));for(ll i=1;i<=n;i++)for(ll j=1;j<=n;j++)for(ll k=1;k<=n;k++)(c.a[i][j]+=a.a[i][k]*b.a[k][j]%XJQ)%=XJQ;return c; } matrix ksm(matrix f,ll b){matrix ans;memset(ans.a,0,sizeof(ans.a));for(ll i=1;i<=n;i++)ans.a[i][i]=1;while(b){if(b&1) ans=ans*f;f=f*f;b>>=1;}return ans; } int main() {scanf("%lld%lld%lld",&n,&m,&t);for(ll i=1;i<=n;i++){scanf("%lld",&h[i]);maxs=max(maxs,h[i]);f.a[i][i]++;}for(ll i=1;i<=m;i++){ll x,y;scanf("%lld%lld",&x,&y);f.a[x][y]++;}z[0][1]=1;maxs=min(t,maxs);for(ll i=1;i<=maxs;i++){for(ll x=1;x<=n;x++)for(ll y=1;y<=n;y++)if(f.a[x][y]&&h[y]<=i)z[i][y]=(z[i][y]+z[i-1][x]*f.a[x][y]%XJQ)%XJQ;}f=ksm(f,t-maxs);for(ll x=1;x<=n;x++)for(ll y=1;y<=n;y++)(z[maxs+1][y]+=z[maxs][x]*f.a[x][y]%XJQ)%=XJQ;printf("%lld",z[maxs+1][n]); }

總結(jié)

以上是生活随笔為你收集整理的jzoj3847-都市环游【矩阵乘法】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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