結果

問題 No.3414 Aperiodic Sequence
コンテスト
ユーザー wolgnik
提出日時 2025-12-18 14:31:36
言語 Kotlin
(2.1.0)
結果
AC  
実行時間 2,136 ms / 3,000 ms
コード長 6,745 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 19,516 ms
コンパイル使用メモリ 519,676 KB
実行使用メモリ 122,148 KB
最終ジャッジ日時 2025-12-20 23:31:59
合計ジャッジ時間 39,383 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import java.io.PrintWriter

const val MOD = 998244353L

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = PrintWriter(System.out)
    
    val (n, m) = br.readLine().split(" ").map { it.toInt() }
    val v = if (n > 0) br.readLine().split(" ").map { it.toLong() } else emptyList()
    
    val conv = Convolution()
    
    // g[k] = sum of v[i]^k の計算
    val g = calcG(v, m, conv)
    
    // メビウス関数
    val mobius = IntArray(m + 1)
    mobius[1] = 1
    val spf = IntArray(m + 1) { it }  // smallest prime factor
    
    for (i in 2..Math.sqrt(m.toDouble()).toInt()) {
        if (spf[i] == i) {
            var j = i * i
            while (j <= m) {
                if (spf[j] == j) spf[j] = i
                j += i
            }
        }
    }
    
    for (i in 2..m) {
        val p = spf[i]
        val prev = i / p
        mobius[i] = if (prev % p == 0) 0 else -mobius[prev]
    }
    
    // 約数列挙
    val divisors = Array(m + 1) { mutableListOf<Int>() }
    for (i in 1..m) {
        var j = i
        while (j <= m) {
            divisors[j].add(i)
            j += i
        }
    }
    
    // solve
    val res = StringBuilder()
    for (n in 1..m) {
        var f = 0L
        for (d in divisors[n]) {
            val mu = mobius[n / d]
            if (mu != 0) {
                val base = g[n / d]
                val pw = powMod(base, d.toLong())
                f = (f + mu * pw % MOD + MOD) % MOD
            }
        }
        if (n > 1) res.append(' ')
        res.append(f)
    }
    
    bw.println(res)
    bw.flush()
}

fun powMod(a: Long, b: Long): Long {
    var result = 1L
    var base = (a % MOD + MOD) % MOD
    var exp = b
    while (exp > 0) {
        if (exp and 1L == 1L) result = result * base % MOD
        base = base * base % MOD
        exp = exp shr 1
    }
    return result
}

fun modInverse(a: Long): Long = powMod(a, MOD - 2)

class Convolution {
    private val W = LongArray(24) { powMod(3L, (MOD - 1) shr it) }
    private val iW = LongArray(24) { powMod(332748118L, (MOD - 1) shr it) }
    
    private fun fmt(k: Int, a: LongArray) {
        for (l in k downTo 1) {
            val d = 1 shl (l - 1)
            val w = W[l]
            var i = 0
            while (i < a.size) {
                var u = 1L
                for (j in 0 until d) {
                    val s = i + j
                    val as_ = a[s]
                    val asd = a[s + d]
                    a[s] = (as_ + asd) % MOD
                    a[s + d] = u * ((as_ - asd) % MOD + MOD) % MOD
                    u = u * w % MOD
                }
                i += d * 2
            }
        }
    }
    
    private fun ifmt(k: Int, a: LongArray) {
        for (l in 1..k) {
            val d = 1 shl (l - 1)
            val w = iW[l]
            var i = 0
            while (i < a.size) {
                var u = 1L
                for (j in 0 until d) {
                    val s = i + j
                    val tmp = a[s + d] * u % MOD
                    a[s + d] = ((a[s] - tmp) % MOD + MOD) % MOD
                    a[s] = (a[s] + tmp) % MOD
                    u = u * w % MOD
                }
                i += d * 2
            }
        }
    }
    
