P10877「KDOI-07」n1gr tS0i 题解

· · 题解

「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，中间括出来的为我们要操作的两数，则：

由于这种操作具有对称性，所以当最后不足两个数的时候可以转到前面，这样，在 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;
}