题意
给定字符集大小 \(|A|\)、一个字符串 \(s\) 和一个包含 \(m\) 个整数的序列 \(b\)。
你可以对字符串 \(S\) 作以下的操作：
1.选择一个合法的 \(i\) ,并且令 \(k=b_i\) ;
2.取出 \(S\) 中前 \(k\) 个字符 \(Pr_k\) ;
3.取出 \(S\) 中后 \(k\) 个字符\(Su_k\) ;
4.将 \(S\) 中前 \(k\) 个字符替换成翻转后的 \(Su_k\) ;
5.将 \(S\) 中后 \(k\) 个字符替换成翻转后的 \(Pr_k\) ;
这个操作可以被执行许多次（可能是零次），任何一个 \(i\) 也可以被使用多次。
我们将字符串 \(S\) 和 \(T\) 称为相等的字符串，当且仅当存在一个操作序列，将字符串 \(S\) 变成 \(T\)。求出互不相同的字符串的个数，答案对 \(998244353\) 取模.
\(2 \leq n \leq 10^9\)，\(1 \leq m \leq min(\frac{n}{2},2 * 10^5)\)，\(1\leq |A|\leq 10^9.\)
题解
分别考虑每一段。
类似于前缀和，这一段可以通过一些操作在新的序列中正序或倒序排列。对于两侧都可以翻转的段，贡献很明显为 \(\dfrac{|A|^{len}\times (|A|^{len}-1)}{2}\)，左侧随意选，右侧把和左侧翻转相同的串减掉，除以二为了去重。
而对于一侧无法翻转的（即 \([b_m,\frac{n}{2}]\)）,可以随意选，即为 \(|A|^{n-2\times b_m}\)。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Maxn=2e5+10;
const int mod=998244353;
int a[Maxn];
int n,m,k,ans;
int ksm(int a,int b)
{if(b==0) return 1;int re=ksm(a,b>>1);re=re*re%mod;if(b&1) re=re*a%mod;return re;
}
signed main()
{cin>>n>>m>>k; ans=1;for(int i=1;i<=m;i++) cin>>a[i];for(int i=1;i<=m;i++) (ans*=(ksm(k,a[i]-a[i-1])*(ksm(k,a[i]-a[i-1])-1)%mod*ksm(2,mod-2))%mod+ksm(k,a[i]-a[i-1]))%=mod;cout<<(ans*ksm(k,n-2*a[m])%mod)<<endl;return 0;
}