AOJ 2214: Warp Hall

dp[i]: 最後にiを使って行ったケース(この値そのものが行き方の総数ではなく、総数になるように上手く補正する(可能な行き方が減る)のをdp[j]->dp[i]やdp[i]->ansで更新するときに計算する)

なかなか見ないタイプのDPで結構難しい。

#include<stdio.h>
#include<algorithm>
using namespace std;
int mod=1000000007;
int X1[1100];
int Y1[1100];
int X2[1100];
int Y2[1100];
pair<pair<int,int>,pair<int,int> > p[1100];
long long fact[210000];
long long inv[210000];
long long factinv[210000];
long long dp[1100];
long long getinv(long long a){
	int b=mod-2;
	long long ret=1;
	long long now=a;
	while(b){
		if(b%2)ret=ret*now%mod;
		b/=2;
		now=now*now%mod;
	}
	//printf("%lld: %lld\n",a,ret);
	return ret;
}
long long C(long long n,long long k){
	if(n<0||k<0)return 0;
	n+=k;
	return fact[n]*factinv[k]%mod*factinv[n-k]%mod;
}
int main(){
	int a,b,c;
	fact[0]=1;
	for(int i=1;i<210000;i++)fact[i]=fact[i-1]*i%mod;
	inv[1]=1;
	for(int i=2;i<210000;i++)inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	factinv[0]=1;
	for(int i=1;i<210000;i++)factinv[i]=factinv[i-1]*inv[i]%mod;
	while(scanf("%d%d%d",&a,&b,&c),a){
		for(int i=1;i<=c;i++){
			scanf("%d%d%d%d",X1+i,Y1+i,X2+i,Y2+i);
			X1[i]--;X2[i]--;Y1[i]--;Y2[i]--;
			p[i]=make_pair(make_pair(X1[i],Y1[i]),make_pair(X2[i],Y2[i]));
		}
		std::sort(p+1,p+c+1);
		a--;b--;
		for(int i=0;i<c+2;i++)dp[i]=0;
		for(int i=1;i<=c;i++){
			int row=p[i].first.first;
			int col=p[i].first.second;
			dp[i]=C(row,col);
			for(int j=1;j<i;j++){
				//if(row<p[j].second.first||col<p[j].second.second)continue;
				dp[i]=(dp[i]+dp[j]*(mod+C(row-p[j].second.first,col-p[j].second.second)-C(row-p[j].first.first,col-p[j].first.second)))%mod;
			}
		}
		long long ret=C(a,b);
		for(int i=1;i<=c;i++)ret=(ret+dp[i]*(mod+C(a-p[i].second.first,b-p[i].second.second)-C(a-p[i].first.first,b-p[i].first.second)))%mod;
		printf("%lld\n",ret);
	}
}