#P18435. Palindrome
Palindrome
Palindrome
作为一位魔术师和回文串爱好者,你希望通过魔法操作使字符串变成回文串。
一次魔法操作中,可以删除字符串 的一个子串 ,并将剩余的前后两部分连接起来,消耗 单位魔法药剂。
给定一个由 个小写英文字母组成的字符串 ,以及 次魔法测试。每次测试给定 ,令 。你最多使用一次魔法操作,求使 变为回文串所需的最少药剂,以及达到该最小消耗的方案数。方案按选择的删除区间区分。
特别地,若 本来就是回文串,直接输出 0 0。
回文串从左向右与从右向左读取相同,例如 aba、ccpcc、qaq;ccpc、qhd 则不是回文串。 指下标从 到 的子串,端点均包含,下标从 开始。
输入格式
第一行包含整数 和字符串 (),字符串只包含小写英文字母。
第二行一个整数 (),表示测试次数。
接下来 行,每行两个整数 (),表示本次令 。各次测试独立,不修改原字符串。
输出格式
对每次测试输出一行两个整数,依次为最小代价及达到最小代价的方案数,以一个空格分隔。方案数不取模。
原样例 1
5 abcca
3
1 5
3 4
3 5
1 1
0 0
1 1
原样例 2
5 babdb
2
1 4
3 4
1 1
1 2