    fun convolve(a: List<Long>, b: List<Long>): LongArray {
        val n0 = a.size + b.size - 1
        if (n0 == 1) {
            return longArrayOf(a[0] * b[0] % MOD)
        }
        
        // 小さい場合は愚直計算
        if (minOf(a.size, b.size) <= 50) {
            val res = LongArray(n0)
            for (i in a.indices) {
                for (j in b.indices) {
                    res[i + j] = (res[i + j] + a[i] * b[j]) % MOD
                }
            }
            return res
        }
        
        val k = Integer.SIZE - Integer.numberOfLeadingZeros(n0 - 1).coerceAtLeast(0)
        val n = 1 shl k
        
        val A = LongArray(n)
        val B = LongArray(n)
        for (i in a.indices) A[i] = a[i]
        for (i in b.indices) B[i] = b[i]
        
        fmt(k, A)
        fmt(k, B)
        
        for (i in 0 until n) {
            A[i] = A[i] * B[i] % MOD
        }
        
        ifmt(k, A)
        
        val invn = modInverse(n.toLong())
        val res = LongArray(n0)
        for (i in 0 until n0) {
            res[i] = A[i] * invn % MOD
        }
        return res
    }
}

fun fpsInv(f: List<Long>, deg: Int, conv: Convolution): LongArray {
    var res = longArrayOf(modInverse(f[0]))
    var d = 1
    
    while (d < deg) {
        d = d shl 1
        val fTrunc = f.subList(0, minOf(f.size, d))
        var fg = conv.convolve(res.toList(), fTrunc)
        
        // fg = -fg
        for (i in fg.indices) {
            fg[i] = (MOD - fg[i]) % MOD
        }
        
        // 必要なら拡張
        if (fg.size < d) {
            val newFg = LongArray(d)
            fg.copyInto(newFg)
            fg = newFg
        }
        
        fg[0] = (fg[0] + 2) % MOD
        
        res = conv.convolve(res.toList(), fg.toList())
        if (res.size > d) {
            res = res.copyOf(d)
        }
    }
    
    return if (res.size > deg) res.copyOf(deg) else res
}

fun calcG(v: List<Long>, m: Int, conv: Convolution): LongArray {
    val n = v.size
    if (n == 0) {
        return LongArray(m + 1)
    }
    
    val deg = m + 2
    
    // polys = [[1, -vi % mod] for vi in v]
    var polys = v.map { vi -> listOf(1L, (MOD - vi % MOD) % MOD) }.toMutableList()
    
    // 分割統治で多項式を掛け合わせる
    while (polys.size > 1) {
        val newPolys = mutableListOf<List<Long>>()
        var i = 0
        while (i < polys.size) {
            if (i + 1 < polys.size) {
                var qNew = conv.convolve(polys[i], polys[i + 1])
                if (qNew.size > deg) {
                    qNew = qNew.copyOf(deg)
                }
                newPolys.add(qNew.toList())
            } else {
                newPolys.add(polys[i])
            }
            i += 2
        }
        polys = newPolys
    }
    
    val Q = if (polys[0].size > deg) polys[0].subList(0, deg) else polys[0]
    
    // Q_deriv = [(k+1) * Q[k+1] for k in range(len(Q)-1)]
    val qDeriv = LongArray(Q.size - 1) { k -> ((k + 1).toLong() * Q[k + 1]) % MOD }
    
    // neg_Q_deriv = -Q_deriv
    val negQDeriv = LongArray(qDeriv.size) { (MOD - qDeriv[it]) % MOD }
    
    val qInv = fpsInv(Q, m + 1, conv)
    
    var s = conv.convolve(negQDeriv.toList(), qInv.toList())
    if (s.size > m + 1) {
        s = s.copyOf(m + 1)
    }
    
    // return [n] + S[:M]
    val result = LongArray(m + 1)
    result[0] = n.toLong()
    for (i in 0 until minOf(m, s.size)) {
        result[i + 1] = s[i]
    }
    
    return result
}
0