CF 1065E Side Transmutations

题目描述

https://codeforces.com/problemset/problem/1065/E

简要题意：给定 $n,m$，求有多少本质不同的序列 $a_i$，每个位置可以填 $[1,m]$，现在还有 $k$ 个序列变换的方法，第 $i$ 个方法给定一个 $b_i$，保证所有 $b_i$ 互不相同且 $b_i\le \lfloor\frac{n}{2}\rfloor$，第 $i$ 种方法表示交换 $[1,b_i]$ 和 $[n-b_i+1,n]$ 的元素，交换顺序为 $i$ 和 $n-i+1$ 交换，两个序列本质不同定义为不能通过使用若干次变换方法变得相同

$n,m\le 10^9,k\le 10^5$

Solution

考虑 $burnside$，注意到有 $2^k$ 个置换，另外我们注意到将 $b_i$ 差分后不影响置换的个数，差分后我们发现不同的交换方法叠加到一起不会相互影响，那么我们直接维护 $m^{n-\sum t_i},t_i$ 表示选择的 $b_i$

#include <iostream>
#define maxn 200010
#define ll long long
using namespace std;

const int p = 998244353;
ll pow_mod(ll x, ll n) {
    ll s = 1;
    for (; n; n >>= 1, x = x * x % p)
        if (n & 1) s = s * x % p;
    return s;
}

int n, m, k;
int a[maxn], d[maxn];



int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> k >> m;
    for (int i = 1; i <= k; ++i) cin >> a[i], d[i] = a[i] - a[i - 1];
    ll sum = pow_mod(m, n), ans = sum;
    for (int i = 1; i <= k; ++i) {
        ll t = pow_mod(m, d[i]), invt = pow_mod(t, p - 2);
        ans = (ans + sum * invt) % p;
        sum = sum * (invt + 1) % p;
    } cout << ans * pow_mod(pow_mod(2, k), p - 2) % p << "\n";
    return 0;
}