问题描述
考虑一个字符集合A（A中元素互不相同）和一个长度为 n 的字符串 S，其中 S 中的字符都属于集合 A 。
给你一个包含 m 个整数的序列 (b (b_1<b_2<dots<b_m))。你可以对字符串 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) ;
举个例子，我们令 (S)= "abcdefghi"，(k=2) 。这时(Pr_2)= "ab"，(Su)= "hi"，翻转后有 (Pr_2)= "ba"，(Su_2)= "ih"，那么最终得到的字符串 (S) 就是 "ihcdefgba"。
这个操作可以被执行许多次（可能是零次），任何一个 (i) 也可以被使用多次。
我们将字符串 (S) 和 (T) 称为相等的字符串，当且仅当存在一个操作序列，将字符串 (S) 变成 (T)。对于上面的例子来说，"abcdefghi" 和 "ihcdefgba" 是相等的。注意到 (S) 和它自己也是相等的。 你的任务很简单，数出互不相同的字符串的个数。 最终的答案可能会非常大，因此你只需要输出答案 $mod 998244353 的结果。
输入格式
第一行包括三个整数 (n)，(m) 和 (|A|（2 leq n leq 10^9，1 leq m leq min(frac{n}{2},2 * 10^5)，1leq |A|leq 10^9）)，分别是字符串的长度，序列 (b) 的大小，以及字符集 (A) 的大小。 第二行包括 (m) 个整数： (b_1,b_2,dots,b_m)。
输出格式
输出一个整数，即答案 (mod 998244353) 的结果。
样例输入
3 1 2
1
样例输出
6
解析
观察题目给我们的交换方法十分特殊，我们可以发现：对于任意((b_i,b_{i+1}])，一定可以将其关于中点翻转。那么我们对每一个这样的区间来考虑。
对于一个长度为$ len$ 的区间，分两种情况讨论：一种是右边的是左边的反串，这种情况下无论如何都不会有相同的，方案为 (|A|^{len}) ；另一种则相反，一共有 (|A|^{len}(|A|^{len}-1)) 种情况，我们可以发现每一种都有对应的相同情况被包含，故方案数为 (frac{|A|^{len}(|A|^{len}-1)}{2}) 。
注意 (b_m) 之后的一段区间是不能翻转的，故答案为 (prod frac{|A|^{len}(|A|^{len}-1)}{2} imes |A|^{n-2b_m})。
代码
#include <iostream>
#include <cstdio>
#define int long long
#define N 200002
using namespace std;
const int mod=998244353;
int n,m,a,i,b[N],ans=1;
int read()
{
char c=getchar();
int w=0;
while(c<'0'||c>'9') c=getchar();
while(c<='9'&&c>='0'){
w=w*10+c-'0';
c=getchar();
}
return w;
}
int poww(int a,int b)
{
int ans=1,base=a;
while(b){
if(b&1) ans=ans*base%mod;
base=base*base%mod;
b>>=1;
}
return ans;
}
signed main()
{
n=read();m=read();a=read();
for(i=1;i<=m;i++) b[i]=read();
int inv=poww(2,mod-2);
for(i=1;i<=m;i++){
int l=b[i]-b[i-1];
ans=ans*(poww(a,l)*((poww(a,l)-1+mod)%mod)%mod*inv%mod+poww(a,l))%mod;
}
ans=ans*poww(a,n-2*b[m])%mod;
printf("%lld
",ans);
return 0;
}