Submission #68303688

---

Source Code Expand

import * as fs from 'fs';

/**
 * ローリングハッシュのパラメータ設定
 */
const BASE1: bigint = 257n;  // 第1ハッシュの基数
const BASE2: bigint = 263n;  // 第2ハッシュの基数
const MOD1: bigint = 1000000007n;  // 第1ハッシュの法
const MOD2: bigint = 1000000009n;  // 第2ハッシュの法

/**
 * 二重ハッシュ値を格納する構造体
 */
interface HashPair {
    hash1: bigint;  // 第1ハッシュ値
    hash2: bigint;  // 第2ハッシュ値
}

/**
 * 前処理データを格納する構造体
 */
interface PrecomputedData {
    forwardHash1: bigint[];   // 前方向第1ハッシュ値
    forwardHash2: bigint[];   // 前方向第2ハッシュ値
    backwardHash1: bigint[];  // 後方向第1ハッシュ値
    backwardHash2: bigint[];  // 後方向第2ハッシュ値
    power1: bigint[];         // 第1基数の累乗
    power2: bigint[];         // 第2基数の累乗
}

/**
 * 文字列の前処理を行い、ローリングハッシュに必要なデータを計算
 * @param s - 入力文字列
 * @returns 前処理されたハッシュデータ
 */
function precomputeHashes(s: string): PrecomputedData {
    const n: number = s.length;
    
    // 各配列を初期化
    const forwardHash1: bigint[] = new Array(n + 1);
    const forwardHash2: bigint[] = new Array(n + 1);
    const backwardHash1: bigint[] = new Array(n + 1);
    const backwardHash2: bigint[] = new Array(n + 1);
    const power1: bigint[] = new Array(n + 1);
    const power2: bigint[] = new Array(n + 1);
    
    // 初期値設定
    forwardHash1[0] = 0n;
    forwardHash2[0] = 0n;
    backwardHash1[n] = 0n;
    backwardHash2[n] = 0n;
    power1[0] = 1n;
    power2[0] = 1n;
    
    // 前方向ハッシュと累乗を計算
    for (let i: number = 0; i < n; i++) {
        const charCode: bigint = BigInt(s.charCodeAt(i));
        
        // 前方向ハッシュ
        forwardHash1[i + 1] = (forwardHash1[i] * BASE1 + charCode) % MOD1;
        forwardHash2[i + 1] = (forwardHash2[i] * BASE2 + charCode) % MOD2;
        
        // 累乗計算
        power1[i + 1] = (power1[i] * BASE1) % MOD1;
        power2[i + 1] = (power2[i] * BASE2) % MOD2;
    }
    
    // 後方向ハッシュを計算
    for (let i: number = n - 1; i >= 0; i--) {
        const charCode: bigint = BigInt(s.charCodeAt(i));
        
        backwardHash1[i] = (backwardHash1[i + 1] * BASE1 + charCode) % MOD1;
        backwardHash2[i] = (backwardHash2[i + 1] * BASE2 + charCode) % MOD2;
    }
    
    return {
        forwardHash1,
        forwardHash2,
        backwardHash1,
        backwardHash2,
        power1,
        power2
    };
}

/**
 * 指定範囲の前方向ハッシュ値を計算
 * @param data - 前処理データ
 * @param l - 開始位置（0-indexed）
 * @param r - 終了位置（0-indexed, 含む）
 * @returns 二重ハッシュ値
 */
function getForwardHash(data: PrecomputedData, l: number, r: number): HashPair {
    const len: number = r - l + 1;
    
    // ハッシュ値計算: hash[r+1] - hash[l] * power[len]
    let hash1: bigint = (data.forwardHash1[r + 1] - (data.forwardHash1[l] * data.power1[len]) % MOD1 + MOD1) % MOD1;
    let hash2: bigint = (data.forwardHash2[r + 1] - (data.forwardHash2[l] * data.power2[len]) % MOD2 + MOD2) % MOD2;
    
    return { hash1, hash2 };
}

/**
 * 指定範囲の後方向ハッシュ値を計算
 * @param data - 前処理データ
 * @param l - 開始位置（0-indexed）
 * @param r - 終了位置（0-indexed, 含む）
 * @returns 二重ハッシュ値
 */
function getBackwardHash(data: PrecomputedData, l: number, r: number): HashPair {
    const len: number = r - l + 1;
    
    // 後方向ハッシュ値計算: hash[l] - hash[r+1] * power[len]
    let hash1: bigint = (data.backwardHash1[l] - (data.backwardHash1[r + 1] * data.power1[len]) % MOD1 + MOD1) % MOD1;
    let hash2: bigint = (data.backwardHash2[l] - (data.backwardHash2[r + 1] * data.power2[len]) % MOD2 + MOD2) % MOD2;
    
    return { hash1, hash2 };
}

/**
 * 二重ハッシュ値が等しいかどうかを判定
 * @param hash1 - 第1ハッシュ値ペア
 * @param hash2 - 第2ハッシュ値ペア
 * @returns ハッシュ値が等しい場合true
 */
function hashEquals(hash1: HashPair, hash2: HashPair): boolean {
    return hash1.hash1 === hash2.hash1 && hash1.hash2 === hash2.hash2;
}

/**
 * 指定された範囲が回文かどうかを二重ハッシュで判定
 * @param data - 前処理データ
 * @param l - 開始位置（1-indexed）
 * @param r - 終了位置（1-indexed）
 * @returns 回文の場合true、そうでなければfalse
 */
function isPalindrome(data: PrecomputedData, l: number, r: number): boolean {
    // 1-indexedを0-indexedに変換
    const startIdx: number = l - 1;
    const endIdx: number = r - 1;
    
    // 前方向と後方向のハッシュ値を計算
    const forwardHash: HashPair = getForwardHash(data, startIdx, endIdx);
    const backwardHash: HashPair = getBackwardHash(data, startIdx, endIdx);
    
    // ハッシュ値が一致するかチェック
    return hashEquals(forwardHash, backwardHash);
}

/**
 * クエリ情報の型定義
 */
interface Query {
    l: number;  // 開始位置（1-indexed）
    r: number;  // 終了位置（1-indexed）
}

/**
 * 入力データの型定義
 */
interface InputData {
    n: number;         // 文字列の長さ
    q: number;         // クエリの数
    s: string;         // 入力文字列
    queries: Query[];  // クエリリスト
}

/**
 * 入力データをパース
 * @param input - 標準入力の内容
 * @returns パースされた入力データ
 */
function parseInput(input: string): InputData {
    const lines: string[] = input.trim().split('\n');
    const [n, q]: number[] = lines[0].split(' ').map(Number);
    const s: string = lines[1];
    
    const queries: Query[] = [];
    for (let i: number = 0; i < q; i++) {
        const [l, r]: number[] = lines[2 + i].split(' ').map(Number);
        queries.push({ l, r });
    }
    
    return { n, q, s, queries };
}

/**
 * メイン処理関数
 * @param input - 標準入力の内容
 * @returns 結果の出力文字列
 */
function solve(input: string): string {
    const data: InputData = parseInput(input);
    
    // 二重ローリングハッシュで事前計算
    const precomputedData: PrecomputedData = precomputeHashes(data.s);
    
    const results: string[] = [];
    
    // 各クエリを処理
    for (const query of data.queries) {
        if (isPalindrome(precomputedData, query.l, query.r)) {
            results.push('Yes');
        } else {
            results.push('No');
        }
    }
    
    return results.join('\n');
}

// 標準入力から読み込み
const input: string = fs.readFileSync('/dev/stdin', 'utf8');
console.log(solve(input));

Submission Info

Compile Error

Judge Result