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 <math><semantics><mrow><mo>{</mo><mi>S</mi><mi mathvariant="normal">∣</mi><msub><mi>S</mi><mi>i</mi></msub><mo>∈</mo><mi>A</mi><mo separator="true">,</mo><mi mathvariant="normal">∣</mi><mi>S</mi><mi mathvariant="normal">∣</mi><mo>=</mo><mi>n</mi><mo>}</mo></mrow><annotation encoding="application/x-tex">\{S |S_i \in A,|S|=n\}</annotation></semantics></math>{S∣Si∈A,∣S∣=n}. Given an array <math><semantics><mrow><mi>b</mi></mrow><annotation encoding="application/x-tex">b</annotation></semantics></math>b of <math><semantics><mrow><mi>m</mi></mrow><annotation encoding="application/x-tex">m</annotation></semantics></math>m integers, define an operation as:
1. Choose some value in <math><semantics><mrow><mi>b</mi></mrow><annotation encoding="application/x-tex">b</annotation></semantics></math>b, called <math><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math>k
2. Get the subsequence of <math><semantics><mrow><mi>S</mi></mrow><annotation encoding="application/x-tex">S</annotation></semantics></math>S that is the prefix <math><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math>k and suffix <math><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math>k, and reverse it

The operations can be applied arbitrary times. If string <math><semantics><mrow><mi>T</mi></mrow><annotation encoding="application/x-tex">T</annotation></semantics></math>T can be transformed from <math><semantics><mrow><mi>S</mi></mrow><annotation encoding="application/x-tex">S</annotation></semantics></math>S by such operations, they are equivalent. The task is to calculate the number of equivalence classes of the set.

**Constraints**: <math><semantics><mrow><mn>2</mn><mo>≤</mo><mi>n</mi><mo>≤</mo><mn>1</mn><msup><mn>0</mn><mn>9</mn></msup><mo separator="true">,</mo><mn>1</mn><mo>≤</mo><mi>m</mi><mo>≤</mo><mi>m</mi><mi>i</mi><mi>n</mi><mo>(</mo><mfrac><mi>n</mi><mn>2</mn></mfrac><mo separator="true">,</mo><mn>2</mn><mo>⋅</mo><mn>1</mn><msup><mn>0</mn><mn>5</mn></msup><mo>)</mo><mo separator="true">,</mo><mn>1</mn><mo>≤</mo><mi mathvariant="normal">∣</mi><mi>A</mi><mi mathvariant="normal">∣</mi><mo>≤</mo><mn>1</mn><msup><mn>0</mn><mn>9</mn></msup><mo separator="true">,</mo><mn>1</mn><mo>≤</mo><msub><mi>b</mi><mn>1</mn></msub><mo>&lt;</mo><msub><mi>b</mi><mn>2</mn></msub><mo>&lt;</mo><mo>⋯</mo><mo>&lt;</mo><msub><mi>b</mi><mi>m</mi></msub><mo>≤</mo><mfrac><mi>n</mi><mn>2</mn></mfrac></mrow><annotation encoding="application/x-tex">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 &lt; b_2 &lt; \cdots &lt; b_m \le \frac{n}{2}</annotation></semantics></math>2≤n≤109,1≤m≤min(2n,2⋅105),1≤∣A∣≤109,1≤b1<b2<⋯<bm≤2n
## Solution
The problem can be solved with **Burnside's lemma**.<math><semantics><mrow><mi mathvariant="normal">∣</mi><mi>C</mi><mi>l</mi><mi>a</mi><mi>s</mi><mi>s</mi><mi>e</mi><mi>s</mi><mi mathvariant="normal">∣</mi><mo>=</mo><mfrac><mn>1</mn><mrow><mi mathvariant="normal">∣</mi><mi>G</mi><mi mathvariant="normal">∣</mi></mrow></mfrac><munder><mo>∑</mo><mrow><mi>π</mi><mo>∈</mo><mi>G</mi></mrow></munder><mi>I</mi><mo>(</mo><mi>π</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">|Classes|=\frac{1}{|G|}\sum_{\pi \in G}I(\pi)</annotation></semantics></math>∣Classes∣=∣G∣1π∈G∑I(π)

Firstly, we can observe that for any <math><semantics><mrow><msub><mi>b</mi><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">b_i</annotation></semantics></math>bi, if it is choosed twice, the string will not change. Thus any **invariant permutation** can be represented by a bitmask, <math><semantics><mrow><mi mathvariant="normal">∣</mi><mi>G</mi><mi mathvariant="normal">∣</mi><mo>=</mo><msup><mn>2</mn><mi>m</mi></msup></mrow><annotation encoding="application/x-tex">|G|=2^m</annotation></semantics></math>∣G∣=2m.

If we choose some elements in <math><semantics><mrow><mi>b</mi></mrow><annotation encoding="application/x-tex">b</annotation></semantics></math>b, the string <math><semantics><mrow><mi>S</mi></mrow><annotation encoding="application/x-tex">S</annotation></semantics></math>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, <math><semantics><mrow><mi>I</mi><mo>(</mo><mi>π</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">I(\pi)</annotation></semantics></math>I(π). 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. <math><semantics><mrow><mi>I</mi><mo>(</mo><mi>π</mi><mo>)</mo><mo>=</mo><mi mathvariant="normal">∣</mi><mi>A</mi><msup><mi mathvariant="normal">∣</mi><mrow><mi>n</mi><mo>−</mo><mi>s</mi></mrow></msup></mrow><annotation encoding="application/x-tex">I(\pi)=|A|^{n-s}</annotation></semantics></math>I(π)=∣A∣n−s, where <math><semantics><mrow><mi>s</mi></mrow><annotation encoding="application/x-tex">s</annotation></semantics></math>s is half of the total length of segments in the second case.

We iterator on the elements of <math><semantics><mrow><mi>b</mi></mrow><annotation encoding="application/x-tex">b</annotation></semantics></math>b and maintain two values: <math><semantics><mrow><mi>x</mi><mo>=</mo><mo>∑</mo><mi mathvariant="normal">∣</mi><mi>A</mi><msup><mi mathvariant="normal">∣</mi><mrow><mi>n</mi><mo>−</mo><msub><mi>s</mi><mi>p</mi></msub></mrow></msup></mrow><annotation encoding="application/x-tex">x=\sum |A|^{n-s_p}</annotation></semantics></math>x=∑∣A∣n−sp, <math><semantics><mrow><mi>y</mi><mo>=</mo><mo>∑</mo><mi mathvariant="normal">∣</mi><mi>A</mi><msup><mi mathvariant="normal">∣</mi><mrow><mi>n</mi><mo>+</mo><msub><mi>s</mi><mi>p</mi></msub></mrow></msup></mrow><annotation encoding="application/x-tex">y=\sum|A|^{n+s_p}</annotation></semantics></math>y=∑∣A∣n+sp. For each element of <math><semantics><mrow><mi>b</mi></mrow><annotation encoding="application/x-tex">b</annotation></semantics></math>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)

コメント

コメントを投稿