結果
問題 | No.2045 Two Reflections |
ユーザー |
|
提出日時 | 2022-04-25 00:05:20 |
言語 | Kotlin (2.1.0) |
結果 |
AC
|
実行時間 | 436 ms / 2,000 ms |
コード長 | 3,101 bytes |
コンパイル時間 | 16,201 ms |
コンパイル使用メモリ | 454,628 KB |
実行使用メモリ | 69,776 KB |
最終ジャッジ日時 | 2024-09-20 03:05:09 |
合計ジャッジ時間 | 26,214 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
// 置換の積を計算fun prod(p: Array<Int>, q: Array<Int>): Array<Int> {val n = p.sizeval r = Array(n) { 0 }for (i in 0 until n) {r[i] = q[p[i]]}return r}fun makeReflectionLeft(n: Int, p: Int): Array<Int> {val x = Array(n) { it }for (i in 0 until p) {x[p - 1 - i] = i}return x}fun makeReflectionRight(n: Int, q: Int): Array<Int> {val x = Array(n) { it }for (i in n - q until n) {x[i] = 2 * n - q - i - 1}return x}fun modpow(a: Int, e: Int, mod: Long): Long {if (e == 0) return 1if (e == 1) return a % modval b = modpow(a, e / 2, mod).let { it * it } % modreturn if (e % 2 == 0) {b} else {a * b % mod}}fun main() {val (n, p, q) = readInts()if (p == 1 && q == 1) {println(1)} else if (p == 1 || q == 1) {println(2)} else {val x = makeReflectionLeft(n, p)val y = makeReflectionRight(n, q)val xy = prod(x, y)val uf = UnionFind(n)for (i in 0 until n) {uf.unite(i, xy[i])}val set = mutableSetOf<Int>()for (i in 0 until n) {set.add(uf.find(i))}val sizes = mutableSetOf<Int>()for (i in set) {sizes.add(uf.size(i))}val minfac = Array(100005) { it }for (d in 2 until 100005) {if (minfac[d] != d) continuevar i = 2while (d * i < 100005) {minfac[d * i] = minOf(minfac[d * i], d)i++}}val lcm = mutableMapOf<Int, Int>()for (size in sizes) {val pf = mutableMapOf<Int, Int>()var m = sizewhile (m > 1) {val fac = minfac[m]pf[fac] = (pf[fac] ?: 0) + 1m /= fac}for ((fac, e) in pf) {lcm[fac] = maxOf(lcm[fac] ?: 0, e)}}var ans = 2Lval mod = 998244353Lfor ((fac, e) in lcm) {ans *= modpow(fac, e, mod)ans %= mod}println(ans)}}class UnionFind(n: Int) {private val rank = IntArray(n) { 0 }private val parent = IntArray(n) { -1 }fun find(x: Int): Int {if (parent[x] < 0) {return x}parent[x] = find(parent[x])return parent[x]}fun unite(x: Int, y: Int) {val x1 = find(x)val y1 = find(y)if (x1 == y1) {return}if (rank[x1] < rank[y1]) {parent[y1] += parent[x1]parent[x1] = y1} else {parent[x1] += parent[y1]parent[y1] = x1if (rank[x1] == rank[y1]) {rank[x1]++}}}fun same(x: Int, y: Int): Boolean {return find(x) == find(y)}fun size(x: Int): Int {return -parent[find(x)]}}fun readInts() = readln().split(" ").map { it.toInt() }