‹ 上一题下一题 ›

j01980. 恰好 k 段回文切割未做

1000 ms 256 MB 测试点 10 通过率 0% 搜索 J·复赛必做100题自拟题 r2 深度优先搜索

文件读写输入j01980.in输出j01980.out

题目描述

把一个长度不超过 $16$ 的小写字母串切成恰好 $k$ 段，使每一段都是回文串。求切法方案数。

输入格式

第一行一个字符串 $t$ ；第二行一个整数 $k$ 。

输出格式

一行一个整数，方案数。

样例

输入

aab
2

输出

数据范围

对于 30% 的数据， $∣ t ∣ \leq 8$ （枚举全部切点组合可过）。
对于 60% 的数据， $∣ t ∣ \leq 12$ 。
对于 100% 的数据， $1 \leq ∣ t ∣ \leq 16$ ， $1 \leq k \leq 16$ （可能为 0）。

输入

输出

答案