Codeforces 1065E. Side Transmutations (Burnside's Lemma)

日付: 11月 18, 2018

[Problem - 1065E - Codeforces](https://codeforces.com/problemset/problem/1065/E)
## Problem
Consider a set of strings $\{S |S_i \in A,|S|=n\}$. Given an array $b$ of $m$ integers, define an operation as:
1. Choose some value in $b$, called $k$
2. Get the subsequence of $S$ that is the prefix $k$ and suffix $k$, and reverse it

The operations can be applied arbitrary times. If string $T$ can be transformed from $S$ by such operations, they are equivalent. The task is to calculate the number of equivalence classes of the set.

**Constraints**: $2\le n \le 10^9,1\le m \le min(\frac{n}{2}, 2\cdot 10^5), 1 \le |A| \le 10^9, 1 \le b_1 < b_2 < \cdots < b_m \le \frac{n}{2}$
## Solution
The problem can be solved with **Burnside's lemma**.$$|Classes|=\frac{1}{|G|}\sum_{\pi \in G}I(\pi)$$

Firstly, we can observe that for any $b_i$, if it is choosed twice, the string will not change. Thus any **invariant permutation** can be represented by a bitmask, $|G|=2^m$.

If we choose some elements in $b$, the string $S$ is divided into several segments, alternating in two cases, remain origin or is the reverse of its symetric segment. We want to calculate the number of **invariant points**, that is, $I(\pi)$. For the first case any character can be chosen. For the second case, we can choose for one segment arbitrarily, but its symetric segment is fixed. $I(\pi)=|A|^{n-s}$, where $s$ is half of the total length of segments in the second case.

We iterator on the elements of $b$ and maintain two values: $x=\sum |A|^{n-s_p}$, $y=\sum|A|^{n+s_p}$. For each element of $b$, there are two cases, whether or not this element is chosen. If this element is chosen, then, segments before the current value is flipped over.

## Code
```c++
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int, int>;
#define FI(i,a,b) for(int i=(a);i<=(b);++i)
#define FD(i,b,a) for(int i=(b);i>=(a);--i)
#define DEBUG(x) cerr << #x << ": " << (x) << endl;
constexpr LL inv(LL x, LL m) { return x > m ? inv(x % m, m) : x > 1 ? inv(m % x, m) * (m - m / x) % m : x; }
constexpr LL mpow(LL a, LL k, LL m) { LL r(1); for (a %= m; k; k >>= 1, a = a * a % m) if (k & 1)r = r * a % m; return r; }

int main() {
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    vector<int> B(m + 1);
    FI(i, 1, m) scanf("%d", &B[i]);
    const int Mod = 998244353;
    LL a = mpow(k, n, Mod), b = mpow(k, n, Mod);
    FI(i, 1, m) {
        LL na = b * inv(mpow(k, B[i], Mod), Mod) % Mod;
        LL nb = a * mpow(k, B[i], Mod) % Mod;
        a = (a + na) % Mod;
        b = (b + nb) % Mod;
    }
    LL ans = a * inv(mpow(2, m, Mod), Mod) % Mod;
    cout << ans << endl;
}
```

KONGROOの基地

このブログを検索

Codeforces 1065E. Side Transmutations (Burnside's Lemma)

コメント

コメントを投稿