ゆるふわ競プロオンサイト #2 : J - swapping paths

続けていきます。
https://www.hackerrank.com/contests/yfkpo2/challenges/swapping-paths

問題

N行M列のグリッドがあり、１人は(1,A)、もう1人は(N,B)にいる。
ターン毎に両名は同時に移動する。
前者は(i,j)から(i+1,j-1)(i+1,j)(i+1,j+1)のいずれか、後者は(i-1,j-1)(i-1,j)(i-1,j+1)に移動する。
途中、(N+1)/2行目で両者が同じマスを通ることなく、互いに最後(N,B),(1,A)に到達する移動の組み合わせを求めよ。

解法

f(x) := (1,A)から((N+1)/2,x)を経由して(N,B)に至る経路
とする。これは(1,A)から((N+1)/2,x)に至る組み合わせと(N,B)から((N+1)/2,x)に至る組み合わせの積である。

f(x)が全部求められたら、両者が(N+1)/2行目で異なるマス目を通ればいいので、異なるx,yに対しf(x)*f(y)の総和を取ればよい。

int N,M;
int A,B;
ll mo=1000000007;

map<int,ll> dpA[501];
map<int,ll> dpB[501];
map<int,ll> dp;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	cin>>A>>B;
	
	dpA[1][A]=1;
	for(y=1;y<=N/2;y++) {
		FORR(v,dpA[y]) {
			int x=v.first;
			if(x>1) (dpA[y+1][x-1]+=v.second)%=mo;
			(dpA[y+1][x]+=v.second)%=mo;
			if(x<M) (dpA[y+1][x+1]+=v.second)%=mo;
		}
	}
	
	
	dpB[N][B]=1;
	for(y=N;y>N/2+1;y--) {
		FORR(v,dpB[y]) {
			int x=v.first;
			if(y==N/2+2) {
				if(x>1) (dp[x-1]+=dpB[y][x]*dpA[y-1][x-1])%=mo;
				(dp[x]+=dpB[y][x]*dpA[y-1][x])%=mo;
				if(x<M) (dp[x+1]+=dpB[y][x]*dpA[y-1][x+1])%=mo;
			}
			else {
				if(x>1) (dpB[y-1][x-1]+=v.second)%=mo;
				(dpB[y-1][x]+=v.second)%=mo;
				if(x<M) (dpB[y-1][x+1]+=v.second)%=mo;
			}
		}
	}
	
	ll ret=0;
	FORR(a,dp) FORR(b,dp) if(a.first!=b.first) (ret+=a.second*b.second)%=mo;
	cout<<ret<<endl;
	
}

まとめ

これNが大きかったらどうなるんだろ。O(N)ぐらいでは行けそうな気もするが。