公式

G - Caeser Syllables 解説 by en_translator 印刷ページ


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;
}

投稿日時:
最終更新: