結果
問題 | No.1547 [Cherry 2nd Tune *] 偶然の勝利の確率 |
ユーザー | 👑 kakel-san |
提出日時 | 2021-06-13 17:22:32 |
言語 | C# (.NET 8.0.203) |
結果 |
AC
|
実行時間 | 608 ms / 2,000 ms |
コード長 | 3,582 bytes |
コンパイル時間 | 10,845 ms |
コンパイル使用メモリ | 145,112 KB |
実行使用メモリ | 163,424 KB |
最終ジャッジ日時 | 2023-08-24 20:20:06 |
合計ジャッジ時間 | 20,729 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 52 ms
28,656 KB |
testcase_01 | AC | 52 ms
28,608 KB |
testcase_02 | AC | 69 ms
30,900 KB |
testcase_03 | AC | 53 ms
30,648 KB |
testcase_04 | AC | 53 ms
28,736 KB |
testcase_05 | AC | 53 ms
28,808 KB |
testcase_06 | AC | 58 ms
30,528 KB |
testcase_07 | AC | 52 ms
30,452 KB |
testcase_08 | AC | 52 ms
28,500 KB |
testcase_09 | AC | 52 ms
28,752 KB |
testcase_10 | AC | 52 ms
28,532 KB |
testcase_11 | AC | 53 ms
30,484 KB |
testcase_12 | AC | 52 ms
28,516 KB |
testcase_13 | AC | 146 ms
29,508 KB |
testcase_14 | AC | 109 ms
29,276 KB |
testcase_15 | AC | 76 ms
29,216 KB |
testcase_16 | AC | 93 ms
28,936 KB |
testcase_17 | AC | 94 ms
29,016 KB |
testcase_18 | AC | 92 ms
31,076 KB |
testcase_19 | AC | 62 ms
28,824 KB |
testcase_20 | AC | 349 ms
30,440 KB |
testcase_21 | AC | 80 ms
29,028 KB |
testcase_22 | AC | 53 ms
28,508 KB |
testcase_23 | AC | 602 ms
33,220 KB |
testcase_24 | AC | 608 ms
31,504 KB |
testcase_25 | AC | 602 ms
31,204 KB |
testcase_26 | AC | 602 ms
31,056 KB |
testcase_27 | AC | 602 ms
33,308 KB |
testcase_28 | AC | 605 ms
31,292 KB |
testcase_29 | AC | 604 ms
31,476 KB |
testcase_30 | AC | 602 ms
31,316 KB |
testcase_31 | AC | 601 ms
31,248 KB |
testcase_32 | AC | 601 ms
31,156 KB |
testcase_33 | AC | 584 ms
31,108 KB |
testcase_34 | AC | 87 ms
28,944 KB |
testcase_35 | AC | 87 ms
163,424 KB |
コンパイルメッセージ
Determining projects to restore... Restored /home/judge/data/code/main.csproj (in 194 ms). .NET 向け Microsoft (R) Build Engine バージョン 17.0.0-preview-21470-01+cb055d28f Copyright (C) Microsoft Corporation.All rights reserved. プレビュー版の .NET を使用しています。https://aka.ms/dotnet-core-preview をご覧ください main -> /home/judge/data/code/bin/Release/net6.0/main.dll main -> /home/judge/data/code/bin/Release/net6.0/publish/
ソースコード
using System; using System.Collections.Generic; using static System.Console; using System.Linq; class yc299 { static int[] NList => ReadLine().Split().Select(int.Parse).ToArray(); static int[][] NMap(int n) => Enumerable.Repeat<int>(0, n).Select(_ => NList).ToArray(); static void Main() { var x = NList; var y = NList; var k = NList[0]; var (ma, na, s) = (x[0], x[1], x[2]); var (mb, nb, t) = (y[0], y[1], y[2]); var key = 998244353; var revna = PowMod(na, key - 2, key); var revnb = PowMod(nb, key - 2, key); var amap = AMap(s + t + 1, ma, revna, key); var bmap = BMap(s + t + 1, mb, revnb, key); var nmap = Mul(bmap, amap, key); var dp = new long[s + t + 1]; dp[t] = 1; var tmp = k; while (tmp > 0) { if (tmp % 2 == 1) { dp = Mul(nmap, dp, key); } nmap = Mul(nmap, nmap, key); tmp >>= 1; } WriteLine(dp.Last()); WriteLine(dp[0]); } static long[,] AMap(int size, int ma, int revna, int key) { var amap = new long[size, size]; amap[0, 0] = 1; amap[size - 1, size - 1] = 1; for (var y = 1; y < size - 1; ++y) { var poss = (long)ma * revna % key; var val = 1L; var rev = (1 + key - poss) % key; for (var x = y; x < size - 1; ++x) { amap[x, y] = val * rev % key; val = (val * ma % key) * revna % key; } amap[size - 1, y] = val; } return amap; } static long[,] BMap(int size, int mb, int revnb, int key) { var bmap = new long[size, size]; bmap[0, 0] = 1; bmap[size - 1, size - 1] = 1; for (var y = size - 2; y > 0; --y) { var poss = (long)mb * revnb % key; var val = 1L; var rev = (1 + key - poss) % key; for (var x = y; x > 0; --x) { bmap[x, y] = val * rev % key; val = (val * mb % key) * revnb % key; } bmap[0, y] = val; } return bmap; } static long[,] Mul(long[,] a, long[,] b, int key) { var h = a.GetLength(0); var w = b.GetLength(1); var cm = a.GetLength(1); var map = new long[h, w]; for (var i = 0; i < h; ++i) { for (var j = 0; j < w; ++j) { for (var c = 0; c < cm; ++c) { map[i, j] = (map[i, j] + a[i, c] * b[c, j]) % key; } } } return map; } static long[] Mul(long[,] a, long[] list, int key) { var len = a.GetLength(0); var res = new long[len]; for (var i = 0; i < len; ++i) for (var j = 0; j < list.Length; ++j) { res[i] = (res[i] + a[i, j] * list[j]) % key; } return res; } static int PowMod(int n, int p, int keyNum) { long _n = n % keyNum; var _p = p; var result = 1L; if ((_p & 1) == 1) { result *= _n; } while (_p > 0) { _n = _n * _n % keyNum; _p >>= 1; if ((_p & 1) == 1) { result = (result * _n) % keyNum; } } return (int)result; } }