CF1065E Side Transmutations 做题记录

考虑一个字符集合$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_2=$ "hi"，翻转后有 $Pr_2=$ "ba"，$Su_2=$ "ih"，那么最终得到的字符串 $S$ 就是 "ihcdefgba"。

这个操作可以被执行许多次（可能是零次），任何一个 $i$ 也可以被使用多次。

我们将字符串 $S$ 和 $T$ 称为相等的字符串，当且仅当存在一个操作序列，将字符串 $S$ 变成 $T$。对于上面的例子来说，"abcdefghi" 和 "ihcdefgba" 是相等的。注意到 $S$ 和它自己也是相等的。

你的任务很简单，数出互不相同的字符串的个数。

最终的答案可能会非常大，因此你只需要输出答案 $mod$ $998244353$ 的结果。

$2 \leq n \leq 10^9$，$1 \leq m \leq min(\frac{n}{2},2 * 10^5)$，$1\leq |A|\leq 10^9$。

记字符集大小为 $V$。

观察到一次操作相当于是把 $S$ 的前 $k$ 位和 $S$ 的后 $k$ 位按位交换，即

$\operatorname{swap}_{i=1}^k(S_i,S_{n-i+1})$

那么考虑把 $S$ “对折”，问题就变成了有两个长度为 $\lfloor\frac{n}{2}\rfloor$ 的字符串 $A$ 和 $B$，每次操作可以选一个 $k\in \{b_i\}$，交换 $A_{[1,k]}$ 和 $B_{[1,k]}$，问有多少种本质不同的 $AB$（$A$ 和 $B$ 拼起来的字符串）。特别的，如果 $n$ 是奇数，那么中间那个位置永远不会被操作到，可以单独处理。

不难发现，由于操作中的 $k$ 一定是序列 $b$ 中的某个数，并且同一个 $k$ 最多只会操作一次。所以我们关心的只是 $A_{[b_{i-1}+1,b_i]}$ 是否等于 $B_{[b_{i-1}+1,b_i]}$。因为若不等则交换后结果不一样，否则结果一样。为了表述方便，不妨记它们为 $A_{[i]}$ 和 $B_{[i]}$。

下面的部分瞟了一眼题解才会。

考虑枚举每一个 $i$：

• $A_{[i]}=B_{[i]}$ 的情况：共有 $V^{|A_{[i]}|}$ 种方案；
• $A_{[i]}\not=B_{[i]}$ 的情况：共有 $\dfrac{V^{|A_{[i]}|}(V^{|B_{[i]}|}-1)}{2}$ 种方案，除以 $2$ 是因为交换后的也枚举过。

这两种情况的方案数加起来，再乘起来，最后永远不会被操作到的单独处理即可。

部分代码：

int ans=1;
for(int i=1;i<=m;i++)
{
    scanf("%d",&b[i]);
    int eq=qpow(v,b[i]-b[i-1]);
    int neq=1ll*qpow(v,b[i]-b[i-1])*(qpow(v,b[i]-b[i-1])-1)%p*qpow(2,p-2)%p;
    ans=1ll*ans*(eq+neq)%p;
}
ans=1ll*ans*qpow(v,n-b[m]-b[m])%p;