結果
問題 | No.1547 [Cherry 2nd Tune *] 偶然の勝利の確率 |
ユーザー |
![]() |
提出日時 | 2021-06-11 21:58:00 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 85 ms / 2,000 ms |
コード長 | 1,907 bytes |
コンパイル時間 | 2,022 ms |
コンパイル使用メモリ | 177,008 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-15 00:48:20 |
合計ジャッジ時間 | 4,091 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 36 |
ソースコード
#include <bits/stdc++.h>using namespace std;const long long MOD = 998244353;long long modpow(long long a, long long b){long long ans = 1;while (b > 0){if (b % 2 == 1){ans *= a;ans %= MOD;}a *= a;a %= MOD;b /= 2;}return ans;}long long modinv(long long a){return modpow(a, MOD - 2);}vector<vector<long long>> matmul(vector<vector<long long>> A, vector<vector<long long>> B){int N = A.size();vector<vector<long long>> ans(N, vector<long long>(N, 0));for (int i = 0; i < N; i++){for (int j = 0; j < N; j++){for (int k = 0; k < N; k++){ans[i][k] += A[i][j] * B[j][k];ans[i][k] %= MOD;}}}return ans;}vector<vector<long long>> matexp(vector<vector<long long>> A, long long b){int N = A.size();vector<vector<long long>> ans(N, vector<long long>(N, 0));for (int i = 0; i < N; i++){ans[i][i] = 1;}while (b > 0){if (b % 2 == 1){ans = matmul(ans, A);}A = matmul(A, A);b /= 2;}return ans;}int main(){long long MA, NA;int S;cin >> MA >> NA >> S;long long MB, NB;int T;cin >> MB >> NB >> T;int K;cin >> K;long long pA = MA * modinv(NA) % MOD;long long pB = MB * modinv(NB) % MOD;int cnt = S + T - 1;vector<vector<long long>> A(S + T + 1, vector<long long>(S + T + 1, 0));A[0][0] = 1;A[S + T][S + T] = 1;for (int i = 1; i < S + T; i++){for (int j = i; j <= S + T; j++){long long p1 = modpow(pA, j - i);if (j == S + T){A[i][S + T] = p1;} else {p1 *= MOD + 1 - pA;p1 %= MOD;for (int k = 0; k <= j; k++){long long p2 = modpow(pB, j - k);if (k != 0){p2 *= MOD + 1 - pB;p2 %= MOD;}A[i][k] += p1 * p2 % MOD;A[i][k] %= MOD;}}}}A = matexp(A, K);cout << A[T][S + T] << endl;cout << A[T][0] << endl;}