题意

给出正整数 $n,k$ 满足 $1\le k\le n$，构造一个长度为 $n$ 的 01 串满足它的最长回文子串为 $k$。

有一万组多测，乱搞多半完蛋。

构造方法

先找规律，$n\le 24$ 的时候直接暴力打表计算可以构造出的 $k$。

n = 1: 1 
n = 2: 1 2 
n = 3: 2 3 
n = 4: 2 3 4 (1111)
n = 5: 3 4 5 (01111)
n = 6: 3 4 5 6 (101111)
n = 7: 3 4 5 6 7 (0101111)
n = 8: 3 4 5 6 7 8 (00101111)
n = 9: 4 5 6 7 8 9 (100101111)
n = 10: 4 5 6 7 8 9 10 (1100101111)
n = 11: 4 5 6 7 8 9 10 11 (11100101111)
n = 12: 4 5 6 7 8 9 10 11 12 (111100101111)
n = 13: 4 5 6 7 8 9 10 11 12 13 (0101100101111)
n = 14: 4 5 6 7 8 9 10 11 12 13 14 (00101100101111)
n = 15: 4 5 6 7 8 9 10 11 12 13 14 15 (100101100101111)
n = 16: 4 5 6 7 8 9 10 11 12 13 14 15 16 (1100101100101111)
n = 17: 4 5 6 7 8 9 10 11 12 13 14 15 16 17 (11100101100101111)
n = 18: 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 (111100101100101111)
n = 19: 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 (0101100101100101111)
n = 20: 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 (00101100101100101111)
n = 21: 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 (100101100101100101111)
n = 22: 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 (1100101100101100101111)
n = 23: 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 (11100101100101100101111)
n = 24: 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 (111100101100101100101111)

发现 $n$ 比较大的时候最小的 $k$ 好像都是 $4$，所以每一行最后还输出了反转后字典序最大的满足 $k=4$ 的构造。

套路地，把这段结果放在 vscode 里面用高亮找重复，发现构造中总是重复出现 $\texttt{001011}$ 这个子串。

思考 $\texttt{001011}$ 的特殊意义，发现 $\texttt{001011}$ 无限重复之后不会出现长于 $4$ 的回文子串。也就是说我们可以通过多次重复它来浪费多余的长度！

所以有了如下构造算法。

• 当 $n\le 20$ 时，直接利用暴力预处理的结果，这可以规避掉所有的边界情况。

• 否则仅当 $k\ge 4$ 时有解，我们直接在字符串前面添加 $k$ 个 $\texttt{1}$，后面直接接上重复的 $\texttt{001011}$，不足一整个就取前缀。这样的正确性在于，除了最前面的 $k$ 个 $\texttt{1}$，不可能有别的回文串。

然后就做完了。

代码我写了，交到 Hcy114514 的账号上去了。

#include<bits/stdc++.h>
using namespace std;
const int N=20;
vector<int>rev[N+1];
bool vis[N+1][N+5];
int ans[N+1][N+5];

void init() {
	for(int i=1;i<=N;i++) {
		rev[i].resize(1<<i);
		for(int j=1;j<1<<i;j++)
			rev[i][j]=rev[i][j>>1]>>1|(j&1)<<i-1;
	}
	for(int n=1;n<=N;n++) {
		for(int i=0;i<1<<n;i++) {
			int mx = 0;
			for(int j=0;j<n;j++) {
				for(int k=j+1;k<=n;k++) {
					int x = (i&((1<<k)-1))>>j;
					if(x==rev[k-j][x]) mx = max(mx,k-j);
				}
			}
			vis[n][mx]=1,ans[n][mx]=i;
		}
	}
}
void hcy() {
	int n,k; cin>>n>>k;
	if(n<=20) {
		if(vis[n][k]) {
			for(int i=0;i<n;i++)
				printf("%c","PA"[ans[n][k]>>i&1]);
			printf("\n");
			return;
		} else {
			printf("NIE\n");
			return;
		}
	}
	if(k>=4) {
		for(int i=1;i<=k;i++) printf("A");
		for(int i=0;i<n-k;i++)
			printf("%c","PPAPAA"[i%6]);
		printf("\n");
	} else {
		printf("NIE\n");
		return;
	}
}
int main(){
	init();
	int T; cin>>T;
	while(T--) hcy();
	return 0;
}