第5回 ドワンゴからの挑戦状 本選 D - Parentheses Inversions

もともと分割統治NTTでO(N log^2 N)想定だったのを高速化して出題した。
D - Parentheses Inversions

問題

長さNの括弧列Sがある。1からNまでの整数の上の置換pであって、Sをpで置換したものがバランスの取れた括弧列であるときのpの転倒数を合計し、mod 10^9+7で答えよ。

• 2 <= N <= 500000
• Sに含まれる'('と')'の個数は等しい。

解法

(省略)

実装上の注意点

• とにかく手数が多い。係数として掛けるべき数も複雑なので、愚直解と比較すべきである。

提出: Submission #3868089 - 第5回 ドワンゴからの挑戦状 本選 (rust)

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($format:expr) => (write!(out,$format).unwrap());
        ($format:expr, $($args:expr),+) => (write!(out,$format,$($args),*).unwrap())
    }
    input! {
        n: usize,
        s: chars,
    }
    let m = n / 2;
    let mut fac = vec![ModInt::new(1); n + 1];
    let mut invfac = vec![ModInt::new(1); n + 1];
    for i in 1 .. n + 1 {
        fac[i] = fac[i - 1] * ModInt::new(i as i64);
    }
    invfac[n] = fac[n].inv();
    for i in (0 .. n).rev() {
        invfac[i] = invfac[i + 1] * ModInt::new(i as i64 + 1);
    }
    let mut catalan = vec![ModInt::new(0); m + 1];
    for i in 0 .. m + 1 {
        catalan[i] = fac[2 * i] * invfac[i] * invfac[i + 1];
    }
    let mut sinv: i64 = 0;
    let mut close = 0;
    for i in 0 .. n {
        if s[i] == '(' {
            sinv += close;
        } else {
            close += 1;
        }
    }
    let mut tot = ModInt::new(0);
    tot += catalan[m] * fac[m].pow(2) * ModInt::new(m as i64 * (m - 1) as i64)
        * ModInt::new(2).inv(); // '('-'(', ')'-')'
    let mut d = vec![ModInt::new(0); m + 1]; // ')' - '('
    let mut e = vec![ModInt::new(0); m + 1]; // '(' - ')'
    // t^2 * P' / (1-4t)
    for i in 2 .. m + 1 {
        d[i] = ModInt::new(i as i64 - 1) * catalan[i - 1];
    }
    for i in 0 .. m {
        d[i + 1] += d[i] * ModInt::new(4);
    }
    for i in 0 .. m + 1 {
        e[i] = catalan[i] * ModInt::new(i as i64).pow(2) - d[i];
    }
    let opposite = ModInt::new(m as i64 * m as i64 - sinv);
    let sinv = ModInt::new(sinv);
    tot += (e[m] * sinv + d[m] * opposite) * fac[m - 1].pow(2);
    puts!("{}\n", tot);
}

まとめ

かなり難しくしてしまったが、最終防衛問題としての役割を果たしてくれてよかった。