0w1

IO

CFR 245 H. Queries for Number of Palindromes ( DP, Inclusion Exclusion, Palindrome, IO = = )

Problem - 245H - Codeforces題意: 給一個字串。接著 Q 筆詢問給左界右界,求對應的子字串中有多少回文子字串。資料規模: 字串長度 1 ≤ | S | ≤ 5000 1 ≤ Q ≤ 1e6 時間限制:2500 ms 空間限制:256 MB解法: 先用 O( N ^ 2 ) 預處理 is_pal[ l ][ r ],表…