Side Transmutations（组合数学+快速幂）

原题：

题目不短，但是容易理解。
最后题目要统计的是“不相等”的字符串个数，是一道组合计数的题目，显然需要我们把各个部分的情形数乘起来得到答案。

最容易算的部分是剪掉两端各b[m]后留下的不能被翻转的“中间”部分，每个字符都有$\left | A \right |$∣A∣种可能，故共有$\left | A \right |^{n-2*b_{m}}$∣A∣n−2∗bm​种情形

两边可翻转的部分没办法一眼看出计算方法，我们可以从简单的m=1入手思考
设翻转的字符数为r，则一段长度为r的序列共有$S=\left | A \right |^r$S=∣A∣r种可能
我们把左边要翻转的串叫做L，右边叫做R
情形一：R翻转后=L，这种情况恰有S种
情形二：R翻转后≠L，那么翻转前后视为同一个串，这种情况有$C_{S}^{2}$CS2​种
故一共有$C_{S}^{2}+S=\frac{S(S+1)}{2}$CS2​+S=2S(S+1)​种情形

再对m进行推广，注意到$b_{i+1}$bi+1​的翻转对于$b_i$bi​内的情形数不产生影响，因此只需要计算$b_i+1$bi​+1到$b_{i+1}$bi+1​的情形数就行了（即$r=b_{i+1}-b_i$r=bi+1​−bi​时的情形数）

最后审视全部计算过程，发现只需要快速幂就足够完成计算了，时间复杂度$O(m logn)$O(mlogn)

代码：

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll PP=998244353;
const int MAXN=2e5+10;
int n,m,A,i,b[MAXN];
ll ans,t,p,x,f[10000];

ll ex(ll x,int y) //calc x*(A^y) 
{
	ll i=0;
	while (y)
	{
		if (y&1) x=(x*f[i])%PP;
		y=y>>1;
		i++;
	}
	return x;
}	

int main()
{
	cin>>n>>m>>A;
	for (i=1;i<=m;i++) scanf("%d",&b[i]);
	A=A%PP;
	f[0]=A%PP;b[0]=0;
	for (i=1;i<=100;i++) f[i]=(f[i-1]*f[i-1])%PP;
	ans=1;t=1;
	for (i=1;i<=m;i++)
	{
		t=ex(1,b[i]-b[i-1]);
		t=(t*(t+1)/2)%PP;
		ans=(ans*t)%PP;
	}
	ans=ex(ans,n-2*b[m]);
	cout<<ans;
	return 0;
}