自动搬运

查看原文

来自洛谷，原作者为

	xixisuper 老八可爱捏 | 塞苏帕 XI 世

搬运于2025-08-24 23:02:06，当前版本为作者最后更新于2024-08-15 16:03:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

「KDOI-07」n1gr tS0i 题解

诈骗题，采用一个先猜后证的方法。

思路

先说赛时思路，不难发现每个询问的答案与 01 串本身是什么样子没有半毛钱关系，然后发现题目不给第二组数据的解释，猜测答案可能很简单，而注意到 $2^{30}\bmod 998244353=75497471$，于是我们猜在 $n$ 足够大时答案就是 $2^n$。

对于小数据特殊情况，我们考虑写个暴力 dfs，发现只有 $n$ 为 $2$ 或 $3$ 时答案不为 $2^n$，其余数据都满足，直接一发特判交上，过了。

回来考虑一下为什么 $n$ 足够大时答案为 $2^n$，即 01 串为任意情况都合法。不难发现题目中 01 串长度与操作次数相等，我们考虑找到一种方法，使得确定最终 01 串中连续 $i$ 个字符所需的操作数为 $i$，这样确定 $n$ 个字符的操作数就一定为 $n$ 了。

我们考虑相邻的两个数的情况，由于我们已知 01 串本身不会影响答案个数，所以我们用 $0$ 表示与原串不同，$1$ 表示与原串相同，则相邻两个数的情况共有四种，分别是 $00,01,10,11$。经验证，发现只要串长足够，我们总能找到一种方式，使得操作 $2$ 次后，让 $00$ 变为 $00,01,10,11$ 任意一种，并且不改变其他位置的值。

详细操作如下：假设某 01 串的部分为 $(00)00$，中间括出来的为我们要操作的两数，则：

• 变为 $00$：进行操作 $[1,2],[1,2]$，改完得到 $(00)00$。
• 变为 $11$：进行操作 $[1,4],[3,4]$，改完得到 $(11)00$。
• 变为 $10$：进行操作 $[1,3],[2,3]$，改完得到 $(10)00$。
• 变为 $01$：进行操作 $[2,4],[3,4]$，改完得到 $(01)00$。

由于这种操作具有对称性，所以当最后不足两个数的时候可以转到前面，这样，在 $n$ 为偶数时最终的 01 串可以是任意的。当 $n$ 为奇数时其实也一样，我们分两种情况，要么第一次操作把 $[1,n]$ 全部改变，要么第一次操作不改变最后一个数，然后用剩下 $n-1$ 次操作改变 $[1,n-1]$ 的值，由于我们能保证用 $n-1$ 次操作能够得到 $[1,n-1]$ 的任意情况，则我们就能用 $n$ 次操作得到 $[1,n]$ 的所有情况，最终答案就是 $2^n$ 了。

反观操作的那部分，不难发现 01 串长度至少为 $4$，所以说当 $n$ 为 $2$ 或 $3$ 的时候特判就好了。

代码

我是蒟蒻，入门题想半天。

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const ll N=1e5+10;
const ll MOD=998244353;
inline ll read(){
	register ll f=1,x=0;
	register char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return x*f;
}
ll T,n;
char s[N];
//当然这题不用快速幂也能过
ll ksm(ll a,ll b){
	ll ret=1;
	while(b){
		if(b&1) ret=ret*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return ret;
}
int main(){
	T=read();
	while(T--){
		n=read();
		scanf("%s",s+1);
		if(n<=3){ 
			if(n==2) printf("1\n");
			if(n==3) printf("4\n");
		}
		else printf("%lld\n",ksm(2,n));
	}
	return 0;
}