G - Caeser Syllables Editorial by en_translator Editorial for printing
In this article, we denote by \([x^i] P\) the coefficient of \(x^i\) in a polynomial \(P\), and use the same notation for multi-variable polynomials too.
Reinterpretation
Let \(\mathbf{V}\) be the set of vowels.
In a symbol string \(A\), the first element of a syllable \(A_v\) satisfies one of the following:
- \(v = 1\) and \(A_v \in \mathbf{V}\)
- \(v \geq 2\), \(A_{v-1} \notin \mathbf{V}\), and \(A_v \in \mathbf{V}\).
The number of indices \(v\) equals the number of syllables in \(A\), so we will count the number of such \(v\).
One can easily check \(v = 1\), so we will consider how to count \(v \geq 2\).
The number of indices \(v \geq 2\) such that \((A_{v-1} + k) \bmod K \notin \mathbf{V}\) and \((A_v + k) \bmod K \in \mathbf{V}\)
Naively counting them costs \(\Theta(K \cdot \min(K^2, N))\) time, so we need a faster way.
Define two-variable polynomials \(A\), \(S\), and \(T\) on \(x\) and \(y\) as:
\[A := \sum_{2 \leq v \leq N} x^{K - A_{v-1}} y^{K - A_{v}},\]
\[S := \sum_{\substack{i \notin \mathbf{V} \\ 0 \leq i \leq K-1}} x^i ,\]
\[T := \sum_{\substack{j \in \mathbf{V} \\ 0 \leq j \leq K-1}} y^j. \]
Then the number of indices \(v\) such that \((A_{v-1} + k) \bmod K \notin \mathbf{V}\) and \((A_v + k) \bmod K \in \mathbf{V}\) equals \(\displaystyle \sum_{\substack{i,j \in \{k,\ k+K\}}} [x^i y^j] AST\). Hence, it suffices to find \(O(K)\) coefficients \(AST\) at specific degrees.
The coefficients of \(A\), \(S\), \(T\), and \(AST\) are all non-negative integers not exceeding \(N\). Thus, by taking a sufficiently large prime \(p\) and finding the coefficients of \(AST\) via Number-Theoretic Transform (NTT) on \(\mathbb{Z}/p\mathbb{Z}\), it will uniquely determine the actual coefficients of \(AST\).
There are multiple ways to compute \(AST\).
Method 1: utilize the form of \(S\) and \(T\) to find \(AS\) and \(AST\) in this order
\(S\) and \(T\) can be regarded as one-variable polynomials with variables \(x\) and \(y\), respectively, so the following two steps give the coefficients of \(A \times S\) and \(A \times S \times T\):
- Define one-variable polynomials on \(x\) as \(A^{(j)}(x) := [y^j]A(x,y)\). Then \([y^j](A \times S) = A^{(j)} \times S\).
- Define one-variable polynomials on \(y\) as \((A \times S)^{(i)}(y) := [x^i](A \times S)(x,y)\). Then \([x^i](A \times S \times T) = (A \times S)^{(i)} \times T\).
It suffices to compute the product of one-variable polynomials of degree \(K\), \(O(K)\) times, which can be realized with an ordinary NTT (with \(p = 998244353\)). The time complexity is \(O(N + K^2 \log K)\), which is fast enough.
Method 2: directly evaluate \(AST\)
By replacing \(y\) with \(x^{2K}\), we can treat \(A\), \(S\), and \(T\) as one-variable polynomials on \(x\) to find the product \(AST\).
\(AST\) becomes a polynomial of degree \(4K^2 + 2K\), which can be up to \(21164600\ ({} \simeq 2^{24.34})\) under the constraints of this problem. Thus, note that the prime \(p\) used for the NTT must satisfy \(2^{25}\ |\ (p-1)\) (where \(998244353\) fails).
The time complexity is \(O(N + 2 K^2 \log K)\), which is fast enough.
Sample code (C++)
#include <iostream>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
#include <vector>
using std::vector;
using std::pair;
#include <map>
using std::map;
using std::max;
using std::min;
#ifdef DEBUG
const int debug = 1;
#else
const int debug = 0;
#endif
using ll = int64_t;
using P = pair<ll, ll>;
const ll FOD = 998244353;
#include <atcoder/modint>
using mint = atcoder::modint998244353;
#include <atcoder/convolution>
using atcoder::convolution;
ll n, k, m;
uint64_t seed;
ll a[7'000'456], v[3'123];
inline void output (const ll x) {
cout << x << "\n";
}
void solve() {
vector<ll> rarr[k]; // rarr[i] := sum of x^{K-A_{i-1}} where K-A_{i-0} == i
for (ll i = 0; i < k; i++) {
rarr[i].assign(k, 0);
}
for (ll i = 1; i < n; i++) {
rarr[(k - a[i-0]) % k][(k - a[i-1]) % k] += 1;
}
vector<ll> s(k, 0), t(k, 0); // s[i] := (i notin VOWEL), t[i] := (i in VOWEL)
for (ll i = 0; i < k; i++) {
if (v[i] == 1) {
t[i] += 1;
} else {
s[i] += 1;
}
}
vector<ll> rsarr[k]; // rsarr[i] := (rarr[i] * s), x^K loops back to x^0
for (ll i = 0; i < k; i++) {
vector<ll> p = convolution(rarr[i], s);
rsarr[i].assign(k, 0);
for (ll v = 0; v < (ll)p.size(); v++) {
rsarr[i][v % k] += p[v];
}
}
vector<ll> rsbrr[k]; // rsbrr[x][y] is the transpose of rsarr[y][x]
for (ll i = 0; i < k; i++) {
rsbrr[i].resize(k);
for (ll j = 0; j < k; j++) {
rsbrr[i][j] = rsarr[j][i];
}
}
vector<ll> rst[k]; // rst[j] := (rsbrr[j] * t), y^K loops back to y^0
for (ll i = 0; i < k; i++) {
vector<ll> q = convolution(rsbrr[i], t);
rst[i].assign(k, 0);
for (ll v = 0; v < (ll)q.size(); v++) {
rst[i][v % k] += q[v];
}
}
// now rst[i][j] is [x^i y^j] (sum of x^{-A_{i-1}} y^{-A_{i-0}}) * (sum of x^NONVOWEL) * (sum of y^VOWEL)
// rst[k][k] + (A_0 + k is a vowel ? 1 : 0) is the answer for k
for (ll i = 0; i < k; i++) {
ll ans = rst[i][i];
if (v[(a[0] + i) % k]) ans += 1;
output(ans);
}
return;
}
int main (void) {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
cin >> n >> k >> seed >> m;
uint64_t state = seed;
for (ll i = 0; i < n; i++) {
if (i < m) {
cin >> a[i];
} else {
uint64_t x = (((state >> 18) ^ state) >> 27) & ((1ULL << 32) - 1);
uint64_t r = state >> 59;
uint64_t y = ((x >> r) + (x << (32-r))) & ((1ULL << 32) - 1);
a[i] = (y % (uint64_t)k) + 0;
state = (state * 6364136223846793005ULL + 2026081520260815ULL);
}
a[i] -= 0;
}
for (ll i = 0; i < k; i++) {
cin >> v[i];
}
solve();
return 0;
}
posted:
last update: