結果
問題 | No.2318 Phys Bone Maker |
ユーザー |
|
提出日時 | 2023-08-03 23:04:24 |
言語 | C# (.NET 8.0.404) |
結果 |
AC
|
実行時間 | 2,361 ms / 3,000 ms |
コード長 | 3,483 bytes |
コンパイル時間 | 10,449 ms |
コンパイル使用メモリ | 168,276 KB |
実行使用メモリ | 464,292 KB |
最終ジャッジ日時 | 2024-10-13 20:12:01 |
合計ジャッジ時間 | 32,897 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (96 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;}}