結果
問題 | No.2045 Two Reflections |
ユーザー |
|
提出日時 | 2022-03-09 03:28:56 |
言語 | Kotlin (2.1.0) |
結果 |
AC
|
実行時間 | 418 ms / 2,000 ms |
コード長 | 5,784 bytes |
コンパイル時間 | 16,227 ms |
コンパイル使用メモリ | 461,076 KB |
実行使用メモリ | 68,780 KB |
最終ジャッジ日時 | 2024-09-20 03:00:50 |
合計ジャッジ時間 | 27,679 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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 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<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] = min(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] = max(lcm[fac] ?: 0, e)}}var ans = ModInt(2)for ((fac, e) in lcm) {ans *= ModInt(fac).pow(e.toLong())}println(ans)}}// region ModIntclass ModInt(x: Long) {companion object {const val MOD = 998244353L//const val MOD = 1000000007L}constructor(y: Int) : this(y.toLong())val x = (x % MOD + MOD) % MODoperator fun plus(other: ModInt): ModInt {return ModInt(x + other.x)}operator fun minus(other: ModInt): ModInt {return ModInt(x - other.x)}operator fun times(other: ModInt): ModInt {return ModInt(x * other.x)}operator fun div(other: ModInt): ModInt {return this * other.inv()}fun pow(exp: Long): ModInt {if (exp == 0L) return ModInt(1L)var a = pow(exp shr 1)a *= aif (exp and 1L == 0L) return areturn this * a}fun inv(): ModInt {return this.pow(MOD - 2)}override fun equals(other: Any?): Boolean {if (this === other) return trueif (javaClass != other?.javaClass) return falseother as ModIntif (x != other.x) return falsereturn true}override fun hashCode(): Int {return x.hashCode()}override fun toString(): String {return "$x"}}class ModIntArray(n: Int) {private val a = LongArray(n) { 0L }constructor(n: Int, init: (Int) -> ModInt) : this(n) {for (i in 0 until n) {a[i] = init(i).x}}operator fun set(i: Int, x: ModInt) {a[i] = x.x}operator fun get(i: Int): ModInt {return ModInt(a[i])}fun joinToString(s: String): String {return a.joinToString(s)}}fun Long.toModInt(): ModInt {return ModInt(this)}fun Int.toModInt(): ModInt {return ModInt(this)}fun binomSimple(n: Long, k: Long): ModInt {var numer = ModInt(1)var denom = ModInt(1)for (i in 0 until k) {numer *= ModInt(n - i)denom *= ModInt(k - i)}return numer / denom}// endregionclass 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