Submission #1856896

---

Source Code Expand

package main

import "fmt"

const (
	MOD = 1000000007
)

func genComb(n int64, k int64) [][]int64 {
	// k = 0 => 1,  n = k => 1, n < k => 0
	dp := make([][]int64, n+1)
	for i := int64(0); i <= n; i++ {
		dp[i] = make([]int64, k+1)
	}

	// dp[n][k] = dp[n-1][k-1] + dp[n-1][k]
	dp[0][0] = 1
	for i := int64(1); i <= n; i++ {
		for j := int64(0); j <= k; j++ {
			if j > 0 {
				dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % MOD
			} else {
				dp[i][j] = dp[i-1][j]
			}
		}
	}

	return dp
}

func calc(dp [][]int64, depth int, D int64, L int64, dx []int64, dy []int64, idx int, x int64, y int64, sign int64) int64 {
	if depth == 0 {
		if D+L <= x*y {
			var ret int64
			ret = (dp[x*y][D] * dp[x*y-D][L]) % MOD
			return sign * ret
		} else {
			return 0
		}
	}

	var ret int64
	ret = 0
	for i := idx; i < len(dx); i++ {
		ret = ret + calc(dp, depth-1, D, L, dx, dy, i+1, x+dx[i], y+dy[i], sign*-1)
		ret = ret % MOD
	}
	return ret
}

func main() {
	var R, C int64
	var X, Y int64
	var D, L int64
	fmt.Scanf("%d %d", &R, &C)
	fmt.Scanf("%d %d", &X, &Y)
	fmt.Scanf("%d %d", &D, &L)

	dp := genComb(900, 900)

	var res int64
	res = 1
	if D+L == X*Y {
		res = ((res % MOD) * dp[X*Y][D]) % MOD
		res = (res * (R - X + 1) * (C - Y + 1)) % MOD // 区画の組み合わせ
	} else {
		dx := []int64{-1, -1, 0, 0}
		dy := []int64{0, 0, -1, -1}
		res = (res * dp[X*Y][D]) % MOD
		res = (res * dp[X*Y-D][L]) % MOD
		for i := 0; i < len(dx); i++ {
			res = res + calc(dp, i+1, D, L, dx, dy, 0, X, Y, 1)
			for {
				if res > 0 {
					break
				}
				res = res + MOD
			}
			res = res % MOD
		}
		res = res * (R - X + 1) * (C - Y + 1) // 区画の組み合わせ
		res = res % MOD
	}

	fmt.Println(res)
}

Submission Info

Judge Result