結果
問題 | No.2613 Sum of Combination |
ユーザー |
|
提出日時 | 2024-01-06 03:09:24 |
言語 | Nim (2.2.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,517 bytes |
コンパイル時間 | 3,269 ms |
コンパイル使用メモリ | 65,920 KB |
実行使用メモリ | 14,464 KB |
最終ジャッジ日時 | 2024-09-28 03:46:43 |
合計ジャッジ時間 | 27,027 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 WA * 1 |
other | AC * 10 WA * 39 |
ソースコード
import strutils, sequtilsconst MOD = 998244353func powMod(a, b, m: int64): int64 =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: int64): int64 =var phi = n - 1var factors = newSeq[int64](0)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[int64]) =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[int64]) =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() =let input = stdin.readLine.split.map(parseBiggestInt)var n = input[0]let p = input[1]let q = findPrimitiveRoot(p)var indexTable = newSeq[int64](p)indexTable[0] = 0var k = 1for i in 0..<p - 1:indexTable[k] = ik = k * q mod pvar indexTableSum = newSeq[int64](p)for i in 1..<p:indexTableSum[i] = indexTableSum[i - 1] + indexTable[i]if indexTableSum[i] >= p:indexTableSum[i] -= pfunc comb(a, b: int64): int64 =(indexTableSum[a] - indexTableSum[b] - indexTableSum[a - b] + 3 * (p - 1)) mod (p - 1)var len = 1while len < (p - 1) * 2:len *= 2var count = newSeq[int64](len)count[0] = 1while n > 0:let m = n mod pn = n div pvar a = newSeq[int64](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()