提出 #67828468

---

ソースコード 拡げる

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

const MOD int64 = 1_000_000_007
const MAX int = 200000 // H + W の最大値に余裕を持たせる

var fact = make([]int64, MAX+1)
var invFact = make([]int64, MAX+1)

/**
 * powMod は base^exp を MOD で割った値を返す
 * @param base int64 底
 * @param exp int64 指数
 * @return int64 base^exp % MOD
 */
func powMod(base, exp int64) int64 {
	result := int64(1)
	base %= MOD
	for exp > 0 {
		if exp%2 == 1 {
			result = (result * base) % MOD
		}
		base = (base * base) % MOD
		exp >>= 1
	}
	return result
}

/**
 * precomputeFactorials は fact[], invFact[] を前計算する
 */
func precomputeFactorials() {
	fact[0] = 1
	for i := 1; i <= MAX; i++ {
		fact[i] = fact[i-1] * int64(i) % MOD
	}
	invFact[MAX] = powMod(fact[MAX], MOD-2)
	for i := MAX - 1; i >= 0; i-- {
		invFact[i] = invFact[i+1] * int64(i+1) % MOD
	}
}

/**
 * combination は nCr (mod MOD) を返す
 * @param n int
 * @param r int
 * @return int64 組み合わせ値
 */
func combination(n, r int) int64 {
	if r < 0 || r > n {
		return 0
	}
	return fact[n] * invFact[r] % MOD * invFact[n-r] % MOD
}

/**
 * countGridPaths はグリッドの経路数を返す
 * @param H int 行数
 * @param W int 列数
 * @return int64 経路数（mod MOD）
 */
func countGridPaths(H, W int) int64 {
	precomputeFactorials()
	return combination(H+W-2, H-1)
}

/**
 * main は標準入力から H, W を読み取り、経路数を出力する
 */
func main() {
	reader := bufio.NewReader(os.Stdin)
	line, _ := reader.ReadString('\n')
	tokens := strings.Fields(line)

	H, _ := strconv.Atoi(tokens[0])
	W, _ := strconv.Atoi(tokens[1])

	result := countGridPaths(H, W)
	fmt.Println(result)
}

提出情報

ジャッジ結果