結果
問題 | No.2045 Two Reflections |
ユーザー |
|
提出日時 | 2022-02-16 21:17:41 |
言語 | Kotlin (2.1.0) |
結果 |
AC
|
実行時間 | 395 ms / 2,000 ms |
コード長 | 3,104 bytes |
コンパイル時間 | 16,168 ms |
コンパイル使用メモリ | 451,528 KB |
実行使用メモリ | 73,112 KB |
最終ジャッジ日時 | 2024-09-20 03:01:36 |
合計ジャッジ時間 | 24,178 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
import java.io.PrintWriterimport java.util.*import kotlin.math.*// 置換の積を計算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 lcm(a: Long, b: Long): Long {return a / gcd(a, b) * b}fun gcd(a: Long, b: Long): Long {if (b == 0L) return aval c = a % breturn gcd(b, c)}fun PrintWriter.solve() {val n = nextInt()val p = nextInt()val q = nextInt()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<Long>()for (i in set) {sizes.add(uf.size(i).toLong())}println(2 * sizes.fold(1L, ::lcm) % 998244353)}}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 main() {Thread(null, {val writer = PrintWriter(System.out, false)writer.solve()writer.flush()}, "solve", abs(1L.shl(26))).apply { setUncaughtExceptionHandler { _, e -> e.printStackTrace(); kotlin.system.exitProcess(1) } }.apply { start() }.join()}// region Scannerprivate var st = StringTokenizer("")private val br = System.`in`.bufferedReader()fun next(): String {while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine())return st.nextToken()}fun nextInt() = next().toInt()fun nextLong() = next().toLong()fun nextLine() = br.readLine()fun nextDouble() = next().toDouble()// endregion