AOJ 2445: MinimumCostPath

これは面白い。
向かいたい方向と逆に回らないといけない、すなわち遠回りを強要するブロック配置は、スタート付近とゴール付近にしかないことが容易に(ここが本質なんだけども)分かります。ということで赤い場所(50*50もない)は真面目にDPをして、白い場所は緑から青の経路の個数をDP+Combinationで計算すればよいです。
白い場所のDPは、dp[i]:i個目の黒ますの場所に黒ます史上初到達する方法の数、とかやるとO(N^2)で簡単にできます。(非指数包除の一つ)
ただし、ソートをする必要があります。あとMODが悪質です。気をつけましょう。
f:id:tozangezan:20151017004151p:plain

#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
long long mod=1000000009;
long long inv[2100000];
long long fact[2100000];
long long factinv[2100000];
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
pair<int,int>pt[100];
int r[100];
int c[100];
long long dp1[210][210];
long long dp2[210][210];
int bfs1[210][210];
int bfs2[210][210];
int m1[210][210];
int m2[210][210];
int R[210];
int C[210];
long long dp[110];
inline long long com(int a,int b){
	return fact[a]*factinv[b]%mod*factinv[a-b]%mod;
}
int main(){
	int a,b;
	inv[1]=1;
	for(int i=2;i<2100000;i++)inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	fact[0]=factinv[0]=1;
	for(int i=1;i<2100000;i++){
		fact[i]=fact[i-1]*i%mod;
		factinv[i]=factinv[i-1]*inv[i]%mod;
	}
	scanf("%d%d",&a,&b);
	if(a<=200){
		for(int i=0;i<b;i++){
			scanf("%d%d",r+i,c+i);
			r[i]--;c[i]--;
			m1[r[i]][c[i]]=1;
		}
		for(int i=0;i<210;i++)for(int j=0;j<210;j++){
			bfs1[i][j]=bfs2[i][j]=999999999;
		}
		bfs1[0][0]=bfs2[0][0]=0;
		dp1[0][0]=dp2[0][0]=1;
		queue<pair<int,int> >Q;
		Q.push(make_pair(0,0));
		while(Q.size()){
			int row=Q.front().first;int col=Q.front().second;Q.pop();
			//if(row==50||col==50)continue;
			for(int i=0;i<4;i++){
				int tr=row+dx[i];int tc=col+dy[i];
				if(tr<0||tc<0||tr>=a||tc>=a||m1[tr][tc])continue;
				if(bfs1[tr][tc]>=bfs1[row][col]+1){
					if(bfs1[tr][tc]>99999999)Q.push(make_pair(tr,tc));
					bfs1[tr][tc]=bfs1[row][col]+1;
					dp1[tr][tc]=(dp1[tr][tc]+dp1[row][col])%mod;
				}
			}
		}
		printf("%lld\n",dp1[a-1][a-1]);
		return 0;
	}
	dp1[0][0]=dp2[0][0]=1;
	for(int i=0;i<b;i++){
		scanf("%d%d",r+i,c+i);
		pt[i]=make_pair(r[i],c[i]);
	}
	std::sort(pt,pt+b);
	for(int i=0;i<b;i++){
		r[i]=pt[i].first;c[i]=pt[i].second;
		r[i]--;c[i]--;
		if(r[i]<=50&&c[i]<=50)m1[r[i]][c[i]]=1;
		if(a-r[i]<=51&&a-c[i]<=51)m2[a-r[i]-1][a-c[i]-1]=1;
	}
	for(int i=0;i<60;i++)for(int j=0;j<60;j++){
		bfs1[i][j]=bfs2[i][j]=999999999;
	}
	bfs1[0][0]=bfs2[0][0]=0;
	queue<pair<int,int> >Q;
	Q.push(make_pair(0,0));
	while(Q.size()){
		int row=Q.front().first;int col=Q.front().second;Q.pop();
		if(row==50||col==50)continue;
		for(int i=0;i<4;i++){
			int tr=row+dx[i];int tc=col+dy[i];
			if(tr<0||tc<0||m1[tr][tc])continue;
			if(bfs1[tr][tc]>=bfs1[row][col]+1){
				if(bfs1[tr][tc]>99999999)Q.push(make_pair(tr,tc));
				bfs1[tr][tc]=bfs1[row][col]+1;
				dp1[tr][tc]=(dp1[tr][tc]+dp1[row][col])%mod;
			}
		}
	}
	Q.push(make_pair(0,0));
	while(Q.size()){
		int row=Q.front().first;int col=Q.front().second;Q.pop();
		if(row==50||col==50)continue;
		for(int i=0;i<4;i++){
			int tr=row+dx[i];int tc=col+dy[i];
			if(tr<0||tc<0||m2[tr][tc])continue;
			if(bfs2[tr][tc]>=bfs2[row][col]+1){
				if(bfs2[tr][tc]>99999999)Q.push(make_pair(tr,tc));
				bfs2[tr][tc]=bfs2[row][col]+1;
				dp2[tr][tc]=(dp2[tr][tc]+dp2[row][col])%mod;
			}
		}
	}
	int md=2066666666;
	long long ret=0;
	for(int i=0;i<100;i++){
		int sr,sc;
		if(i<50){
			sr=i;sc=50;
		}else{
			sr=50;sc=i-50;
		}
		for(int j=0;j<100;j++){
			int gr,gc;
			if(j<50){
				gr=a-1-j;gc=a-1-50;
			}else{
				gr=a-1-50;gc=a-1-(j-50);
			}
			int sz=0;
			for(int k=0;k<b;k++){
				if(sr<=r[k]&&r[k]<=gr&&sc<=c[k]&&c[k]<=gc){
					R[sz]=r[k];C[sz++]=c[k];
				}
			}
			R[sz]=gr;C[sz++]=gc;
			for(int k=0;k<sz;k++){
				dp[k]=com(R[k]-sr+C[k]-sc,R[k]-sr);
				for(int l=0;l<sz;l++){
					if(k!=l&&R[l]<=R[k]&&C[l]<=C[k])dp[k]=(dp[k]+mod-dp[l]*com(R[k]-R[l]+C[k]-C[l],R[k]-R[l])%mod)%mod;
				}
			}
			int dist=bfs1[sr][sc]+bfs2[a-1-gr][a-1-gc]+gr-sr+gc-sc;
			if(dist<md){
				md=dist;
				ret=dp[sz-1]*dp1[sr][sc]%mod*dp2[a-1-gr][a-1-gc]%mod;
			}else if(dist==md){
				ret=(ret+dp[sz-1]*dp1[sr][sc]%mod*dp2[a-1-gr][a-1-gc])%mod;
			}
		}
	}
	if(md>100000000)ret=0;
	printf("%lld\n",ret);
}