結果
問題 | No.2318 Phys Bone Maker |
ユーザー | 👑 kakel-san |
提出日時 | 2023-08-03 23:04:24 |
言語 | C# (.NET 8.0.203) |
結果 |
AC
|
実行時間 | 2,402 ms / 3,000 ms |
コード長 | 3,483 bytes |
コンパイル時間 | 13,065 ms |
コンパイル使用メモリ | 167,272 KB |
実行使用メモリ | 463,964 KB |
最終ジャッジ日時 | 2024-04-21 21:48:15 |
合計ジャッジ時間 | 34,259 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 62 ms
30,848 KB |
testcase_01 | AC | 61 ms
30,836 KB |
testcase_02 | AC | 2,402 ms
463,964 KB |
testcase_03 | AC | 81 ms
31,360 KB |
testcase_04 | AC | 90 ms
31,208 KB |
testcase_05 | AC | 78 ms
31,232 KB |
testcase_06 | AC | 81 ms
31,360 KB |
testcase_07 | AC | 70 ms
31,232 KB |
testcase_08 | AC | 96 ms
31,232 KB |
testcase_09 | AC | 83 ms
31,480 KB |
testcase_10 | AC | 108 ms
31,360 KB |
testcase_11 | AC | 117 ms
31,356 KB |
testcase_12 | AC | 155 ms
31,488 KB |
testcase_13 | AC | 152 ms
33,524 KB |
testcase_14 | AC | 94 ms
31,232 KB |
testcase_15 | AC | 94 ms
31,232 KB |
testcase_16 | AC | 84 ms
31,232 KB |
testcase_17 | AC | 100 ms
31,488 KB |
testcase_18 | AC | 145 ms
31,232 KB |
testcase_19 | AC | 77 ms
31,232 KB |
testcase_20 | AC | 89 ms
31,104 KB |
testcase_21 | AC | 80 ms
31,232 KB |
testcase_22 | AC | 80 ms
31,232 KB |
testcase_23 | AC | 80 ms
31,208 KB |
testcase_24 | AC | 99 ms
31,360 KB |
testcase_25 | AC | 101 ms
31,360 KB |
testcase_26 | AC | 101 ms
31,336 KB |
testcase_27 | AC | 87 ms
31,232 KB |
testcase_28 | AC | 78 ms
31,232 KB |
testcase_29 | AC | 75 ms
31,232 KB |
testcase_30 | AC | 75 ms
31,208 KB |
testcase_31 | AC | 119 ms
31,232 KB |
testcase_32 | AC | 90 ms
31,360 KB |
testcase_33 | AC | 60 ms
30,848 KB |
testcase_34 | AC | 112 ms
32,232 KB |
testcase_35 | AC | 346 ms
74,200 KB |
testcase_36 | AC | 1,083 ms
243,488 KB |
testcase_37 | AC | 1,083 ms
239,984 KB |
testcase_38 | AC | 1,240 ms
247,516 KB |
testcase_39 | AC | 1,607 ms
343,300 KB |
testcase_40 | AC | 1,634 ms
369,836 KB |
testcase_41 | AC | 1,871 ms
409,740 KB |
testcase_42 | AC | 1,906 ms
401,192 KB |
testcase_43 | AC | 157 ms
33,408 KB |
testcase_44 | AC | 615 ms
88,564 KB |
testcase_45 | AC | 559 ms
83,488 KB |
testcase_46 | AC | 2,060 ms
401,592 KB |
testcase_47 | AC | 89 ms
186,304 KB |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (98 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using System; using static System.Console; using System.Linq; using System.Collections.Generic; class Program { public static void Main() { Solve(); } static void Solve() { var n = long.Parse(ReadLine()); var plist = PList(n); var map = new List<long>[plist.Count]; for (var i = 0; i < map.Length; ++i) map[i] = PList(plist[i]); var rev = new Dictionary<long, int>(); for (var i = 0; i < plist.Count; ++i) rev[plist[i]] = i; var dic = PDiv(n); var primes = new List<long>(dic.Select(kv => kv.Key)); primes.Sort(); var pcntmap = new int[plist.Count][]; for (var i = 0; i < pcntmap.Length; ++i) { pcntmap[i] = new int[primes.Count]; for (var j = 0; j < pcntmap[i].Length; ++j) { var tmp = plist[i]; while (tmp % primes[j] == 0) { ++pcntmap[i][j]; tmp /= primes[j]; } } } var mmap = new Dictionary<int, int>[plist.Count]; for (var i = 0; i < mmap.Length; ++i) { mmap[i] = new Dictionary<int, int>(); foreach (var r in map[map.Length - 1 - i]) { if (r == 1) continue; var next = rev[plist[i] * r]; mmap[i][next] = 1; for (var q = 0; q < primes.Count; ++q) { if (pcntmap[i][q] == pcntmap[next][q]) mmap[i][next] *= (pcntmap[i][q] + 1); } } } var dp = new long[plist.Count][]; for (var i = 0; i < dp.Length; ++i) dp[i] = new long[plist.Count]; dp[0][0] = 1; var mod = 998_244_353; for (var m = 0; m + 1 < dp.Length; ++m) for (var i = 0; i + 1 < dp[m].Length; ++i) { if (dp[m][i] == 0) continue; foreach (var r in map[map.Length - 1 - i]) { if (r == 1) continue; var next = rev[plist[i] * r]; var add = dp[m][i]; dp[m + 1][next] = (dp[m + 1][next] + dp[m][i] * mmap[i][next] % mod) % mod; } } var ans = 0L; for (var i = 1; i < dp.Length; ++i) ans = (ans + dp[i][dp[i].Length - 1]) % mod; WriteLine(ans); } static List<long> PList(long n) { var list = new List<long>(); var rev = new List<long>(); for (var i = 1L; i * i <= n; ++i) { if (n % i == 0) { list.Add(i); if (i * i < n) rev.Add(n / i); } } rev.Reverse(); list.AddRange(rev); return list; } static Dictionary<long, int> PDiv(long n) { var dic = new Dictionary<long, int>(); var tmp = n; while (tmp % 2 == 0) { tmp /= 2; if (dic.ContainsKey(2)) ++dic[2]; else dic.Add(2, 1); } for (var p = 3L; p * p <= n; p += 2) { while (tmp % p == 0) { tmp /= p; if (dic.ContainsKey(p)) ++dic[p]; else dic.Add(p, 1); } if (tmp == 1) break; } if (tmp > 1) dic.Add(tmp, 1); return dic; } }