bzoj4417:[Shoi2013]超级跳马(矩阵快速幂优化DP)

Author Avatar
Sakits 3月 16, 2018

题解

  有趣的题
  一眼DP矩乘优化,但是转移有点麻烦,每次列跳奇数步,用一个DP数组其实是比较难处理的。显然每次跳完列的奇偶性会改变,所以其实可以对奇数列和偶数列各开一个数组来计算。
  设f(i,j)f(i,j)表示跳到(i,2j1)(i,2j-1)的方案数,g(i,j)g(i,j)表示跳到(i,2j)(i, 2j)的方案数,显然要O(1)O(1)转移的话取个前缀和就好了。

f(i,j)=f(i1,j)+g(i1,j1)+g(i,j1)+g(i+1,j)g(i,j)=g(i1,j)+f(i1,j)+f(i,j)+f(i+1,j)\begin{gathered} f(i,j)=f(i-1,j)+g(i-1,j-1)+g(i,j-1)+g(i+1,j)\\ g(i,j)=g(i-1,j)+f(i-1,j)+f(i,j)+f(i+1,j) \end{gathered}

  然后会发现g(i,j)g(i,j)需要从f(i,j)f(i,j)转移,那么就先计算ff再计算gg,所以转移矩阵应该是ff的转移矩阵乘上gg的转移矩阵,然后这题就完了。
  注意记得把前缀和化回去,还有初始化矩阵的时候别越界,调了好久T_T…

代码

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#define MOD(x) ((x)>=mod?((x)-mod):(x))
#define ll long long
using namespace std;
const int maxn=110, inf=1e9, mod=30011;
struct mtx{int mp[maxn][maxn]; mtx(){memset(mp, 0, sizeof(mp));}}base1, base2, base, ans1, ans2;
int n, m, N;
inline void read(int &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;	
} 
mtx operator * (mtx a, mtx b)
{
	mtx c;
	for(int i=1;i<=N;i++)
	for(int j=1;j<=N;j++)
	for(int k=1;k<=N;k++)
	c.mp[i][j]=(c.mp[i][j]+a.mp[i][k]*b.mp[k][j])%mod;
	return c;
}
inline void power(mtx& ans, int b)
{
	for(;b;b>>=1, base=base*base)
	if(b&1) ans=ans*base;
}
int main()
{
	read(n); read(m); N=n<<1;
	if(m==1) return printf("%d\n", n==1?1:0), 0;
	if(m==2) return printf("%d\n", n<=2?1:0), 0;
	for(int i=1;i<=n;i++)
	{
		base1.mp[i][i]=base1.mp[i+n][i+n]=base2.mp[i][i]=base2.mp[i+n][i+n]=1;  
        for(int j=i-1;j<=i+1;j++)  
    	if(j>0 && j<=n) base1.mp[i][j+n]=base2.mp[i+n][j]=1;  
	}
	base=base1*base2;
	for(int i=1;i<=N;i++) ans1.mp[i][i]=1, ans2.mp[i][i]=1;
	power(ans1, (m>>1)-1);
	base=base1*base2;
	power(ans2, m>>1);
	int ANS2=MOD(ans2.mp[(m&1)?n:(n<<1)][1]);
	int ANS1=MOD(ans1.mp[(m&1)?n:(n<<1)][1]);
	printf("%d\n", MOD(ANS2-ANS1+mod));
}