結果

問題 No.1547 [Cherry 2nd Tune *] 偶然の勝利の確率
ユーザー 👑 KazunKazun
提出日時 2021-04-10 17:22:04
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 733 ms / 2,000 ms
コード長 2,216 bytes
コンパイル時間 992 ms
コンパイル使用メモリ 75,872 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-05-08 18:30:11
合計ジャッジ時間 11,082 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 25 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 3 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 127 ms
5,376 KB
testcase_14 AC 83 ms
5,376 KB
testcase_15 AC 35 ms
5,376 KB
testcase_16 AC 57 ms
5,376 KB
testcase_17 AC 56 ms
5,376 KB
testcase_18 AC 52 ms
5,376 KB
testcase_19 AC 17 ms
5,376 KB
testcase_20 AC 401 ms
5,376 KB
testcase_21 AC 34 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
testcase_23 AC 733 ms
5,376 KB
testcase_24 AC 720 ms
5,376 KB
testcase_25 AC 714 ms
5,376 KB
testcase_26 AC 717 ms
5,376 KB
testcase_27 AC 719 ms
5,376 KB
testcase_28 AC 717 ms
5,376 KB
testcase_29 AC 716 ms
5,376 KB
testcase_30 AC 716 ms
5,376 KB
testcase_31 AC 720 ms
5,376 KB
testcase_32 AC 717 ms
5,376 KB
testcase_33 AC 682 ms
5,376 KB
testcase_34 AC 51 ms
5,376 KB
testcase_35 AC 50 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>

using namespace std;
using ll = long long;

#define Vec vector<ll>
#define Mat vector<vector<ll>>

ll Mod = 998244353;

//単位行列の設定
Mat Identity(int N) {
	Mat I(N, Vec(N, 0));
	for (int i = 0; i < N; i++) I[i][i] = 1;
	return I;
}

//行列の乗算
Mat mul(Mat A, Mat B) {
	int N = A.size();
	Mat C(N, Vec(N, 0));

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < N; k++) {
				C[i][j] += A[i][k] * B[k][j];
				C[i][j] %= Mod;
			}
		}
	}
	return C;
}

//行列の累乗
Mat mat_power(Mat A, ll k) {
	Mat E = Identity(A.size());
	while (k) {
		if (k & 1) E = mul(E, A);
		A = mul(A, A);
		k >>= 1;
	}
	return E;
}

//剰余の累乗
ll mod_power(ll a, ll k) {
	ll e = 1;
	while (k) {
		if (k & 1) e = (e * a) % Mod;
		a = (a * a) % Mod;
		k >>= 1;
	}
	return e;
}

int main() {
	//入力
	ll MA, NA, MB, NB, K;
	int S, T;

	cin >> MA >> NA >> S;
	cin >> MB >> NB >> T;
	cin >> K;

	//定数の設定
	ll rho_A = (MA * mod_power(NA, Mod - 2)) % Mod;
	ll rho_B = (MB * mod_power(NB, Mod - 2)) % Mod;

	//===Aについての行列
	Mat U(S + T + 1, Vec(S + T + 1, 0));
	for (int y = 0; y <= S + T; y++) {
		for (int x = 0; x <= S + T; x++) {
			if (x == 0) {
				if (y == 0) U[y][x] = 1;
				else U[y][x] = 0;
			}
			else if(x == S + T) {
				if (y == S + T) U[y][x] = 1;
				else U[y][x] = 0;
			}
			else {
				if (y < x) U[y][x] = 0;
				else {
					if (y == S + T) U[y][x] = mod_power(rho_A, y - x);
					else U[y][x] = (mod_power(rho_A, y - x) * (Mod + 1 - rho_A)) % Mod;
				}
			}
		}
	}

	//===Bについての行列
	Mat V(S + T + 1, Vec(S + T + 1, 0));
	for (int y = 0; y <= S + T; y++) {
		for (int x = 0; x <= S + T; x++) {
			if (x == 0) {
				if (y == 0) V[y][x] = 1;
				else V[y][x] = 0;
			}
			else if (x == S + T) {
				if (y == S + T) V[y][x] = 1;
				else V[y][x] = 0;
			}
			else {
				if (y > x) V[y][x] = 0;
				else {
					if (y == 0) V[y][x] = mod_power(rho_B, x - y);
					else V[y][x] = (mod_power(rho_B, x - y) * (Mod + 1 - rho_B)) % Mod;
				}
			}
		}
	}

	//行列の計算
	Mat M = mul(V, U);
	Mat E = mat_power(M, K);

	//結果の出力
	cout << E[S + T][T] << endl;
	cout << E[0][T] << endl;
}
0