Submission #816087


Source Code Expand

#include <iostream>
#include <set>
using namespace std;
const int MOD = 1000000000 + 7;
long long F[200005] = {1};
long long pwr(long long a, long long b) {
	long long ret = 1;
	while(b) {
		if (b & 1) {
			ret = ret * a % MOD;
		}
		a = a * a % MOD;
		b >>= 1;
	}
	return ret;
}
long long ways(int r, int c, int R, int C) {
	R -= r;
	C -= c;
	if (R < 0 or C < 0) {
		return 0;
	}
	long long num = F[R + C];
	long long den = F[R] * F[C] % MOD;
	den = pwr(den, MOD - 2);
	return num * den % MOD;
}
int main() {
	for (int i = 1; i < 200005; ++i) {
		F[i] = F[i - 1] * i % MOD;
	}
	int h, w, a, b;
	cin >> h >> w >> a >> b;
	a = h - a + 1;
	long long total = ways(1, 1, h, w);
	for (int c = 1; c < b; ++c) {
		total -= ways(1, 1, a, c) * ways(a + 1, c, h, w) % MOD; 
	}
	total -= ways(1, 1, a, b) * ways(a, b, h, w) % MOD;
	total = (total % MOD + MOD) % MOD;
	cout << total;
}

Submission Info

Submission Time
Task D - Iroha and a Grid
User moscow_fans
Language C++14 (GCC 5.4.1)
Score 400
Code Size 914 Byte
Status AC
Exec Time 74 ms
Memory 1792 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 4
AC × 26
Set Name Test Cases
Sample subtask0_01.txt, subtask0_02.txt, subtask0_03.txt, subtask0_04.txt
All subtask0_01.txt, subtask0_02.txt, subtask0_03.txt, subtask0_04.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_max.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_max.txt
Case Name Status Exec Time Memory
subtask0_01.txt AC 9 ms 1792 KiB
subtask0_02.txt AC 9 ms 1792 KiB
subtask0_03.txt AC 74 ms 1792 KiB
subtask0_04.txt AC 46 ms 1792 KiB
subtask1_01.txt AC 9 ms 1792 KiB
subtask1_02.txt AC 9 ms 1792 KiB
subtask1_03.txt AC 9 ms 1792 KiB
subtask1_04.txt AC 8 ms 1792 KiB
subtask1_05.txt AC 9 ms 1792 KiB
subtask1_06.txt AC 9 ms 1792 KiB
subtask1_07.txt AC 9 ms 1792 KiB
subtask1_08.txt AC 9 ms 1792 KiB
subtask1_09.txt AC 9 ms 1792 KiB
subtask1_10.txt AC 8 ms 1792 KiB
subtask1_max.txt AC 10 ms 1792 KiB
subtask2_01.txt AC 10 ms 1792 KiB
subtask2_02.txt AC 15 ms 1792 KiB
subtask2_03.txt AC 11 ms 1792 KiB
subtask2_04.txt AC 11 ms 1792 KiB
subtask2_05.txt AC 12 ms 1792 KiB
subtask2_06.txt AC 10 ms 1792 KiB
subtask2_07.txt AC 71 ms 1792 KiB
subtask2_08.txt AC 37 ms 1792 KiB
subtask2_09.txt AC 52 ms 1792 KiB
subtask2_10.txt AC 9 ms 1792 KiB
subtask2_max.txt AC 11 ms 1792 KiB