結果

問題 No.3392 Count 23578 Sequence
コンテスト
ユーザー LyricalMaestro
提出日時 2026-05-25 02:14:36
言語 Rust
(1.94.0 + proconio + num + itertools)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
WA  
実行時間 -
コード長 3,729 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,398 ms
コンパイル使用メモリ 206,708 KB
実行使用メモリ 185,988 KB
最終ジャッジ日時 2026-05-25 02:15:57
合計ジャッジ時間 35,916 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16 WA * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use proconio::input;
use std::collections::BTreeMap;

const H: u128 = 9007199254740997;

fn main() {
    input! {
        n: usize,
        a: [i128; n],
    }

    let mut answer: u128 = n as u128;

    if n == 1 {
        println!("{}", answer);
        return;
    }

    let m = n - 1;

    let mut diff_a = Vec::with_capacity(m);
    for i in 0..m {
        diff_a.push(a[i + 1] - a[i]);
    }

    // 座標圧縮
    let mut vals = diff_a.clone();
    vals.sort();
    vals.dedup();

    let mut mp = BTreeMap::new();
    for (i, v) in vals.iter().enumerate() {
        mp.insert(*v, (i + 1) as u128);
    }

    let diff_a2: Vec<u128> = diff_a.iter().map(|x| mp[x]).collect();

    let max_a = *diff_a2.iter().max().unwrap();
    let b_base = max_a + 1;

    // forward hash
    let mut forward_hash = vec![0_u128; m];
    let mut h = 0_u128;
    for i in 0..m {
        h *= b_base;
        h %= H;
        h += diff_a2[i];
        h %= H;
        forward_hash[i] = h;
    }

    // backward hash
    let mut backward_hash = vec![0_u128; m];
    h = 0;
    for i in (0..m).rev() {
        h *= b_base;
        h %= H;
        h += diff_a2[i];
        h %= H;
        backward_hash[i] = h;
    }

    let mut pow_b = vec![0_u128; n];
    let mut cur = 1_u128;
    for i in 0..n {
        pow_b[i] = cur;
        cur *= b_base;
        cur %= H;
    }

    let solve = |forward_hash: &Vec<u128>,
                 backward_hash: &Vec<u128>,
                 pow_b: &Vec<u128>,
                 i: usize,
                 l: usize|
     -> bool {
        let b = (backward_hash[i - l] + H
            - ((backward_hash[i] * pow_b[l]) % H))
            % H;

        let f = (forward_hash[i + l] + H
            - ((forward_hash[i] * pow_b[l]) % H))
            % H;

        b == f
    };

    // 奇数長回文
    for i in 0..m {
        let left = i;
        let right = m - 1 - i;
        let max_length = left.min(right);

        let mut low = 0_usize;
        let mut high = max_length;

        while high > low + 1 {
            let mid = (high + low) / 2;
            if solve(&forward_hash, &backward_hash, &pow_b, i, mid) {
                low = mid;
            } else {
                high = mid;
            }
        }

        if solve(&forward_hash, &backward_hash, &pow_b, i, high) {
            answer += 1 + high as u128;
        } else {
            answer += 1 + low as u128;
        }
    }

    let solve2 = |forward_hash: &Vec<u128>,
                  backward_hash: &Vec<u128>,
                  pow_b: &Vec<u128>,
                  i: usize,
                  l: usize|
     -> bool {
        let b = (backward_hash[i - l] + H
            - ((backward_hash[i + 1] * pow_b[l]) % H))
            % H;

        let f = (forward_hash[i + 1 + l] + H
            - ((forward_hash[i] * pow_b[l]) % H))
            % H;

        b == f
    };

    // 偶数長回文
    if m >= 2 {
        for i in 0..m - 1 {
            if diff_a2[i] != diff_a2[i + 1] {
                continue;
            }

            let left = i;
            let right = m - 1 - (i + 1);
            let max_length = left.min(right);

            let mut low = 0_usize;
            let mut high = max_length;

            while high > low + 1 {
                let mid = (high + low) / 2;
                if solve2(&forward_hash, &backward_hash, &pow_b, i, mid) {
                    low = mid;
                } else {
                    high = mid;
                }
            }

            if solve2(&forward_hash, &backward_hash, &pow_b, i, high) {
                answer += 1 + high as u128;
            } else {
                answer += 1 + low as u128;
            }
        }
    }

    println!("{}", answer);
}
0