aoj2335:10-Year-Old Dynamic Programming

問題文

10-Year-Old Dynamic Programming | Aizu Online Judge

解法

縦方向に寄り道する回数をk、横方向をlとすると、(k+l=K)
右にW+k回、左にk回、上にH+l回、下にl回移動することになる。

最終的にx座標がWになるような横方向の移動の方法の総数をX、同様に縦方向のやつをYと求められたとすると、
C(W+H+2*K,W+2*k)*X*Y通りの方法がある。ここで、C(n,k)=nCk。これを、すべてのkについて足し合わせればいい。

X,Yを求める。どちらかを求める方法が分かれば同じ方法でもう一方も求まるので、Xを求める。
X=[(0,0)->(W+k,k)に右または下への移動のみで行く方法の総数。ただし、途中でy>xとなってはならない]
である。これはカラタン数の亜種(というか少し上位バージョン)みたいな感じがして、
カタラン数の一般項Cn=C(2n,n)-C(2n,n-1)を導くときにやった、
「いい感じの直線を引いて、ゴールを線対象な位置に写していい感じにやる(適当)」みたいな方法が使える(多分)
よって、X=C(W+2*k,k)-C(W+2*k,k-1)である。

コード

#include<bits/stdc++.h>
using namespace std;

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

const int mod=1000000007;
int mpow(int n,int m){
    int ret=1;
    while(m){
        if(m&1)ret=ret*n%mod;
        n=n*n%mod;
        m>>=1;
    }
    return ret;
}

int fact[555555],inv[555555];

int C(int n,int k){
    return fact[n]*inv[k]%mod*inv[n-k]%mod;
}

signed main(){
    int W,H,K;
    cin>>W>>H>>K;

    fact[0]=inv[0]=1;
    for(int i=1;i<555555;i++){
        fact[i]=fact[i-1]*i%mod;
        inv[i]=mpow(fact[i],mod-2);
    }


    int ans=0;
    for(int k=0;k<=K;k++){
        int l=K-k;
        int hoge=(C(W+2*k,k)-(k?C(W+2*k,k-1):0)+mod)%mod;
        int piyo=(C(H+2*l,l)-(l?C(H+2*l,l-1):0)+mod)%mod;

        ans+=C(W+H+2*K,W+2*k)*hoge%mod*piyo%mod;
        ans%=mod;
    }
    cout<<ans<<endl;
    return 0;
}