結果

問題 No.1547 [Cherry 2nd Tune *] 偶然の勝利の確率
コンテスト
ユーザー 👑 Kazun
提出日時 2021-04-10 17:22:04
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 719 ms / 2,000 ms
コード長 2,216 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 934 ms
コンパイル使用メモリ 77,392 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-15 00:45:50
合計ジャッジ時間 10,847 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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