ABC 034 C - 経路 ( Math )

C: 経路 - AtCoder Beginner Contest 034 | AtCoder
前はDPにこだわりすぎてとけなかった。でもよく考えると実は H + W - 2 の選択から H - 1 ( あるいは W - 1 ) 個を選ぶだけの事。factorial と mod_inv で終わり。

const int MOD = 1e9 + 7;

int int_pow( int x, int p ){
    int res = 1;
    while( p ){
        if( p & 1 ) res = 1LL * res * x % MOD;
        x = 1LL * x * x % MOD;
        p >>= 1;
    }
    return res;
}

int mod_inv( int x ){
    return int_pow( x, MOD - 2 );
}

void solve(){
    int W, H; cin >> W >> H;
    vi fact( W + H );
    fact[ 0 ] = 1;
    for( int i = 0; i + 1 < fact.size(); ++i )
        fact[ i + 1 ] = 1LL * fact[ i ] * ( i + 1 ) % MOD;
    int ans = 1LL * fact[ W + H - 2 ] * mod_inv( fact[ W - 1 ] ) % MOD * mod_inv( fact[ H - 1 ] ) % MOD;
    cout << ans << "\n";
}