題目鏈接：

　　傳送。

題解：

　　矩陣快速冪優化DP。

　　先考慮$nm^2$DP，設$f_{(i,j)}$表示從$1,1$到$i,j$的方案，顯然這個方程和奇偶性有關，我們考慮某列的$i$同奇偶性的轉移和奇偶性相異的貢獻，很容易把剛才的方程變成$nm$的輪換式方程，即$f_{(0/1,j)}$表示偶/奇數列第$j$行的方案數。此時轉移方程為$$f_{(i,j)}=f_{(i,j)}+\sum_{x=-1}^{1}f_{（i(xor)1，j+x）}$$

　　然后考慮如何用矩陣優化，畫圖發現十字相乘時，如果我們把奇偶分成兩列會沒辦法轉移，然后考慮十字相乘性質，我們可以把奇偶兩列轉換為一列上的兩段，這樣我們構建$(2n)^2$的矩陣，至于遞推矩陣，YY一下即可。

代碼：

　　

#define Troy 10/24/2017#include <bits/stdc++.h>using namespace std;inline int read(){int s=0,k=1;char ch=getchar();while(ch<'0'|ch>'9') ch=='-'?k=-1:0,ch=getchar();while(ch>47&ch<='9') s=s*10+(ch^48),ch=getchar();return s*k; }const int mod=30011;int n,m;struct Matrix{int a[101][101];Matrix(){memset(a,0,sizeof(a));}inline void e1(){for(int i=1;i<=2*n;i++)a[i][i]=1;}inline friend Matrix operator *(Matrix x,Matrix y){Matrix z;for(int i=1;i<=2*n;i++)for(int j=1;j<=2*n;j++)for(int k=1;k<=2*n;k++) z.a[i][j]=(z.a[i][j]+x.a[i][k]*1ll*y.a[k][j])%mod;return z;}inline friend Matrix operator ^(Matrix a,long long b){Matrix ret;ret.e1();while(b){if(b&1) ret=ret*a;a=a*a;b>>=1;}return ret;} };int main(){n=read(),m=read();if(m==1){puts(n==1?"1":"0");return 0;}Matrix ans;ans.a[1+n][1]=1;if(n>1)ans.a[2+n][1]=1;Matrix t;for(int i=1;i<=n;i++){t.a[i][i+n]=1;t.a[i+n][i]=1;t.a[i+n][i+n]=1;if(i-1)t.a[i+n][i+n-1]=1;if(i+1<=n)t.a[i+n][i+n+1]=1;}ans=(t^(m-2))*ans;printf("%d",ans.a[2*n][1]); }

?

轉載于:https://www.cnblogs.com/Troywar/p/7724937.html

總結

以上是生活随笔為你收集整理的【BZOJ4417】: [Shoi2013]超级跳马的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。