結果
問題 | No.2613 Sum of Combination |
ユーザー |
|
提出日時 | 2024-01-06 13:17:04 |
言語 | Nim (2.2.0) |
結果 |
AC
|
実行時間 | 1,314 ms / 4,500 ms |
コード長 | 3,614 bytes |
コンパイル時間 | 4,346 ms |
コンパイル使用メモリ | 66,436 KB |
実行使用メモリ | 14,400 KB |
最終ジャッジ日時 | 2024-09-28 03:47:18 |
合計ジャッジ時間 | 34,644 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 49 |
ソースコード
import strutils, sequtilsiterator readInt(): int {.closure.} =while true:let line = stdin.readLine.split.map(parseInt)for x in line:yield xconst MOD = 998244353func powMod(a, b, m: int): int =result = 1vara = a mod mb = bwhile b > 0:if (b and 1) == 1:result = result * a mod ma = a * a mod mb = b shr 1func findPrimitiveRoot(n: int): int =var phi = n - 1var factors = newSeq[int]()for i in 2..n:if i * i > phi:breakif phi mod i == 0:factors.add(i)while phi mod i == 0:phi = phi div iif phi > 1:factors.add(phi)for res in 1..<n:var ok = truefor factor in factors:if powMod(res, (n - 1) div factor, n) == 1:ok = falsebreakif ok:return res-1const primitiveRoot = findPrimitiveRoot(MOD)proc ntt(a: var seq[int]) =let n = a.lenvar m = nwhile m > 1:let mh = m shr 1let wm = powMod(primitiveRoot, (MOD - 1) div m, MOD)var w = 1for i in 0..<mh:for j in countup(i, n - 1, m):let k = j + mhleta0 = a[j]a1 = a[k]a[j] = a0 + a1if a[j] >= MOD:a[j] -= MODa[k] = (a0 - a1 + MOD) * w mod MODw = w * wm mod MODm = mhproc intt(a: var seq[int]) =let n = a.lenvar m = 2while m <= n:let mh = m shr 1let wm = powMod(primitiveRoot, MOD - 1 - (MOD - 1) div m, MOD)var w = 1for i in 0..<mh:for j in countup(i, n - 1, m):let k = j + mhleta0 = a[j]a1 = a[k] * w mod MODa[j] = a0 + a1if a[j] >= MOD:a[j] -= MODa[k] = a0 - a1if a[k] < 0:a[k] += MODw = w * wm mod MODm = m shl 1let inv = powMod(n, MOD - 2, MOD)for i in 0..<n:a[i] = a[i] * inv mod MODproc solve() =var input = readIntvar n = input()let p = input()let q = findPrimitiveRoot(p)var indexTable = newSeq[int](p)indexTable[0] = 0var k = 1for i in 0..<p - 1:indexTable[k] = ik = k * q mod pvar indexTableSum = newSeq[int](p)for i in 1..<p:indexTableSum[i] = indexTableSum[i - 1] + indexTable[i]if indexTableSum[i] >= p - 1:indexTableSum[i] -= p - 1func comb(a, b: int): int =(indexTableSum[a] - indexTableSum[b] - indexTableSum[a - b] + 2 * (p - 1)) mod (p - 1)var len = 1while len < (p - 1) * 2:len *= 2var count = newSeq[int](len)count[0] = 1while n > 0:let m = n mod pn = n div pvar a = newSeq[int](len)for i in 0..m:a[comb(m, i)] += 1ntt(count)ntt(a)for i in 0..<len:count[i] = count[i] * a[i] mod MODintt(count)for i in countdown(len - 1, p - 1):count[i - p + 1] += count[i]if count[i - p + 1] >= MOD:count[i - p + 1] -= MODcount[i] = 0var ans = 0k = 1for i in 0..<p - 1:ans = (ans + count[i] * k) mod MODk = k * q mod pecho anssolve()