Thanks to everyone who participated in this round! I hope you enjoyed the problems! Apologies for the overly simplistic Div2D and the trivial Div1D(and the statements with poor readability). I think that the whole difficulty of Div1D lies in how people hack the solutions of other participants: if nobody hacks, this problem is easier than Div1C, but if somebody hacks, it becomes hard. I will explain this in more detail in the tutorial below.
2288A - Youmu Konpaku and the Duel
The last operation can only be an Attack.
You can only Charge several times first and then Attack several times.
If your sequence of operations contains a segment [Attack, several Charges, several Attacks], move the leading Attack behind those Charges. The total damage cannot decrease.
Therefore we may assume that all Attacks are performed after all Charges. Then you can enumerate how many Charges are performed at the very beginning, and simulate how many Attacks are needed to defeat the youkai.
Depending on the implementation, your time complexity is either $$$O(x)$$$ or $$$O(x\log x)$$$ per test case.
#include <algorithm>
#include <cstdio>
int main() {
int t;
if (scanf("%d", &t) != 1) return 0;
while (t-- > 0) {
int x;
if (scanf("%d", &x) != 1) return 0;
int best = x; // attacking x times with no charges always works
for (int a = 0; a <= x; ++a) {
int damage = 0, stacks = a, moves = a;
while (damage < x) {
if (stacks == 0) { // every remaining attack deals 1 damage
moves += x - damage;
break;
}
damage += stacks + 1;
--stacks;
++moves;
}
best = std::min(best, moves);
}
printf("%d\n", best);
}
return 0;
}
2288B1 - Yukari Yakumo and the Boundary Stones (Easy Version) / 2287A1 - Yukari Yakumo and the Boundary Stones (Easy Version)
Use dynamic programming.
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
if (scanf("%d", &t) != 1)
return 0;
while (t--) {
int x, y, m;
if (scanf("%d %d %d", &x, &y, &m) != 3)
return 0;
char buf[256];
if (scanf("%255s", buf) != 1)
return 0;
string s(buf);
int n = x + y;
int maxI = n + m + 2;
vector<int> dp(maxI + 2, -1), nd(maxI + 2, -1);
dp[y] = n;
int ans = n; // the empty prefix
for (char ch : s) {
fill(nd.begin(), nd.end(), -1);
for (int i = 0; i <= maxI; ++i) {
int u = dp[i];
if (u < 0)
continue;
if (ch == '+') {
if (i >= 1)
nd[i + 1] = max(nd[i + 1], u + 1);
else if (u >= 1)
nd[1] = max(nd[1], u);
} else {
if (i >= 1)
nd[i - 1] = max(nd[i - 1], u);
if (u - i >= 1)
nd[i] = max(nd[i], u - 1);
}
}
dp.swap(nd);
for (int i = 0; i <= maxI; ++i)
ans = max(ans, dp[i]);
}
printf("%d\n", ans);
}
return 0;
}
2288B2 - Yukari Yakumo and the Boundary Stones (Hard Version) / 2287A2 - Yukari Yakumo and the Boundary Stones (Hard Version)
We need $$$k$$$ to take at least $$$n+1$$$ different values. What do we need for that?
In the vast majority of cases the returned $$$k$$$ points at a \texttt{+}, and either $$$k$$$ is already the end of the string or $$$k+1$$$ points at a \texttt{-}.
A repeated structure \texttt{+-} is useless.
To make good use of every character, a naive idea is to spread the possible values of $$$k$$$ as evenly as possible. For that we should use more \texttt{-} characters.
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
if (scanf("%d", &t) != 1)
return 0;
string spell = "+";
while ((int)spell.size() < 997)
spell += "--+";
while (t--) {
int n;
scanf("%d", &n);
printf("%s\n", spell.c_str());
fflush(stdout);
int k;
scanf("%d", &k);
int y = (k == 0 ? 0 : (k + 2) / 3);
printf("%d\n", n + y);
fflush(stdout);
}
return 0;
}
2288C - Reimu Hakurei and the Youkai
We only need to track how many attacks a youkai needs before it leaves the field, which is $$$c_i = \left\lceil \frac{a_i}{x} \right\rceil$$$.
Sort $$$c$$$ and ignore the maximum.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n;
long long x;
cin >> n >> x;
vector<long long> h(n);
for (int i = 0; i < n; i++) {
long long a;
cin >> a;
h[i] = (a + x - 1) / x; // hits needed to defeat this youkai
}
sort(h.begin(), h.end());
long long ans = 0;
// Leave the largest h as the final surviving youkai.
for (int i = 0; i < n - 1; i++) {
ans = max(ans, h[i] - (long long)(i + 1));
}
cout << ans << '\n';
}
return 0;
}
2288D - Satori Komeiji and the Metro / 2287B - Satori Komeiji and the Metro
At least one of the two trains must stop at every station. Why?
The other train only stops at a prefix and a suffix. Why?
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T1> istream& operator>>(istream& cin, vector<T1>& a) { for (auto& x : a) cin >> x; return cin; }
void Solve() {
int n;
cin >> n;
vector<ll>a(n);
cin >> a;
auto ck = [&](ll x)->bool {
ll tmp = 0;
vector<int>stop(n);
for (int i = 0; i < n; i++) {
tmp += a[i];
if (tmp > x)stop[i] = 1;
}
tmp = 0;
for (int i = n - 1; i >= 0; i--) {
tmp += a[i];
if (tmp > x)stop[i] = 1;
}
tmp = 0;
for (int i = 0; i < n; i++) {
if (stop[i])tmp += a[i];
}
return tmp > x;
};
ll res = 0;
ll tmp = 1ll << 50;
while (tmp) {
if (ck(res + tmp))res += tmp;
tmp >>= 1;
}
cout << res + 1 << endl;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T = 1;
cin >> T;
while (T--) Solve();
return 0;
}
2288E - Cirno and the Math Problem / 2287C - Cirno and the Math Problem
It is obvious that we should use bitsets.
The final time complexity is $$$O\left(\frac{n_{\max} m_{\max} \log m_{\max}}{w}\right)$$$, where $$$w = 64$$$. Do not worry about TLE: this code runs fast and is completely fine.
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define N 50010
int pri[N];
int mu[N];
void Init() {
mu[1] = 1;
vector<int>primes;
for (int x = 2; x < N; ++x) {
if (!pri[x]) {
primes.push_back(x);
mu[x] = -1;
}
for (int p : primes) {
if (x * p >= N) break;
pri[x * p] = true;
if (x % p == 0) {
mu[x * p] = 0;
break;
}
else {
mu[x * p] = -mu[x];
}
}
}
}
struct que
{
int id;
int n, m;
bool operator<(const que& o)const {
if (o.m != m)return m < o.m;
return id < o.id;
}
};
void Solve() {
int q;
cin >> q;
vector<que>t(q);
vector<int>ans(q);
for (int i = 0; i < q; i++) {
cin >> t[i].n >> t[i].m;
t[i].id = i;
}
sort(all(t));
int p = 0;
int m = 50000;
vector<bitset<50000>>dp(m + 1);
dp[1][0] = 1;
bitset<50000>res;
res[0] = 1;
while (p < q && t[p].m == 1) {
ans[t[p].id] = res[t[p].n - 1];
p++;
}
dp[1] <<= 1;
for (int j = 2; j <= m; j++) {
bitset<50000>tmp;
for (int i = 1; i * i <= j; i++) {
if (j % i)continue;
if (mu[i]) {
tmp ^= dp[i];
}
if (j / i != i) {
if (mu[j / i]) {
tmp ^= dp[j / i];
}
}
}
tmp[0] = 1;
res ^= tmp;
while (p < q && t[p].m == j) {
ans[t[p].id] = res[t[p].n - 1];
p++;
}
tmp <<= 1;
for (int i = 1; i * i <= j; i++) {
if (j % i)continue;
dp[i] ^= tmp;
if (j / i != i) {
dp[j / i] ^= tmp;
}
}
}
for (auto& u : ans)cout << u << endl;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
Init();
Solve();
return 0;
}
2287D - Patchouli Knowledge and the String
How would you solve this problem if there were no hacks?
Is there any way to compute the hashes of the length-$$$\ell$$$ prefixes of $$$a_0, a_1, \dots, a_{n-1}$$$ quickly?
Classic string hashing is great: it supports rolling hashes, but it also makes us fragile when facing attacks.
PS: This problem accepts using a high-resolution clock as the RNG seed. Among the approaches known today, if you do not use it, you have to use a cryptographic hash (such as SHA-256). Also, banning timers is technically unrealistic, and it would expose the intended solution of this problem.
PS: During testing, Codex used fixed seeds and one RNG-generated weight array, and compared every character naively whenever the hashes were equal. I successfully constructed data that hacks this approach (a 120s TLE), and I proved that even with four independent RNGs, this approach is still fragile as long as the seeds are fixed (I constructed a 20s TLE). But I guess that during the Div1 contest nobody will try to hack this approach.
// Generated by OpenAI Codex (AI)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 998244353;
int pw(int a, int b) {
int ans = 1;
while (b) {
if (b & 1) ans = (ll)ans * a % MOD;
a = (ll)a * a % MOD;
b >>= 1;
}
return ans;
}
struct NTT {
int n;
vector<int> rev, roots;
NTT(int n) : n(n), rev(n), roots(n) {
for (int i = 1; i < n; i++) {
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? n >> 1 : 0);
}
for (int len = 1; len < n; len <<= 1) {
int w = pw(3, (MOD - 1) / (len << 1));
roots[len] = 1;
for (int j = 1; j < len; j++) {
roots[len + j] = (ll)roots[len + j - 1] * w % MOD;
}
}
}
void transform(vector<int>& a, bool inverse = false) {
for (int i = 0; i < n; i++) if (i < rev[i]) swap(a[i], a[rev[i]]);
for (int len = 1; len < n; len <<= 1) {
for (int i = 0; i < n; i += len << 1) {
for (int j = 0; j < len; j++) {
int x = a[i + j];
int y = (ll)a[i + j + len] * roots[len + j] % MOD;
a[i + j] = x + y;
if (a[i + j] >= MOD) a[i + j] -= MOD;
a[i + j + len] = x - y;
if (a[i + j + len] < 0) a[i + j + len] += MOD;
}
}
}
if (inverse) {
reverse(a.begin() + 1, a.end());
int inv = pw(n, MOD - 2);
for (int& x : a) x = (ll)x * inv % MOD;
}
}
};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void solve() {
int n;
string s;
cin >> n >> s;
vector<int> p(n);
for (int& x : p) cin >> x, --x;
vector<int> pi(n);
for (int i = 1; i < n; i++) {
int j = pi[i - 1];
while (j && s[i] != s[j]) j = pi[j - 1];
if (s[i] == s[j]) j++;
pi[i] = j;
}
if (n % (n - pi.back()) == 0 && pi.back()) {
cout << n << '\n';
return;
}
int len = 1;
while (len < 2 * n - 1) len <<= 1;
NTT ntt(len);
vector<int> spectrum(len), weight(n), work(len);
for (int i = 0; i < n; i++) {
spectrum[i] = s[i] - 'a';
weight[i] = uniform_int_distribution<int>(1, MOD - 1)(rng);
}
ntt.transform(spectrum);
s += s;
vector<pair<int, int>> hashes(n);
auto check = [&](int k) {
fill(work.begin(), work.end(), 0);
for (int i = 0; i < k; i++) work[(n - p[i]) % n] = weight[i];
ntt.transform(work);
for (int i = 0; i < len; i++) work[i] = (ll)work[i] * spectrum[i] % MOD;
ntt.transform(work, true);
for (int i = 0; i < n; i++) {
int value = work[i];
if (i + n < 2 * n - 1) {
value += work[i + n];
if (value >= MOD) value -= MOD;
}
hashes[i] = {value, i};
}
sort(hashes.begin(), hashes.end());
for (int l = 0; l < n; ) {
int r = l + 1;
while (r < n && hashes[r].first == hashes[l].first) r++;
for (int i = l; i < r; i++) {
for (int j = l; j < i; j++) {
int u = hashes[i].second, v = hashes[j].second;
bool same = true;
for (int h = 0; h < k; h++) {
if (s[u + p[h]] != s[v + p[h]]) {
same = false;
break;
}
}
if (same) return true;
}
}
l = r;
}
return false;
};
int lo = 0, hi = n;
while (hi - lo > 1) {
int mid = (lo + hi) >> 1;
if (check(mid)) lo = mid;
else hi = mid;
}
cout << lo << '\n';
}
int main() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
int t;
cin >> t;
while (t--) solve();
return 0;
}
//I must have missed the evolution memo.
//In case I never coding, good afternoon, good evening, and good night.
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING
#define _SILENCE_CXX20_CISO646_REMOVED_WARNING
#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable : 4700)
#include "bits/stdc++.h"
#include <random>
#include <array>
#include <chrono>
#if 0
#include "atcoder/all"
using namespace atcoder;
#endif
using namespace std;
template<typename T1, typename T2> istream& operator>>(istream& cin, pair<T1, T2>& a) { return cin >> a.first >> a.second; }
template<typename T1> istream& operator>>(istream& cin, vector<T1>& a) { for (auto& x : a) cin >> x; return cin; }
template<typename T1> istream& operator>>(istream& cin, valarray<T1>& a) { for (auto& x : a) cin >> x; return cin; }
template<typename T1, typename T2> ostream& operator<<(ostream& cout, const pair<T1, T2>& a) { return cout << a.first << ' ' << a.second; }
template<typename T1, typename T2> ostream& operator<<(ostream& cout, const vector<pair<T1, T2>>& a) { for (auto& x : a) cout << x << '\n'; return cout; }
template<typename T1> ostream& operator<<(ostream& cout, const vector<T1>& a) { int n = a.size(); if (!n) return cout; cout << a[0]; for (int i = 1; i < n; i++) cout << ' ' << a[i]; return cout; }
template<typename T1, typename T2> bool cmin(T1& x, const T2& y) { if (y < x) { x = y; return 1; } return 0; }
template<typename T1, typename T2> bool cmax(T1& x, const T2& y) { if (x < y) { x = y; return 1; } return 0; }
template<typename T1> vector<T1> range(T1 l, T1 r, T1 step = 1) { assert(step > 0); int n = (r - l + step - 1) / step, i; vector<T1> res(n); for (i = 0; i < n; i++) res[i] = l + step * i; return res; }
template<typename T1> basic_string<T1> operator*(const basic_string<T1>& s, int m) { auto r = s; m *= s.size(); r.resize(m); for (int i = s.size(); i < m; i++) r[i] = r[i - s.size()]; return r; }
#if !defined(ONLINE_JUDGE)&&defined(LOCAL)
#include "my_header\debug.h"
#else
#define dbg(...) ;
#define dbgn(...) ;
#endif
typedef unsigned int ui;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
#define all(x) (x).begin(),(x).end()
#define Endl endl
#define THREADCNT 8
#define MY_NAME "LNight"
#define NAN 0.1217728619
#define small_queue(name, ...) priority_queue<__VA_ARGS__, vector<__VA_ARGS__>, greater<__VA_ARGS__>>name
#define small_queue_type(...) priority_queue<__VA_ARGS__, vector<__VA_ARGS__>, greater<__VA_ARGS__>>
namespace atcoder {
namespace internal {
#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value ||
std::is_same<T, __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int128 =
typename std::conditional<std::is_same<T, __uint128_t>::value ||
std::is_same<T, unsigned __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using make_unsigned_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value,
__uint128_t,
unsigned __int128>;
template <class T>
using is_integral = typename std::conditional<std::is_integral<T>::value ||
is_signed_int128<T>::value ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value&&
std::is_signed<T>::value) ||
is_signed_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<(is_integral<T>::value&&
std::is_unsigned<T>::value) ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<
is_signed_int128<T>::value,
make_unsigned_int128<T>,
typename std::conditional<std::is_signed<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type>::type;
#else
template <class T> using is_integral = typename std::is_integral<T>;
template <class T>
using is_signed_int =
typename std::conditional<is_integral<T>::value&& std::is_signed<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<is_integral<T>::value&&
std::is_unsigned<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<is_signed_int<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type;
#endif
template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
template <class T> using to_unsigned_t = typename to_unsigned<T>::type;
} // namespace internal
} // namespace atcoder
namespace atcoder {
namespace internal {
// @param m `1 <= m`
// @return x mod m
constexpr long long safe_mod(long long x, long long m) {
x %= m;
if (x < 0) x += m;
return x;
}
// Fast modular multiplication by barrett reduction
// Reference: https://en.wikipedia.org/wiki/Barrett_reduction
// NOTE: reconsider after Ice Lake
struct barrett {
unsigned int _m;
unsigned long long im;
// @param m `1 <= m`
explicit barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}
// @return m
unsigned int umod() const { return _m; }
// @param a `0 <= a < m`
// @param b `0 <= b < m`
// @return `a * b % m`
unsigned int mul(unsigned int a, unsigned int b) const {
// [1] m = 1
// a = b = im = 0, so okay
// [2] m >= 2
// im = ceil(2^64 / m)
// -> im * m = 2^64 + r (0 <= r < m)
// let z = a*b = c*m + d (0 <= c, d < m)
// a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im
// c*r + d*im < m * m + m * im < m * m + 2^64 + m <= 2^64 + m * (m + 1) < 2^64 * 2
// ((ab * im) >> 64) == c or c + 1
unsigned long long z = a;
z *= b;
#ifdef _MSC_VER
unsigned long long x;
_umul128(z, im, &x);
#else
unsigned long long x =
(unsigned long long)(((unsigned __int128)(z)*im) >> 64);
#endif
unsigned long long y = x * _m;
return (unsigned int)(z - y + (z < y ? _m : 0));
}
};
// @param n `0 <= n`
// @param m `1 <= m`
// @return `(x ** n) % m`
constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
if (m == 1) return 0;
unsigned int _m = (unsigned int)(m);
unsigned long long r = 1;
unsigned long long y = safe_mod(x, m);
while (n) {
if (n & 1) r = (r * y) % _m;
y = (y * y) % _m;
n >>= 1;
}
return r;
}
// Reference:
// M. Forisek and J. Jancina,
// Fast Primality Testing for Integers That Fit into a Machine Word
// @param n `0 <= n`
constexpr bool is_prime_constexpr(int n) {
if (n <= 1) return false;
if (n == 2 || n == 7 || n == 61) return true;
if (n % 2 == 0) return false;
long long d = n - 1;
while (d % 2 == 0) d /= 2;
constexpr long long bases[3] = { 2, 7, 61 };
for (long long a : bases) {
long long t = d;
long long y = pow_mod_constexpr(a, t, n);
while (t != n - 1 && y != 1 && y != n - 1) {
y = y * y % n;
t <<= 1;
}
if (y != n - 1 && t % 2 == 0) {
return false;
}
}
return true;
}
template <int n> constexpr bool is_prime = is_prime_constexpr(n);
// @param b `1 <= b`
// @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
a = safe_mod(a, b);
if (a == 0) return { b, 0 };
// Contracts:
// [1] s - m0 * a = 0 (mod b)
// [2] t - m1 * a = 0 (mod b)
// [3] s * |m1| + t * |m0| <= b
long long s = b, t = a;
long long m0 = 0, m1 = 1;
while (t) {
long long u = s / t;
s -= t * u;
m0 -= m1 * u; // |m1 * u| <= |m1| * s <= b
// [3]:
// (s - t * u) * |m1| + t * |m0 - m1 * u|
// <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
// = s * |m1| + t * |m0| <= b
auto tmp = s;
s = t;
t = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
// by [3]: |m0| <= b/g
// by g != b: |m0| < b/g
if (m0 < 0) m0 += b / s;
return { s, m0 };
}
// Compile time primitive root
// @param m must be prime
// @return primitive root (and minimum in now)
constexpr int primitive_root_constexpr(int m) {
if (m == 2) return 1;
if (m == 167772161) return 3;
if (m == 469762049) return 3;
if (m == 754974721) return 11;
if (m == 998244353) return 3;
int divs[20] = {};
divs[0] = 2;
int cnt = 1;
int x = (m - 1) / 2;
while (x % 2 == 0) x /= 2;
for (int i = 3; (long long)(i)*i <= x; i += 2) {
if (x % i == 0) {
divs[cnt++] = i;
while (x % i == 0) {
x /= i;
}
}
}
if (x > 1) {
divs[cnt++] = x;
}
for (int g = 2;; g++) {
bool ok = true;
for (int i = 0; i < cnt; i++) {
if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
ok = false;
break;
}
}
if (ok) return g;
}
}
template <int m> constexpr int primitive_root = primitive_root_constexpr(m);
// @param n `n < 2^32`
// @param m `1 <= m < 2^32`
// @return sum_{i=0}^{n-1} floor((ai + b) / m) (mod 2^64)
unsigned long long floor_sum_unsigned(unsigned long long n,
unsigned long long m,
unsigned long long a,
unsigned long long b) {
unsigned long long ans = 0;
while (true) {
if (a >= m) {
ans += n * (n - 1) / 2 * (a / m);
a %= m;
}
if (b >= m) {
ans += n * (b / m);
b %= m;
}
unsigned long long y_max = a * n + b;
if (y_max < m) break;
// y_max < m * (n + 1)
// floor(y_max / m) <= n
n = (unsigned long long)(y_max / m);
b = (unsigned long long)(y_max % m);
std::swap(m, a);
}
return ans;
}
} // namespace internal
} // namespace atcoder
namespace atcoder {
namespace internal {
struct modint_base {};
struct static_modint_base : modint_base {};
template <class T> using is_modint = std::is_base_of<modint_base, T>;
template <class T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;
} // namespace internal
template <int m, std::enable_if_t<(1 <= m)>* = nullptr>
struct static_modint : internal::static_modint_base {
using mint = static_modint;
public:
static constexpr int mod() { return m; }
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
static_modint() : _v(0) {}
template <class T, internal::is_signed_int_t<T>* = nullptr>
static_modint(T v) {
long long x = (long long)(v % (long long)(umod()));
if (x < 0) x += umod();
_v = (unsigned int)(x);
}
template <class T, internal::is_unsigned_int_t<T>* = nullptr>
static_modint(T v) {
_v = (unsigned int)(v % umod());
}
unsigned int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
_v -= rhs._v;
if (_v >= umod()) _v += umod();
return *this;
}
mint& operator*=(const mint& rhs) {
unsigned long long z = _v;
z *= rhs._v;
_v = (unsigned int)(z % umod());
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
if (prime) {
assert(_v);
return pow(umod() - 2);
}
else {
auto eg = internal::inv_gcd(_v, m);
assert(eg.first == 1);
return eg.second;
}
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
private:
unsigned int _v;
static constexpr unsigned int umod() { return m; }
static constexpr bool prime = internal::is_prime<m>;
};
template <int id> struct dynamic_modint : internal::modint_base {
using mint = dynamic_modint;
public:
static int mod() { return (int)(bt.umod()); }
static void set_mod(int m) {
assert(1 <= m);
bt = internal::barrett(m);
}
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
dynamic_modint() : _v(0) {}
template <class T, internal::is_signed_int_t<T>* = nullptr>
dynamic_modint(T v) {
long long x = (long long)(v % (long long)(mod()));
if (x < 0) x += mod();
_v = (unsigned int)(x);
}
template <class T, internal::is_unsigned_int_t<T>* = nullptr>
dynamic_modint(T v) {
_v = (unsigned int)(v % mod());
}
unsigned int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
_v += mod() - rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator*=(const mint& rhs) {
_v = bt.mul(_v, rhs._v);
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
auto eg = internal::inv_gcd(_v, mod());
assert(eg.first == 1);
return eg.second;
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
private:
unsigned int _v;
static internal::barrett bt;
static unsigned int umod() { return bt.umod(); }
};
template <int id> internal::barrett dynamic_modint<id>::bt(998244353);
using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
using modint = dynamic_modint<-1>;
namespace internal {
template <class T>
using is_static_modint = std::is_base_of<internal::static_modint_base, T>;
template <class T>
using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>;
template <class> struct is_dynamic_modint : public std::false_type {};
template <int id>
struct is_dynamic_modint<dynamic_modint<id>> : public std::true_type {};
template <class T>
using is_dynamic_modint_t = std::enable_if_t<is_dynamic_modint<T>::value>;
} // namespace internal
} // namespace atcoder
namespace atcoder {
namespace internal {
#if __cplusplus >= 202002L
using std::bit_ceil;
#else
// @return same with std::bit::bit_ceil
unsigned int bit_ceil(unsigned int n) {
unsigned int x = 1;
while (x < (unsigned int)(n)) x *= 2;
return x;
}
#endif
// @param n `1 <= n`
// @return same with std::bit::countr_zero
int countr_zero(unsigned int n) {
#ifdef _MSC_VER
unsigned long index;
_BitScanForward(&index, n);
return index;
#else
return __builtin_ctz(n);
#endif
}
// @param n `1 <= n`
// @return same with std::bit::countr_zero
constexpr int countr_zero_constexpr(unsigned int n) {
int x = 0;
while (!(n & (1 << x))) x++;
return x;
}
} // namespace internal
} // namespace atcoder
namespace atcoder {
namespace internal {
template <class mint,
int g = internal::primitive_root<mint::mod()>,
internal::is_static_modint_t<mint>* = nullptr>
struct fft_info {
static constexpr int rank2 = countr_zero_constexpr(mint::mod() - 1);
std::array<mint, rank2 + 1> root; // root[i]^(2^i) == 1
std::array<mint, rank2 + 1> iroot; // root[i] * iroot[i] == 1
std::array<mint, std::max(0, rank2 - 2 + 1)> rate2;
std::array<mint, std::max(0, rank2 - 2 + 1)> irate2;
std::array<mint, std::max(0, rank2 - 3 + 1)> rate3;
std::array<mint, std::max(0, rank2 - 3 + 1)> irate3;
fft_info() {
root[rank2] = mint(g).pow((mint::mod() - 1) >> rank2);
iroot[rank2] = root[rank2].inv();
for (int i = rank2 - 1; i >= 0; i--) {
root[i] = root[i + 1] * root[i + 1];
iroot[i] = iroot[i + 1] * iroot[i + 1];
}
{
mint prod = 1, iprod = 1;
for (int i = 0; i <= rank2 - 2; i++) {
rate2[i] = root[i + 2] * prod;
irate2[i] = iroot[i + 2] * iprod;
prod *= iroot[i + 2];
iprod *= root[i + 2];
}
}
{
mint prod = 1, iprod = 1;
for (int i = 0; i <= rank2 - 3; i++) {
rate3[i] = root[i + 3] * prod;
irate3[i] = iroot[i + 3] * iprod;
prod *= iroot[i + 3];
iprod *= root[i + 3];
}
}
}
};
template <class mint, internal::is_static_modint_t<mint>* = nullptr>
void butterfly(std::vector<mint>& a) {
int n = int(a.size());
int h = internal::countr_zero((unsigned int)n);
static const fft_info<mint> info;
int len = 0; // a[i, i+(n>>len), i+2*(n>>len), ..] is transformed
while (len < h) {
if (h - len == 1) {
int p = 1 << (h - len - 1);
mint rot = 1;
for (int s = 0; s < (1 << len); s++) {
int offset = s << (h - len);
for (int i = 0; i < p; i++) {
auto l = a[i + offset];
auto r = a[i + offset + p] * rot;
a[i + offset] = l + r;
a[i + offset + p] = l - r;
}
if (s + 1 != (1 << len))
rot *= info.rate2[countr_zero(~(unsigned int)(s))];
}
len++;
}
else {
// 4-base
int p = 1 << (h - len - 2);
mint rot = 1, imag = info.root[2];
for (int s = 0; s < (1 << len); s++) {
mint rot2 = rot * rot;
mint rot3 = rot2 * rot;
int offset = s << (h - len);
for (int i = 0; i < p; i++) {
auto mod2 = 1ULL * mint::mod() * mint::mod();
auto a0 = 1ULL * a[i + offset].val();
auto a1 = 1ULL * a[i + offset + p].val() * rot.val();
auto a2 = 1ULL * a[i + offset + 2 * p].val() * rot2.val();
auto a3 = 1ULL * a[i + offset + 3 * p].val() * rot3.val();
auto a1na3imag =
1ULL * mint(a1 + mod2 - a3).val() * imag.val();
auto na2 = mod2 - a2;
a[i + offset] = a0 + a2 + a1 + a3;
a[i + offset + 1 * p] = a0 + a2 + (2 * mod2 - (a1 + a3));
a[i + offset + 2 * p] = a0 + na2 + a1na3imag;
a[i + offset + 3 * p] = a0 + na2 + (mod2 - a1na3imag);
}
if (s + 1 != (1 << len))
rot *= info.rate3[countr_zero(~(unsigned int)(s))];
}
len += 2;
}
}
}
template <class mint, internal::is_static_modint_t<mint>* = nullptr>
void butterfly_inv(std::vector<mint>& a) {
int n = int(a.size());
int h = internal::countr_zero((unsigned int)n);
static const fft_info<mint> info;
int len = h; // a[i, i+(n>>len), i+2*(n>>len), ..] is transformed
while (len) {
if (len == 1) {
int p = 1 << (h - len);
mint irot = 1;
for (int s = 0; s < (1 << (len - 1)); s++) {
int offset = s << (h - len + 1);
for (int i = 0; i < p; i++) {
auto l = a[i + offset];
auto r = a[i + offset + p];
a[i + offset] = l + r;
a[i + offset + p] =
(unsigned long long)(mint::mod() + l.val() - r.val()) *
irot.val();
;
}
if (s + 1 != (1 << (len - 1)))
irot *= info.irate2[countr_zero(~(unsigned int)(s))];
}
len--;
}
else {
// 4-base
int p = 1 << (h - len);
mint irot = 1, iimag = info.iroot[2];
for (int s = 0; s < (1 << (len - 2)); s++) {
mint irot2 = irot * irot;
mint irot3 = irot2 * irot;
int offset = s << (h - len + 2);
for (int i = 0; i < p; i++) {
auto a0 = 1ULL * a[i + offset + 0 * p].val();
auto a1 = 1ULL * a[i + offset + 1 * p].val();
auto a2 = 1ULL * a[i + offset + 2 * p].val();
auto a3 = 1ULL * a[i + offset + 3 * p].val();
auto a2na3iimag =
1ULL *
mint((mint::mod() + a2 - a3) * iimag.val()).val();
a[i + offset] = a0 + a1 + a2 + a3;
a[i + offset + 1 * p] =
(a0 + (mint::mod() - a1) + a2na3iimag) * irot.val();
a[i + offset + 2 * p] =
(a0 + a1 + (mint::mod() - a2) + (mint::mod() - a3)) *
irot2.val();
a[i + offset + 3 * p] =
(a0 + (mint::mod() - a1) + (mint::mod() - a2na3iimag)) *
irot3.val();
}
if (s + 1 != (1 << (len - 2)))
irot *= info.irate3[countr_zero(~(unsigned int)(s))];
}
len -= 2;
}
}
}
template <class mint, internal::is_static_modint_t<mint>* = nullptr>
std::vector<mint> convolution_naive(const std::vector<mint>& a,
const std::vector<mint>& b) {
int n = int(a.size()), m = int(b.size());
std::vector<mint> ans(n + m - 1);
if (n < m) {
for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++) {
ans[i + j] += a[i] * b[j];
}
}
}
else {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ans[i + j] += a[i] * b[j];
}
}
}
return ans;
}
template <class mint, internal::is_static_modint_t<mint>* = nullptr>
std::vector<mint> convolution_fft(std::vector<mint> a, std::vector<mint> b) {
int n = int(a.size()), m = int(b.size());
int z = (int)internal::bit_ceil((unsigned int)(n + m - 1));
a.resize(z);
internal::butterfly(a);
b.resize(z);
internal::butterfly(b);
for (int i = 0; i < z; i++) {
a[i] *= b[i];
}
internal::butterfly_inv(a);
a.resize(n + m - 1);
mint iz = mint(z).inv();
for (int i = 0; i < n + m - 1; i++) a[i] *= iz;
return a;
}
} // namespace internal
template <class mint, internal::is_static_modint_t<mint>* = nullptr>
std::vector<mint> convolution(std::vector<mint>&& a, std::vector<mint>&& b) {
int n = int(a.size()), m = int(b.size());
if (!n || !m) return {};
int z = (int)internal::bit_ceil((unsigned int)(n + m - 1));
assert((mint::mod() - 1) % z == 0);
if (std::min(n, m) <= 60) return convolution_naive(a, b);
return internal::convolution_fft(a, b);
}
template <class mint, internal::is_static_modint_t<mint>* = nullptr>
std::vector<mint> convolution(const std::vector<mint>& a,
const std::vector<mint>& b) {
int n = int(a.size()), m = int(b.size());
if (!n || !m) return {};
int z = (int)internal::bit_ceil((unsigned int)(n + m - 1));
assert((mint::mod() - 1) % z == 0);
if (std::min(n, m) <= 60) return convolution_naive(a, b);
return internal::convolution_fft(a, b);
}
template <unsigned int mod = 998244353,
class T,
std::enable_if_t<internal::is_integral<T>::value>* = nullptr>
std::vector<T> convolution(const std::vector<T>& a, const std::vector<T>& b) {
int n = int(a.size()), m = int(b.size());
if (!n || !m) return {};
using mint = static_modint<mod>;
int z = (int)internal::bit_ceil((unsigned int)(n + m - 1));
assert((mint::mod() - 1) % z == 0);
std::vector<mint> a2(n), b2(m);
for (int i = 0; i < n; i++) {
a2[i] = mint(a[i]);
}
for (int i = 0; i < m; i++) {
b2[i] = mint(b[i]);
}
auto c2 = convolution(std::move(a2), std::move(b2));
std::vector<T> c(n + m - 1);
for (int i = 0; i < n + m - 1; i++) {
c[i] = c2[i].val();
}
return c;
}
std::vector<long long> convolution_ll(const std::vector<long long>& a,
const std::vector<long long>& b) {
int n = int(a.size()), m = int(b.size());
if (!n || !m) return {};
static constexpr unsigned long long MOD1 = 754974721; // 2^24
static constexpr unsigned long long MOD2 = 167772161; // 2^25
static constexpr unsigned long long MOD3 = 469762049; // 2^26
static constexpr unsigned long long M2M3 = MOD2 * MOD3;
static constexpr unsigned long long M1M3 = MOD1 * MOD3;
static constexpr unsigned long long M1M2 = MOD1 * MOD2;
static constexpr unsigned long long M1M2M3 = MOD1 * MOD2 * MOD3;
static constexpr unsigned long long i1 =
internal::inv_gcd(MOD2 * MOD3, MOD1).second;
static constexpr unsigned long long i2 =
internal::inv_gcd(MOD1 * MOD3, MOD2).second;
static constexpr unsigned long long i3 =
internal::inv_gcd(MOD1 * MOD2, MOD3).second;
static constexpr int MAX_AB_BIT = 24;
static_assert(MOD1 % (1ull << MAX_AB_BIT) == 1, "MOD1 isn't enough to support an array length of 2^24.");
static_assert(MOD2 % (1ull << MAX_AB_BIT) == 1, "MOD2 isn't enough to support an array length of 2^24.");
static_assert(MOD3 % (1ull << MAX_AB_BIT) == 1, "MOD3 isn't enough to support an array length of 2^24.");
assert(n + m - 1 <= (1 << MAX_AB_BIT));
auto c1 = convolution<MOD1>(a, b);
auto c2 = convolution<MOD2>(a, b);
auto c3 = convolution<MOD3>(a, b);
std::vector<long long> c(n + m - 1);
for (int i = 0; i < n + m - 1; i++) {
unsigned long long x = 0;
x += (c1[i] * i1) % MOD1 * M2M3;
x += (c2[i] * i2) % MOD2 * M1M3;
x += (c3[i] * i3) % MOD3 * M1M2;
// B = 2^63, -B <= x, r(real value) < B
// (x, x - M, x - 2M, or x - 3M) = r (mod 2B)
// r = c1[i] (mod MOD1)
// focus on MOD1
// r = x, x - M', x - 2M', x - 3M' (M' = M % 2^64) (mod 2B)
// r = x,
// x - M' + (0 or 2B),
// x - 2M' + (0, 2B or 4B),
// x - 3M' + (0, 2B, 4B or 6B) (without mod!)
// (r - x) = 0, (0)
// - M' + (0 or 2B), (1)
// -2M' + (0 or 2B or 4B), (2)
// -3M' + (0 or 2B or 4B or 6B) (3) (mod MOD1)
// we checked that
// ((1) mod MOD1) mod 5 = 2
// ((2) mod MOD1) mod 5 = 3
// ((3) mod MOD1) mod 5 = 4
long long diff =
c1[i] - internal::safe_mod((long long)(x), (long long)(MOD1));
if (diff < 0) diff += MOD1;
static constexpr unsigned long long offset[5] = {
0, 0, M1M2M3, 2 * M1M2M3, 3 * M1M2M3 };
x -= offset[diff % 5];
c[i] = x;
}
return c;
}
} // namespace atcoder
void Init(int t) {
}
#define MOD 998244353
namespace sha256 {
using u8 = uint8_t;
using u32 = uint32_t;
using u64 = uint64_t;
static const u32 K[64] = {
0x428a2f98u, 0x71374491u, 0xb5c0fbcfu, 0xe9b5dba5u, 0x3956c25bu, 0x59f111f1u, 0x923f82a4u, 0xab1c5ed5u,
0xd807aa98u, 0x12835b01u, 0x243185beu, 0x550c7dc3u, 0x72be5d74u, 0x80deb1feu, 0x9bdc06a7u, 0xc19bf174u,
0xe49b69c1u, 0xefbe4786u, 0x0fc19dc6u, 0x240ca1ccu, 0x2de92c6fu, 0x4a7484aau, 0x5cb0a9dcu, 0x76f988dau,
0x983e5152u, 0xa831c66du, 0xb00327c8u, 0xbf597fc7u, 0xc6e00bf3u, 0xd5a79147u, 0x06ca6351u, 0x14292967u,
0x27b70a85u, 0x2e1b2138u, 0x4d2c6dfcu, 0x53380d13u, 0x650a7354u, 0x766a0abbu, 0x81c2c92eu, 0x92722c85u,
0xa2bfe8a1u, 0xa81a664bu, 0xc24b8b70u, 0xc76c51a3u, 0xd192e819u, 0xd6990624u, 0xf40e3585u, 0x106aa070u,
0x19a4c116u, 0x1e376c08u, 0x2748774cu, 0x34b0bcb5u, 0x391c0cb3u, 0x4ed8aa4au, 0x5b9cca4fu, 0x682e6ff3u,
0x748f82eeu, 0x78a5636fu, 0x84c87814u, 0x8cc70208u, 0x90befffau, 0xa4506cebu, 0xbef9a3f7u, 0xc67178f2u
};
inline u32 rotr(u32 x, int r) { return (x >> r) | (x << (32 - r)); }
struct Sha256 {
u32 h[8];
u64 total;
u8 buf[64];
size_t blen;
void init() {
static const u32 iv[8] = { 0x6a09e667u, 0xbb67ae85u, 0x3c6ef372u, 0xa54ff53au,
0x510e527fu, 0x9b05688cu, 0x1f83d9abu, 0x5be0cd19u };
for (int i = 0; i < 8; i++) h[i] = iv[i];
total = 0;
blen = 0;
}
void compress(const u8* p) {
u32 w[64];
for (int i = 0; i < 16; i++)
w[i] = (u32)p[4 * i] << 24 | (u32)p[4 * i + 1] << 16 | (u32)p[4 * i + 2] << 8 | (u32)p[4 * i + 3];
for (int i = 16; i < 64; i++) {
u32 s0 = rotr(w[i - 15], 7) ^ rotr(w[i - 15], 18) ^ (w[i - 15] >> 3);
u32 s1 = rotr(w[i - 2], 17) ^ rotr(w[i - 2], 19) ^ (w[i - 2] >> 10);
w[i] = w[i - 16] + s0 + w[i - 7] + s1;
}
u32 a = h[0], b = h[1], c = h[2], d = h[3], e = h[4], f = h[5], g = h[6], hh = h[7];
for (int i = 0; i < 64; i++) {
u32 t1 = hh + (rotr(e, 6) ^ rotr(e, 11) ^ rotr(e, 25)) + ((e & f) ^ (~e & g)) + K[i] + w[i];
u32 t2 = (rotr(a, 2) ^ rotr(a, 13) ^ rotr(a, 22)) + ((a & b) ^ (a & c) ^ (b & c));
hh = g; g = f; f = e; e = d + t1; d = c; c = b; b = a; a = t1 + t2;
}
h[0] += a; h[1] += b; h[2] += c; h[3] += d;
h[4] += e; h[5] += f; h[6] += g; h[7] += hh;
}
void update(const void* data, size_t n) {
const u8* p = (const u8*)data;
total += n;
while (n) {
size_t take = 64 - blen;
if (take > n) take = n;
memcpy(buf + blen, p, take);
blen += take; p += take; n -= take;
if (blen == 64) { compress(buf); blen = 0; }
}
}
void finish(u8 out[32]) {
u64 bits = total << 3;
u8 pad[72];
size_t np = 0;
pad[np++] = 0x80;
while ((blen + np) % 64 != 56) pad[np++] = 0;
for (int i = 0; i < 8; i++) pad[np++] = (u8)(bits >> (56 - 8 * i));
for (size_t i = 0; i < np; i++) {
buf[blen++] = pad[i];
if (blen == 64) { compress(buf); blen = 0; }
}
for (int i = 0; i < 8; i++) {
out[4 * i] = (u8)(h[i] >> 24);
out[4 * i + 1] = (u8)(h[i] >> 16);
out[4 * i + 2] = (u8)(h[i] >> 8);
out[4 * i + 3] = (u8)h[i];
}
}
};
inline void sha256(const void* data, size_t n, u8 out[32]) {
Sha256 c;
c.init();
c.update(data, n);
c.finish(out);
}
}
struct WeightStream {
uint8_t seed[32];
uint64_t pool[4];
uint64_t counter;
int left;
WeightStream(const uint8_t s[32]) {
memcpy(seed, s, 32);
counter = 0;
left = 0;
}
uint64_t next64() {
if (!left) {
uint8_t in[40], out[32];
memcpy(in, seed, 32);
for (int i = 0; i < 8; i++) in[32 + i] = (uint8_t)(counter >> (8 * i));
sha256::sha256(in, 40, out);
memcpy(pool, out, 32);
left = 4;
++counter;
}
return pool[--left];
}
// non-zero weight; the 64-bit modulo bias is about 1e-10
uint32_t nextWeight() {
uint64_t x;
do {
x = next64() % (uint64_t)MOD;
} while (x == 0);
return (uint32_t)x;
}
};
using mi = atcoder::modint998244353;
void Solve() {
int n;
string s;
cin >> n >> s;
vector<int>a(n);
cin >> a;
for (auto& u : a)u--;
int tmp = 1 << 20, res = 0;
vector<mi>g(n);
for (int i = 0; i < n; i++)g[i] = s[i] - 'a';
reverse(all(g));
auto h = sha256::Sha256();
h.init();
h.update(s.data(), n);
h.update(a.data(), n * sizeof(int));
h.update("LNight", 7);
h.update(&n, sizeof(int));
uint8_t sha[32];
h.finish(sha);
WeightStream ws(sha);
vector<vector<mi>>list(4, vector<mi>(n));
for (auto& u : list) {
for (auto& z : u)z = ws.nextWeight();
}
auto ck = [&](int x)->bool {
if (x > n)return 0;
vector<mi>d(n);
vector<pair<ull, ull>>z(n);
for (int k = 0; k < 4; k++) {
for (int i = 0; i < x; i++)d[a[i]] = list[k][i];
auto tmp = convolution(g, d);
vector<mi>r(n);
for (int i = 0; i < tmp.size(); i++) {
r[(n - 1 - i + n) % n] += tmp[i];
}
for (int i = 0; i < n; i++) {
if (k == 0)z[i].first = r[i].val();
else if (k == 1)z[i].first = (z[i].first << 32) | r[i].val();
else if (k == 2)z[i].second = r[i].val();
else if (k == 3)z[i].second = (z[i].second << 32) | r[i].val();
}
}
vector<int>pt(n);
for (int i = 0; i < n; i++)pt[i] = i;
sort(all(pt), [&](auto x, auto y) {return z[x] < z[y]; });
for (int l = 0; l < n;) {
int r = l + 1;
while (r < n && z[pt[r]] == z[pt[l]])r++;
for (int i = l; i < r; i++) {
for (int j = i + 1; j < r; j++) {
bool flag = 1;
for (int k = 0; k < x; k++) {
if (s[(a[k] + pt[i]) % n] != s[(a[k] + pt[j]) % n]) {
flag = 0;
break;
}
}
if (flag)return 1;
}
}
l = r;
}
return 0;
};
while (tmp)
{
if (ck(res + tmp))res += tmp;
tmp >>= 1;
}
cout << res << endl;
}
signed main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cout << fixed << setprecision(18);
int T = 1;
cin >> T;
int tit = clock();
Init(T);
while (T--) Solve();
cerr << clock() - tit << endl;
}
2287E1 - Marisa Kirisame and the Game (Easy Version)
My initial problem only had an $$$n \le 10^5$$$ version and an $$$n \le 500$$$ version; thanks to Error_Yuan for proposing this $$$n \le 10^4$$$ version.
If the two maxima differ, or if they are equal with different multiplicities, the position is already trivial: keep attacking the opponent's maximum, and the outcome is decided by whose maximum is larger and, on a tie, by who owns more copies of it.
A player has only two useful attack targets: the opponent's maximum value and the opponent's strict second maximum. Attacking anything smaller brings no extra profit.
Both players may play optimally without ever skipping a turn: skipping never turns a lost position into a non-lost one, so every move may be assumed to be a real attack.
//I must have missed the evolution memo.
//In case I never coding, good afternoon, good evening, and good night.
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING
#define _SILENCE_CXX20_CISO646_REMOVED_WARNING
#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable : 4700)
#include "bits/stdc++.h"
#include <array>
#if 0
#include "atcoder/all"
using namespace atcoder;
#endif
using namespace std;
template<typename T1, typename T2> istream& operator>>(istream& cin, pair<T1, T2>& a) { return cin >> a.first >> a.second; }
template<typename T1> istream& operator>>(istream& cin, vector<T1>& a) { for (auto& x : a) cin >> x; return cin; }
template<typename T1> istream& operator>>(istream& cin, valarray<T1>& a) { for (auto& x : a) cin >> x; return cin; }
template<typename T1, typename T2> ostream& operator<<(ostream& cout, const pair<T1, T2>& a) { return cout << a.first << ' ' << a.second; }
template<typename T1, typename T2> ostream& operator<<(ostream& cout, const vector<pair<T1, T2>>& a) { for (auto& x : a) cout << x << '\n'; return cout; }
template<typename T1> ostream& operator<<(ostream& cout, const vector<T1>& a) { int n = a.size(); if (!n) return cout; cout << a[0]; for (int i = 1; i < n; i++) cout << ' ' << a[i]; return cout; }
template<typename T1, typename T2> bool cmin(T1& x, const T2& y) { if (y < x) { x = y; return 1; } return 0; }
template<typename T1, typename T2> bool cmax(T1& x, const T2& y) { if (x < y) { x = y; return 1; } return 0; }
template<typename T1> vector<T1> range(T1 l, T1 r, T1 step = 1) { assert(step > 0); int n = (r - l + step - 1) / step, i; vector<T1> res(n); for (i = 0; i < n; i++) res[i] = l + step * i; return res; }
template<typename T1> basic_string<T1> operator*(const basic_string<T1>& s, int m) { auto r = s; m *= s.size(); r.resize(m); for (int i = s.size(); i < m; i++) r[i] = r[i - s.size()]; return r; }
#if !defined(ONLINE_JUDGE)&&defined(LOCAL)
#include "my_header\debug.h"
#else
#define dbg(...) ;
#define dbgn(...) ;
#endif
typedef unsigned int ui;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
#define all(x) (x).begin(),(x).end()
#define Endl endl
#define THREADCNT 8
#define MY_NAME "LNight"
#define NAN 0.1217728619
#define small_queue(name, ...) priority_queue<__VA_ARGS__, vector<__VA_ARGS__>, greater<__VA_ARGS__>>name
#define small_queue_type(...) priority_queue<__VA_ARGS__, vector<__VA_ARGS__>, greater<__VA_ARGS__>>
#define MOD 998244353
void Init(int t) {
}
pair<bool, bool> check(const vector<int>& a, const vector<int>& b) {
int n = a.size(), m = b.size();
int lim = max(n, m), inf = n + 1;
vector<int> f(lim + 1), g(lim + 1);
vector<int> nf(lim + 1), ng(lim + 1);
f[0] = g[0] = 1;
for (int r = 1; r <= lim; ++r) {
f[r] = g[r - 1];
g[r] = max(f[r] + 1, f[r - 1]);
}
int i = 0;
for (int l = 0; l < m; ) {
int r = l;
while (r < m && b[r] == b[l]) ++r;
while (i < n && a[i] < b[l]) ++i;
int p = i;
while (p < n && a[p] == b[l]) ++p;
int ca = p - i;
int cb = r - l;
vector<int> base_f(cb + 1), base_g(cb + 1);
for (int s = 1; s <= cb; ++s) {
int v;
if (s < ca) v = i + s + 1;
else if (p < n) v = p + 1;
else v = inf;
base_f[s] = base_g[s] = v;
if (s <= ca) {
if (i >= f[s]) base_f[s] = min(base_f[s], i + s);
if (i >= g[s]) base_g[s] = min(base_g[s], i + s);
}
}
for (int s = 1; s <= cb; ++s) {
nf[0] = base_f[s];
ng[0] = base_g[s];
for (int k = 1; k <= lim; ++k) {
nf[k] = min(g[k], ng[k - 1]);
ng[k] = max(nf[k] + 1, nf[k - 1]);
}
f.swap(nf);
g.swap(ng);
}
l = r;
}
return { n >= f[0], n >= g[0] };
}
int solve(vector<int> a, vector<int> b) {
pair<int, int> alice = check(a, b);
if (alice.first) return 1;
pair<int, int> bob = check(b, a);
if (bob.second) return -1;
return 0;
}
void Solve() {
int n, m;
cin >> n >> m;
vector<int>a(n), b(m);
cin >> a >> b;
sort(all(a));
sort(all(b));
int res = solve(a, b);
if (res == 1)cout << "A" << endl;
else if (res == -1)cout << "B" << endl;
else cout << "C" << endl;
}
signed main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cout << fixed << setprecision(18);
int T = 1;
cin >> T;
int tit = clock();
Init(T);
while (T--) Solve();
cerr << clock() - tit << endl;
}
The idea comes from the power level settings of some fantasy works. In many fantasy works every character has a power level, and the levels differ wildly (for example, Tier 10 is an ordinary human, while Tier 9 is a superhuman). In this setting I created this problem, so that you can see how a battle between two groups should happen in such a fantasy world, and what the best arrangement is if a group wants to defeat another group.
2287E2 - Marisa Kirisame and the Game (Hard Version)
Codex did not pass this problem during testing, which surprised me a lot.
Before reading, please go through the hints of 2287E1 - Marisa Kirisame and the Game (Easy Version), but no need read its tutorial, because what follows is completely different.
Sort the input. You can see that at any moment both players hold a prefix plus $$$k$$$ copies of the maximum value. This is already an $$$O(n^3)$$$-level DP.
We focus on the case $$$k = 0$$$: at this moment both players hold only a prefix, and we enter a subproblem.
Recall Hint 1 of the easy version: only $$$O(n)$$$ subproblems are not trivial.
Every state with $$$k \gt 0$$$ can be derived from the states with $$$k = 0$$$, and we only need to find the derivation rule.
//I must have missed the evolution memo.
//In case I never coding, good afternoon, good evening, and good night.
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING
#define _SILENCE_CXX20_CISO646_REMOVED_WARNING
#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable : 4700)
#include "bits/stdc++.h"
#if 0
#include "atcoder/all"
using namespace atcoder;
#endif
using namespace std;
template<typename T1, typename T2> istream& operator>>(istream& cin, pair<T1, T2>& a) { return cin >> a.first >> a.second; }
template<typename T1> istream& operator>>(istream& cin, vector<T1>& a) { for (auto& x : a) cin >> x; return cin; }
template<typename T1> istream& operator>>(istream& cin, valarray<T1>& a) { for (auto& x : a) cin >> x; return cin; }
template<typename T1, typename T2> ostream& operator<<(ostream& cout, const pair<T1, T2>& a) { return cout << a.first << ' ' << a.second; }
template<typename T1, typename T2> ostream& operator<<(ostream& cout, const vector<pair<T1, T2>>& a) { for (auto& x : a) cout << x << '\n'; return cout; }
template<typename T1> ostream& operator<<(ostream& cout, const vector<T1>& a) { int n = a.size(); if (!n) return cout; cout << a[0]; for (int i = 1; i < n; i++) cout << ' ' << a[i]; return cout; }
template<typename T1, typename T2> bool cmin(T1& x, const T2& y) { if (y < x) { x = y; return 1; } return 0; }
template<typename T1, typename T2> bool cmax(T1& x, const T2& y) { if (x < y) { x = y; return 1; } return 0; }
template<typename T1> vector<T1> range(T1 l, T1 r, T1 step = 1) { assert(step > 0); int n = (r - l + step - 1) / step, i; vector<T1> res(n); for (i = 0; i < n; i++) res[i] = l + step * i; return res; }
template<typename T1> basic_string<T1> operator*(const basic_string<T1>& s, int m) { auto r = s; m *= s.size(); r.resize(m); for (int i = s.size(); i < m; i++) r[i] = r[i - s.size()]; return r; }
#if !defined(ONLINE_JUDGE)&&defined(LOCAL)
#include "my_header\debug.h"
#else
#define dbg(...) ;
#define dbgn(...) ;
#endif
typedef unsigned int ui;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
#define all(x) (x).begin(),(x).end()
#define Endl endl
#define THREADCNT 8
#define MY_NAME "LNight"
#define NAN 0.1217728619
#define small_queue(name, ...) priority_queue<__VA_ARGS__, vector<__VA_ARGS__>, greater<__VA_ARGS__>>name
#define small_queue_type(...) priority_queue<__VA_ARGS__, vector<__VA_ARGS__>, greater<__VA_ARGS__>>
void Init(int t) {
}
struct fwt {
int n;
vector<int>d;
fwt(int _n) {
n = _n;
d.resize(n + 1, -1);
}
void set(int x, int v) {
while (x <= n) {
d[x] = max(d[x], v);
x += x & -x;
}
}
int get(int x) {
int res = -1;
while (x) {
res = max(res, d[x]);
x -= x & -x;
}
return res;
}
};
int sv(vector<int>a, vector<int>b) {
int n = a.size();
int m = b.size();
vector<vector<int>>dpa(2, vector<int>(m + 1));//面对有i个的鲍勃,爱丽丝先手需要dpa[0][i]个才能赢,爱丽丝后手需要dpa[1][i]个才能赢
vector<vector<int>>dpb(2, vector<int>(n + 1));//面对有i个的爱丽丝,鲍勃先手需要dpb[1][i]个才能赢,鲍勃后手需要dpb[0][i]个才能赢
fwt sta(n + m + 10);//鲍勃行动时1的查询,pa-pb+m+1
fwt stb(n + m + 10);//爱丽丝行动时-1的查询,pb-pa+n+1
vector<vector<int>>draw(2, vector<int>(n + m + 10, -1));//平局状态,[[pb-pa+m+1]=pa,[pa-pb+m+1]=pb]
draw[0][n + 1] = 0;
draw[1][m + 1] = 0;
sta.set(m + 2, 0);
stb.set(n + 2, 0);
int pa = 1, pb = 1;
int z = 1;
while (pa <= n && pb <= m) {
if (a[pa - 1] != b[pb - 1]) {
if (a[pa - 1] > b[pb - 1]) {
dpa[0][pb] = dpa[1][pb] = pa;//役满确定
sta.set(dpa[1][pb] - pb + m + 1, pb);
pb++;
continue;
}
else {
dpb[0][pa] = dpb[1][pa] = pb;//役满确定
stb.set(dpb[0][pa] - pa + n + 1, pa);
pa++;
continue;
}
}
if (pa > 1 && a[pa - 2] == a[pa - 1])z++;
else z = 1;
int x = pa - z;
int y = pb - z;
//役满机会
dpa[0][pb] = dpa[1][pb] = pa + 1;
dpb[0][pa] = dpb[1][pa] = pb + 1;
{//Alice first
int aw, ad, bw, bd;//分别代表F上的1,F上的0,G上的-1,G上的0
int tmp = 0;
aw = y - sta.get(x - z + 1 - y + m + 1);
bw = x - stb.get(y - z - x + n + 1);
ad = y - draw[1][x - z + 1 - y + m + 1];
bd = x - draw[0][y - z - x + n + 1];
if (aw != y + 1 && (bw == x + 1 || aw <= bw)) {//aw <= bw + z + 1 会错误的让爱丽丝赢,aw<=bw - 1 - z会错误的让alice不赢
if (bd == x + 1 || bd >= aw)tmp = 1;//bd + z + 3>=aw 会错误的让爱丽丝赢,aw<=bd - z - 1会错误的让alice不赢
}
else if (bw != x + 1 && (aw == y + 1 || aw > bw)) {//aw + z + 1 > bw会错误的让鲍勃赢,aw - z - 1 > bw 会错误的让鲍勃不赢。
if (ad == y + 1 || ad > bw)tmp = -1;//ad + z + 3 > bw会错误的让鲍勃赢,ad - z - 1 > bw 会错误的让鲍勃不赢。
}
if (tmp == 1) {
dpa[0][pb] = pa;
}
else if (tmp == -1) {
dpb[0][pa] = pb;
}
else {
draw[0][pb - pa + n + 1] = pa;
}
}
{//Bob first
int aw, ad, bw, bd;
int tmp = 0;
aw = y - sta.get(x - z - y + m + 1);
bw = x - stb.get(y + 1 - z - x + n + 1);
ad = y - draw[1][x - z - y + m + 1];
bd = x - draw[0][y + 1 - z - x + n + 1];
if (aw != y + 1 && (bw == x + 1 || aw < bw)) {//aw < bw + z + 1 会错误的让爱丽丝赢,aw<bw - 1 - z会错误的让alice不赢
if (bd == x + 1 || bd > aw)tmp = 1;//bd + z + 3>aw 会错误的让爱丽丝赢,aw<bd - z - 1会错误的让alice不赢
}
else if (bw != x + 1 && (aw == y + 1 || aw >= bw)) {//aw + z + 1 >= bw会错误的让鲍勃赢,aw - z - 1 >= bw 会错误的让鲍勃不赢。
if (ad == y + 1 || ad >= bw)tmp = -1;//ad + z + 3 >= bw会错误的让鲍勃赢,ad - z - 1 >= bw 会错误的让鲍勃不赢。
}
if (tmp == 1) {
dpa[1][pb] = pa;
}
else if (tmp == -1) {
dpb[1][pa] = pb;
}
else {
draw[1][pa - pb + m + 1] = pb;
}
}
sta.set(dpa[1][pb] - pb + m + 1, pb);
stb.set(dpb[0][pa] - pa + n + 1, pa);
pa++;
pb++;
}
int res = 0;
if (pa > n) {
if (dpb[0][n] <= m)res = -1;
else if (draw[0][m + 1] == n)res = 0;
else res = 1;
}
else {
if (dpa[0][m] <= n)res = 1;
else if (draw[0][m + 1] == n)res = 0;
else res = -1;
}
return res;
}
void Solve() {
int n, m;
cin >> n >> m;
vector<int>a(n), b(m);
cin >> a >> b;
sort(all(a));
sort(all(b));
int res = sv(a, b);
if (res == 1)cout << "A" << endl;
else if (res == -1)cout << "B" << endl;
else cout << "C" << endl;
}
signed main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cout << fixed << setprecision(18);
int T = 1;
cin >> T;
int tit = clock();
Init(T);
while (T--) Solve();
cerr << clock() - tit << endl;
}
This problem was originally conceived as a two-attribute version (attack power and defense power), but I only know an $$$O(2^n)$$$ solution for it.








