题解 | 小苯的数字合并

#include<bits/stdc++.h>
using namespace std;
long long mod = 998244353;

long long q(long long a,long long b) {
    long long ans = 1;
    if(b==0) return ans;
    while(b>0) {
        if(b&1)ans = a*ans%mod;
        b = b>>1;
        a = a*a%mod;
    }
    return ans;
}
int main()
{
    int t;cin >> t;long long n,x;
    while(t--) {
        cin >> n;
        for(int i = 0;i<n;i++) {
            cin >> x;
        }
        cout << q(2,n-1) <<'\n';
    }
}

前面的题解有够快的＼(●´ϖ`●)／但可能有些不太清楚和详细，如果能看懂上面的题解，就跳过本篇吧

首先，读者要了解快速幂算法，本质上属于将指数换为二进制后，减少了乘法的次数，如有不懂，请跳转这里https://oi-wiki.org/math/binary-exponentiation/

接着，我们来解释下，为什么n个数是2的n-1次方，首先我们不妨将第i个数是否与i+1合并设为一种状态，很明显，有着n-1种状态，而每种状态都有合并和不合并两种情况，那么就一共有2的n-1次方种可能，题目得解