#P3350. 相似回文串

    ID: 2541 传统题 1000ms 512MiB 尝试: 153 已通过: 63 难度: 9 上传者: 标签>CF2800省选/NOI-Manacher普通并查集顶点着色完美消除序列乘法原理时间戳避免清空数组

相似回文串

题目描述

记 S(i,j)S(i,j) 为字符串 SS 的第 ii 个字母到第 jj 个字母组成的子串。

给出一个长度为 nn 由小写英文字母组成的字符串 AA 。

若字符串 BB 也由小写英文字母组成,长度为 nn,且对于任意 1≤i<j≤n1 \leq i < j \leq n 有:若 A(i,j)A(i,j) 是回文串,B(i,j)B(i,j) 也是回文串;若 A(i,j)A(i,j) 不是回文串,B(i,j)B(i,j) 也不是回文串。那么我们称 BB 与 AA 是 ayq 相似的。

求有多少个字符串与 AA ayq 相似?输出答案对 10000000071000000007 取模的余数。

输入格式

输入 11 行一个字符串 AA。

输出格式

输出一行一个数表示所求答案

abcba
15600

数据范围与约定

对于 100%100\% 的数据,n≤1000000n \leq 1000000