题意：
给你一个长为m的序列$b_i$，定义两个字符串a,b相同当前仅当a执行以下操作后能变成b：（$\rm{prefix}(x,y)$及$\rm{suffix}(x,y)$定义为串x的前/后y位组成的串）
- 选择一个$k=b_i$；
- 将$s1=\rm{prefix}(a,k)$和$s2=\rm{suffix}(a,k)$取出；
- 将s2翻转后接到头部，s1翻转后接到头部；
- 退出或重复上述操作。
求长为n，字符集大小为x的不相同串个数。
$m\leq2\times10^5,n,x\leq10^9.$
题解：
不太懂题解那个神奇的组合做法。。问到一种polya推法，重新复习了一遍polya定理。
polya定理：在一个置换群F中用t种颜色染色，第i个置换有$k_i$个循环，本质不同的染色数为
$$\begin{equation}\frac{\sum_{i=0}^{|F|}t^{k_i}}{|F|}\end{equation}$$
那么这题里的翻转就是F，可以看做是一些交换操作，如选择$k=b_1$就是交换$(1,n)(2,n-1)...(b_1,n-b_1+1)$这些数对。不难发现一个置换交换了x对数对，就有n-x个循环。
我们可以对b做差分记为c，这样每一个$c_i$对应的是一些互不相交的交换操作，同时通过$2^m$种组合可以组合出任意一种对应原序列b的方案，也就是c和b是等价的。
记$cnt_i$为$n-c_i$也就是$c_i$对应置换的循环个数，由于互不相交，任意一些$c_i$组合后的循环个数可以直接相加。所以最终答案的式子应该是：
$$\begin{equation}\frac{1}{|F|}\sum_{s\subseteq c}x^{n-\sum s}\end{equation}$$
提出$x^n$，此题有$|F|=2^m$。那个枚举c的子集求$x^{\sum s}$部分，用生成函数的思想转化，写成$\prod_{s\in c} (1+x^s)$即可。这样就可以直接算了。
由于指数上有$n-\sum s$，相当于要除法，其实可以提一个$x^{\sum c}$出来，那么后面的指数就变正了。
复杂度一个log。
code:
#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define ll long long
using namespace std;
const int N=2e5+,mod=,inv2=(mod+)/;
int n,m,x,a[N],ans;
int ksm(int x,int y){
int s=;
for (;y;y>>=,x=(ll)x*x%mod) if (y&) s=(ll)s*x%mod;
return s;
}
int main(){
scanf("%d%d%d",&n,&m,&x);
rep (i,,m) scanf("%d",&a[i]);
ans=ksm(x,n-a[m]);
for (int i=m;i;i--) a[i]-=a[i-],ans=(ll)ans*inv2%mod;
rep (i,,m) ans=(ll)ans*(+ksm(x,a[i]))%mod;
printf("%d\n",ans);
return ;
}