Submission #20049

#	Time	Username	Problem	Language	Result	Execution time	Memory
20049		tonyjjw	제비 (kriii4_W)	C++14	6 / 100	1895 ms	18948 KiB

W

#include <algorithm>
#include <assert.h>
#include <complex>
#include <ctype.h>
#include <functional>
#include <iostream>
#include <limits.h>
#include <locale.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <vector>
#include <unordered_set>
#include <unordered_map>

#pragma warning(disable:4996)
using namespace std;

#define mp make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <ldb, ldb> pdd;

int IT_MAX = 131072;
const ll MOD = 1000000007;
const int INF = 1034567891;
const ll LL_INF = 2234567890123456789ll;
const db PI = 3.141592653589793238;
const ldb ERR = 1E-10;

ll mul_inv(ll a, ll b)
{
	ll b0 = b, t, q;
	ll x0 = 0, x1 = 1;
	if (b == 1) return 1;
	while (a > 1) {
		q = a / b;
		t = b, b = a % b, a = t;
		t = x0, x0 = x1 - q * x0, x1 = t;
	}
	if (x1 < 0) x1 += b0;
	return x1;
}

ll dp[1050][1050];
ll P[1050][1050];
int main() {
	int T;
	scanf("%d", &T);
	for (int tc = 1; tc <= T; tc++) {
		int R, G, B, K, i, j;
		scanf("%d %d %d %d", &R, &G, &B, &K);

		if (tc == 1) {
			dp[0][0] = 0;
			P[0][0] = 1;
			for (i = 0; i <= R; i++) {
				for (j = 0; j <= 1000; j++) {
					if (i == 0 && j == 0) continue;
					int r = R - i, b = B, g = G;

					ll sum = 0, p = 0;
					if (i != 0) {
						r++;
						ll t = dp[i-1][j] + (b + g + r) * mul_inv(b + r, MOD);
						t %= MOD;

						ll tp = P[i - 1][j] * r % MOD * mul_inv(b + r, MOD) % MOD;
						sum += t * tp;
						p += tp;
						r--;
					}
					if (j != 0) {
						ll t = dp[i][j - 1] + (b + g + r) * mul_inv(b + r, MOD);
						t %= MOD;
						
						ll tp = P[i][j - 1] * b % MOD * mul_inv(b + r, MOD) % MOD;
						sum += t*tp;
						p += tp;
						
					}
					
					sum %= MOD;
					p %= MOD;
					P[i][j] = p;
					dp[i][j] = sum * mul_inv(p, MOD) % MOD;
				}
			}
		}

		ll sum = 0, p = 0;
		for (i = 0; i <= R; i++) {
			int r = R - i, g = G, b = B;
			ll t = dp[i][K - 1];
			t += (r + g + b) * mul_inv(r + b, MOD);
			t %= MOD;

			ll tp = P[i][K - 1] * b % MOD * mul_inv(r + b, MOD) % MOD;

			sum += (t*tp) % MOD;
			p += tp;
		}
		sum %= MOD;
		p %= MOD;
		printf("%lld\n", sum * mul_inv(p, MOD) % MOD);
	}
	return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 0 / 94