这场比赛还是有收获的，特别是对 E 题的坚持。

但比赛体验真的比较糟糕，在学校里比赛就感觉特别吵，而且 D 题开始还读错了题目，E 题没有在赛时通过，最后上蓝再次失败。

A

水题。

但开始时十分紧张，题目读了好久才明白，浪费了一些时间。

大概很多人一起比赛无形之中会增加紧张感吧。

B

水题。

做题开始有点儿状态了。

C

状态正常！

D

开始看错了题目，以为是要整个串的和是 $p$ 的倍数，当然推不出什么结果，就直接看了别人的结论。

赛后发现读错题了之后就简单了，有一个显然的 dp， 然后它又可以很显然地化成 $(p-2)^{n-1}(p-1)$ 的形式。

E

最大的“亮点”，赛场上想了一会儿模拟了几个样例居然想到了正解。

不过实现起来就是另外一回事了，感觉细节特别特别多，然后就是……赛后补了一早上才过。

大致的思路其实很好想，就是每次分段一层一层的剖下来，然后对于每一个找出最多的把其它都改成它，然后就遇到了一堆的问题：

1. 如何快速找到最后一层的一个所对应的其它
2. 若最后一层仍然回文怎么办
3. 奇数个的如何匹配中间

然后赛场上想到了设一个在最后串中左边有 $a$ 个， 右边有 $b$ 个就是每次加俩 $b$ 再加俩 $a$, 然后用栈处理有奇数个层的多出来的那个，先把所有当个的拉出来就好了，总和肯定不超过 $n$。于是直接噼里啪啦写代码，写完错误一堆。

主要问题是考场上怕来不及，很多地方都没有想清楚，比如栈变化的那个操作序列怎么生成，又比如最后仍然回文应该怎么处理……

于是第二天还调了一早上才终于过了， $100+$ 行的代码。

最后一看题解发现人家 $50$ 几行就写完了。

好吧好吧，不过调这题大概真的锻炼了思维的严谨性，就把代码拿来纪念吧。

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
std::vector<int> tmp;
const int N = 500005, SPJ = 19;
int k, n, sta[N], tub[28], ans, top, len, opt[N], pre[N], tns;
char st[N], st2[N];
bool check() {
	for(int i = 1; i <= len; i++)
		if(st2[i] != st2[len-i+1]) return false;
	return true;
}
void doit(int opt) {
	for(int i = 0; i < 26; i++) tub[i] = 0;
	for(int i = 0; i < (signed)tmp.size(); i++) 
	    if(opt != SPJ) tub[st[tmp[i]]-'a'] ++;
	    else if(st[tmp[i]]-'a' != st2[tmp[i]]-'a') tub[st[tmp[i]]-'a'] ++;
	int maxj = 27;
	for(int i = 0; i < 26; i++) 
		if(tub[i] > tub[maxj]) maxj = i;
	int cnt = 0;
	for(int i = 0; i < (signed)tmp.size(); i++) 
	    cnt += (st[tmp[i]] != maxj+'a'), st2[tmp[i]] = maxj + 'a';
	if(opt == SPJ) {
	    if(tmp[0] != (len+1)/2) tns = std::min(tns, cnt - pre[tmp[0]]);
	}
	else {
	    pre[tmp[0]] = cnt;
	    ans += cnt;
	}
}
int makeopt(int x) {
	if(x == 0) return 0;
	opt[1] = x;
	int j = 1;
	for(int i = x-1; i >= 1; i--) {
		opt[++j] = i;
		for(int k = j-1; k >= 1; k--) 
			opt[++j] = opt[k];
	}
	return j;
}
int main() {
	scanf("%d%s", &k, st+1);
	n = strlen(st+1);
	if(k == 0) {
	    if(n == 1) return puts("impossible"), 0;
	    ans = 1;
	    for(int i = 1; i <= n; i++)
	        if(st[i] != st[n-i+1]) ans = 0;
	    printf("%d", ans);
	    return 0;
	}
	for(int i = 1; i <= n; i++) st2[i] = st[i];
	if(k > 20 || (n >> (k-1)) == 0 || (n >> k) == 1) return puts("impossible"), 0;
	len = n;
	for(int j = 1; j <= k; j++) {
		if(len & 1) {
			int a = len >> 1;
			tmp.clear();
			int end = makeopt(top);
			tmp.push_back(a+1);
			for(int i = a+1, w = 1; i <= n && w <= end; w++) {
				i += 2*a + sta[opt[w]] + 1;
				tmp.push_back(i);
			}
			doit(0);
			sta[++top] = 1;
		}
		else sta[++top] = 0;
		len >>= 1;
	}
	for(int i = 1; i <= len; i++) {
		int a = i-1, b = len-i;
		tmp.clear();
		int end = makeopt(top);
		tmp.push_back(i);
		for(int j = i, c = 1, w = 1; j <= n && w <= end; c++, w++) {
			if(c%2 == 1) j = j + 2*b + sta[opt[w]] + 1;
			else j = j + 2*a + sta[opt[w]] + 1;
			tmp.push_back(j);
		}
		doit(0);
	}
	if(len != 0 && check()) {
	    tns = 0x3f3f3f3f;
	    for(int i = 1; i <= len; i++) {
    		int a = i-1, b = len-i;
    		tmp.clear();
    		int end = makeopt(top);
    		tmp.push_back(i);
    		for(int j = i, c = 1, w = 1; j <= n && w <= end; c++, w++) {
    			if(c%2 == 1) j = j + 2*b + sta[opt[w]] + 1;
    			else j = j + 2*a + sta[opt[w]] + 1;
    			tmp.push_back(j);
    		}
    		doit(SPJ);
    	}
    	ans = ans + tns;
	}
	printf("%d\n", ans);
	return 0;
}