Submission #66434399

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#define MOD_BY 998244353
int add(int a, int b) {
  return a + b - MOD_BY * (a + b >= MOD_BY);
}
int mul(int a, int b) {
  return (int)((long long)a * b % MOD_BY);
}
int pou(int a, int b) {
  int r = 1;
  while (b > 0) {
    if (b & 1) r = mul(r, a);
    a = mul(a, a);
    b >>= 1;
  }
  return r;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>

#define MOD_BY 998244353

int add(int a, int b) {
	return a + b - MOD_BY * (a + b >= MOD_BY);
}

int mul(int a, int b) {
	return (int)((long long)a * b % MOD_BY);
}

int pou(int a, int b) {
	int r = 1;
	while (b > 0) {
		if (b & 1) r = mul(r, a);
		a = mul(a, a);
		b >>= 1;
	}
	return r;
}

int inv(int a) {
	return pou(a, MOD_BY - 2);
}

int kaizyo_cache[1123456 * 4];
int kaizyo_cache_max = -1;

int kaizyo(int a) {
	if (a > kaizyo_cache_max) {
		int i;
		if (kaizyo_cache_max < 0) {
			kaizyo_cache[0] = 1;
			kaizyo_cache_max = 0;
		}
		for (i = kaizyo_cache_max + 1; i <= a; i++) {
			kaizyo_cache[i] = mul(kaizyo_cache[i - 1], i);
		}
		kaizyo_cache_max = a;
	}
	return kaizyo_cache[a];
}

/* hoge を a 個、fuga を b 個並べるパターン数を求める */
int kazu(int a, int b) {
	return mul(kaizyo(a + b), inv(mul(kaizyo(a), kaizyo(b))));
}

int main(void) {
	int A, B, C, D;
	int ans = 0;
	int i;
	if (scanf("%d%d%d%d", &A, &B, &C, &D) != 4) return 1;
	for (i = 0; i <= B; i++) {
		ans = add(ans, mul(kazu(A - 1, i), kazu(C, B - i + D)));
	}
	printf("%d\n", ans);
	return 0;
}

/*

                          ラストリンゴ     ファーストブドウ
<----- リンゴゾーン ----->○<---------------------- バナナゾーン ----->
<----- オレンジゾーン -------------------->○<----- ブドウゾーン ----->

1. オレンジ・バナナ・Xを適当に並べる
2. X の前半をリンゴに、後半をブドウにする

→ ダメ (バナナの後にリンゴが来る可能性があるので)
→ 来るパターンを弾けばいい？

-------

リンゴゾーンに入れるオレンジの数を決め打ちする
↓
「リンゴ」「決めた数のオレンジ」を並べる (最後はリンゴで固定)
「バナナ」「X (残りのオレンジとブドウ)」を並べる

*/

Submission Info

Judge Result