魔法权值

[编程题]魔法权值

热度指数：3176 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给出 n 个字符串，对于每个 n 个排列 p，按排列给出的顺序(p[0] , p[1] … p[n-1])依次连接这 n 个字符串都能得到一个长度为这些字符串长度之和的字符串。所以按照这个方法一共可以生成 n! 个字符串。

一个字符串的权值等于把这个字符串循环左移 i 次后得到的字符串仍和原字符串全等的数量，i 的取值为 [1 , 字符串长度]。求这些字符串最后生成的 n! 个字符串中权值为 K 的有多少个。

注：定义把一个串循环左移 1 次等价于把这个串的第一个字符移动到最后一个字符的后面。

输入描述:

每组测试用例仅包含一组数据，每组数据第一行为两个正整数 n, K ， n 的大小不超过 8 ， K 不超过 200。接下来有 n 行，每行一个长度不超过 20 且仅包含大写字母的字符串。

输出描述:

输出一个整数代表权值为 K 的字符串数量。

示例1

输入

3 2
AB
RAAB
RA

输出

算法知识视频讲解

头大的烦恼

发表于 2021-04-23 15:32:13

此题首先注意到最多不超过8个字符串，用全排列也只有2的8次方之多，所以首先可以确定是可以穷举，然后拼接完的字符串最长长度也不超过200，可以判断真的一直左移算法的循环次数也不会太大。所以这道题我采取的方式是穷举。以下是关键步骤的解析。1 - 穷举产生全排列：使用的方式是迭代，利用辅助vec 展开全文