问题 6755 --最少操作次数

6755: 最少操作次数★★★

时间限制: 2 Sec  内存限制: 256 MB
提交: 15  解决: 6
[提交][状态][命题人:]

题目描述

小赵有一个字符串s1,s2,…,sn和一个字符c。他希望通过最少的操作次数将字符串中的所有字符都变成c。

在一次操作中,他可以选择一个数字x(1 ≤ x ≤ n),对于每一个位置i,如果i不能被x整除,就将si替换为c。

找到将所有字符变为c所需的最少操作次数,以及在操作中应使用的x值。并且在保证操作次数最小的情况下,所有的x的总和最大。

输入

第一行包含一个整数t(1 ≤ t ≤ 10^4)————测试用例的数量。

每个测试用例的第一行包含一个整数n(3 ≤ n ≤ 3 × 10^5)和一个小写字母c————字符串的长度以及要得到的目标字符。

第二行包含一个字符串s,它是初始的字符串。

保证所有测试用例中n的总和不超过3 × 10^5。

输出

对于每个测试用例,首先输出一个整数m———— 将所有字符变成c所需的最少操作次数。

接着,输出m个整数x1, x2, …, xm— 在操作中应使用的x值,并且这m个x的总和最大。所有的x由大到小输出。

在给定的约束下,可以证明总是存在一个解。

样例输入
Copy
3
4 a
aaaa
4 a
baaa
4 b
bzyx
样例输出
Copy
0
1
4
2 
4 3

提示

第三个用例中

m = 2,x1 = 3,x2 = 2两次操作可以让字符串全变成c

m = 2,x1 = 4,x2 = 3两次操作可以让字符串全变成c

但是4 + 3 > 3  + 2,所以答案是m = 2,x1 = 4,x2 = 3。

来源

[提交][状态]