解题思路

本题属于典型的“划分型动态规划”。设字符串为 s[0..n-1]，我们用二维 DP 来描述“前缀被切成若干段且每段为回文”的方案数：

• 定义 dp[i][j]：表示把前 i 个字符（即 s[0..i-1]）切分成恰好 j 段回文子串的方案数。
• 初始条件：dp[0][0] = 1（空串切成 0 段只有 1 种方式），其余为 0。
• 状态转移：枚举最后一段的起点 t（最后一段为 s[t..i-1]，其中 j-1 ≤ t ≤ i-1） 若 s[t..i-1] 是回文，则有

题面描述

给定一个只包含小写字母的字符串 $s$（长度为 $n$）和一个整数 $k$。请将 $s$ 切分成恰好 $k$ 个非空且连续的子串，并使得每个子串都是回文串。求满足条件的切分方案数；若无解则输出 0。 切分的位置不同视为不同方案。

输入输出

输入： 第一行一个字符串 $s$。 第二行一个整数 $k$。

输出： 输出一个整数，表示将 $s$ 切分成 $k$ 个回文子串的方案数。

数据范围

• $1 \le n=|s| \le 60$
• $1 \le k \le n$
• 字符仅由小写字母组成

样例

输入

aab
2

输出

1

说明 只存在切分 aa|b。

输入

aaaa
3

输出

3

说明 可行切分为 a|a|aa、a|aa|a、aa|a|a。