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