Auto comment: topic has been updated by LNight121 (previous revision, new revision, compare).
great A
I wonder why Um_nik didn't fucking slime you out for such terrible problemsetting
I wonder why your mother didn't fucking slime you out for such terrible words
I wonder why MikeMirzayanov doesn't slime you out for cheating...
lmao he got dq'ed in calico fall 26 and is still very bold
WHY DP IN PROBLEM B
you can do greedy brute force aswell
Why $$$n \leq 10^5$$$ on multiple problems if the intended time complexity is $$$O(n)$$$ or $$$O(n \log n)$$$?
Isnt B1 just greedy? DP is a lil bit overkill
What kind of greedy solution do you have?
Im not very good at explaining stuff so im not sure if i can help you understand my approach
I simply iterate through the string S
At the current character Si
-if Si = '+', then i'd want to duplicate a stone with power 2, if there is no stone with power 2 then i will just increase a random power 1 stone by 1, making it a power 2 stone
-if Si = '-', then ill check if there exist more than one power 2 stones (because id still have atleast one power 2 stone left), and decrease that stone's power by 1, because deleting a power 1 stone makes the answer lower, if there is one (or none) power 2 stone then ill delete a power 1 stone instead, because i need a power 2 stone to duplicate more stones, and if there is no power 1 stone, then ill simply decrease the only power 2 stone left by one
If at any step there is no stones left, ill stop
Every step ill update the answer = max(answer, current stones)
We will apply all of the operations as we traverse through $$$s$$$. When we encounter a $$$+$$$, it is obviously better to use it on a $$$2$$$ rather than on a $$$1$$$ whenever possible. One useful observation is that we only really need one $$$2$$$ so that we extract the most benefit from $$$+$$$. Then the casework on '-' follows:
dang that's a weird greedy, I gave up on greedy after trying the first ones that comes to mind lol
Of course, Greedy is possible, but initially I thought it might be too difficult, so I lowered the data range.
Is it just me or this contest is kind of weird
The time complexity of div1C's 5e4 square is absolutely absurd. I tried for an hour and a half to remove the O(logm), hoping to find special properties through mod2, but it completely failed. Why isn't this problem given a reasonable data range, such as 1e4/1s or 2e4/4s.
Maybe you can test it on your own PC first? In my PC, 1e5/3s is completely fine. The solution to this problem runs unbelievably fast. Of course. I admit that 5e4/3s is too confusing.
It doesn't seem like the correct time complexity, 5e4 seems to indicate that you need to find a way to remove this log in order to pass.
What were the problemsetters thinking?
You are not allowed to view the requested page. https://codeforces.me/contest/2288/submission/399348749
PS Why was my rating recalculated? Previously, if the first test case was not passed and no other attempts at a solution were made a participant’s status was set to "non-competitive."
really? We will fix this issue as soon as possible (maybe an hour, maybe ten minutes).
UPD: fixed (maybe)
still no access (definitely)
fixing
fixed
Wth is wrong with this B2 it's not wrth being B
My solution for Div.1 E1 should be able to solve E2 in $$$O(n+m)$$$ time beyond sort without using data structures(only need two-pointers, which should be better than std in complexity beyond sort), but the sample for E1 was too weak that it took me about $$$20$$$ minutes for debugging, which means there wasn't enough time for me to solve E2 :(
Well, to me it seems like you have some weird code (writing multiple lines into one). Not saying you cheated, just saying you had some weird code.
I think AI won't write code like this though.
Anyways, I write codes how I find to be easy to read and write for me, since I think too loose would make the code hard both for read and write.
Auto comment: topic has been updated by LNight121 (previous revision, new revision, compare).
Am I the only who thought we need to minimise the sum of all passengers time in D2D metro problem? Also is there any solution for my version of the problem in 2s time limit?
Div2 A has $$$O(1)$$$ solution.
Let's say you do $$$a$$$ charges first then $$$b$$$ attacks. The total damage is:
The damage needs to be equal to or greater than $$$x$$$, so we have:
This means that, if you decide to make $$$b$$$ attacks, the minimum number of charges required is $$$\displaystyle a = \left\lceil \frac{x}{b} + \frac{b-1}{2} \right\rceil$$$.
Then, the total number of moves is:
If you differentiate the function within the ceil bracket, you'll see that the function becomes minimum when $$$\displaystyle b = \sqrt{\frac{2x}{3}}$$$. Therefore you pick several integer values around $$$\displaystyle \sqrt{\frac{2x}{3}}$$$ as $$$b$$$ and the minimum value of $$$\displaystyle \left\lceil \frac{x}{b} + \frac{b-1}{2} - 1 + b\right\rceil$$$ among those $$$b$$$'s will be the answer.
Does the editorial imply there is a solution without reducing to XORs for D1C? (sorry it doesn't let me see their official solution. I thought using sums was way too slow since without optimizations, my XOR solution passes in 1.1s which is a bit much. (with pragmas it's 3x faster, but that is not the point here.)
The correct solution used is XOR, because in mod 2, summation is essentially no different from XOR, so I used the summation symbol in the solution to the problem
Got it. As i said i wasn't able to read the code, thanks for clarifying!
I wasn't even able to solve A
i am unable to see the code
fixed
Auto comment: topic has been updated by LNight121 (previous revision, new revision, compare).