結果

問題 No.1855 Intersected Lines
ユーザー MitarushiMitarushi
提出日時 2022-01-05 11:06:59
言語 Nim
(2.2.0)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,693 bytes
コンパイル時間 3,745 ms
コンパイル使用メモリ 67,200 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-01 11:34:15
合計ジャッジ時間 5,045 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

import strutils, sequtils, math, sugar, algorithm

const MOD = 998244353

proc mod_pow(r, x: int): int =
    var
        r = r
        x = x
    result = 1
    while x > 0:
        if x mod 2 == 1:
            result = result * r mod MOD
        r = r * r mod MOD
        x = x div 2

type Combination = ref object
    factorial: seq[int]
    factorial_inv: seq[int]

proc init_combination(n: int): Combination =
    result = Combination(
        factorial: newSeq[int](n),
        factorial_inv: newSeq[int](n)
    )

    result.factorial[0] = 1
    for i in 1..<n:
        result.factorial[i] = result.factorial[i - 1] * i mod MOD
    result.factorial_inv[n - 1] = mod_pow(result.factorial[n - 1], MOD - 2)
    for i in countdown(n - 1, 1):
        result.factorial_inv[i - 1] = result.factorial_inv[i] * i mod MOD

proc combination(c: Combination, a, b: int): int =
    if a < 0 or b < 0 or a < b:
        return 0

    c.factorial[a] * c.factorial_inv[b] mod MOD * c.factorial_inv[a - b] mod MOD

proc fft(a: var seq[int], w: seq[int]) =
    let n = a.len
    var
        m = n
        t = 1
    while m >= 2:
        let mh = m shr 1
        for i in countup(0, n-1, m):
            for s in 0..<mh:
                let
                    j = i + s
                    k = j + mh
                (a[j], a[k]) = ((a[j] + a[k]) mod MOD, (a[j] - a[k]) * w[s * t] mod MOD)
        m = mh
        t *= 2

proc ifft(a: var seq[int], w: seq[int]) =
    let n = a.len
    var
        m = 2
        t = n shr 1
    while m <= n:
        let mh = m shr 1
        for i in countup(0, n-1, m):
            for s in 0..<mh:
                let
                    j = i + s
                    k = j + mh
                a[k] *= w[n - s * t]
                (a[j], a[k]) = ((a[j] + a[k]) mod MOD, (a[j] - a[k]) mod MOD)
        m = m shl 1
        t = t shr 1

    let n_inv = mod_pow(n, MOD - 2)
    for i in 0..<n:
        a[i] *= n_inv
        a[i] = a[i] mod MOD

proc convolution(a, b: seq[int]): seq[int] =
    let n2 = max(a.len + b.len - 1, 1)
    let n = n2.nextPowerOfTwo
    var
        a = a
        b = b
    a.setLen(n)
    b.setLen(n)

    let w_root = mod_pow(3, (MOD - 1) div n)
    var w = newSeq[int](n + 1)
    w[0] = 1
    for i in 1..n:
        w[i] = w[i - 1] * w_root mod MOD

    fft(a, w)
    fft(b, w)

    result = collect(newSeq):
        for (x, y) in zip(a, b):
            x * y mod MOD

    ifft(result, w)
    result.setLen(n2)

    for idx, i in result:
        if i < 0:
            result[idx] += MOD

proc inv(x: int): int =
    mod_pow(x, MOD - 2)

proc double_factorial(c: Combination, x: int): int =
    c.factorial[x] * c.factorial_inv[x div 2] mod MOD * mod_pow(2, MOD - 1 - x div 2) mod MOD

let n = stdin.readLine.parseInt
let s = stdin.readLine

let 
    r = s.count('R')
    b = s.count('B')

if r mod 2 == 1 or b mod 2 == 1:
    echo 0
    quit()

let c = init_combination(500000)

var ans = 0

if r >= 4:
    ans += combination(c, r, 4) * double_factorial(c, r - 4) mod MOD * double_factorial(c, b)
    ans = ans mod MOD

if b >= 4:
    ans += combination(c, b, 4) * double_factorial(c, b - 4) mod MOD * double_factorial(c, r)
    ans = ans mod MOD

if r >= 2 and b >= 2:
    var acc = newSeq[int](2 * n)
    var acc_b = 0
    for i in s:
        if i == 'B':
            acc_b += 1
        else:
            acc[acc_b] += 1
    
    var acc_rev = acc
    acc_rev.reverse()
    let conv = convolution(acc, acc_rev)

    var sum = 0
    for i in 0..<2*n:
        sum += conv[i + 2 * n - 1] * i mod MOD * (b - i)
        sum = sum mod MOD

    ans += sum * double_factorial(c, r - 2) mod MOD * double_factorial(c, b - 2)
    ans = ans mod MOD

echo ans
0