結果
| 問題 |
No.1195 数え上げを愛したい（文字列編）
|
| コンテスト | |
| ユーザー |
 KoD
|
| 提出日時 | 2020-08-22 15:32:41 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2,832 ms / 3,000 ms |
| コード長 | 11,593 bytes |
| コンパイル時間 | 1,816 ms |
| コンパイル使用メモリ | 84,400 KB |
| 最終ジャッジ日時 | 2025-01-13 09:40:39 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 26 |
ソースコード
#line 1 "main.cpp"
/**
* @title Template
*/
#include <iostream>
#include <algorithm>
#include <utility>
#include <numeric>
#include <vector>
#include <array>
#include <cassert>
#line 2 "/Users/kodamankod/Desktop/Programming/Library/other/chmin_chmax.cpp"
template <class T, class U>
constexpr bool chmin(T &lhs, const U &rhs) {
if (lhs > rhs) { lhs = rhs; return true; }
return false;
}
template <class T, class U>
constexpr bool chmax(T &lhs, const U &rhs) {
if (lhs < rhs) { lhs = rhs; return true; }
return false;
}
/**
* @title Chmin/Chmax
*/
#line 2 "/Users/kodamankod/Desktop/Programming/Library/other/range.cpp"
#line 4 "/Users/kodamankod/Desktop/Programming/Library/other/range.cpp"
class range {
public:
class iterator {
private:
int64_t M_position;
public:
constexpr iterator(int64_t position) noexcept: M_position(position) { }
constexpr void operator ++ () noexcept { ++M_position; }
constexpr bool operator != (iterator other) const noexcept { return M_position != other.M_position; }
constexpr int64_t operator * () const noexcept { return M_position; }
};
class reverse_iterator {
private:
int64_t M_position;
public:
constexpr reverse_iterator(int64_t position) noexcept: M_position(position) { }
constexpr void operator ++ () noexcept { --M_position; }
constexpr bool operator != (reverse_iterator other) const noexcept { return M_position != other.M_position; }
constexpr int64_t operator * () const noexcept { return M_position; }
};
private:
const iterator M_first, M_last;
public:
constexpr range(int64_t first, int64_t last) noexcept: M_first(first), M_last(std::max(first, last)) { }
constexpr iterator begin() const noexcept { return M_first; }
constexpr iterator end() const noexcept { return M_last; }
constexpr reverse_iterator rbegin() const noexcept { return reverse_iterator(*M_last - 1); }
constexpr reverse_iterator rend() const noexcept { return reverse_iterator(*M_first - 1); }
};
/**
* @title Range
*/
#line 2 "/Users/kodamankod/Desktop/Programming/Library/other/rev.cpp"
#include <type_traits>
#include <iterator>
#line 6 "/Users/kodamankod/Desktop/Programming/Library/other/rev.cpp"
template <class T>
class rev_impl {
public:
using iterator = decltype(std::rbegin(std::declval<T>()));
private:
const iterator M_begin;
const iterator M_end;
public:
constexpr rev_impl(T &&cont) noexcept: M_begin(std::rbegin(cont)), M_end(std::rend(cont)) { }
constexpr iterator begin() const noexcept { return M_begin; }
constexpr iterator end() const noexcept { return M_end; }
};
template <class T>
constexpr decltype(auto) rev(T &&cont) {
return rev_impl<T>(std::forward<T>(cont));
}
/**
* @title Reverser
*/
#line 2 "/Users/kodamankod/Desktop/Programming/Library/algebraic/modular.cpp"
#include <cstdint>
#line 5 "/Users/kodamankod/Desktop/Programming/Library/algebraic/modular.cpp"
template <class Modulus>
class modular {
public:
using value_type = uint32_t;
using cover_type = uint64_t;
static constexpr value_type mod() { return Modulus::value(); }
template <class T>
static constexpr value_type normalize(T value_) noexcept {
if (value_ < 0) {
value_ = -value_;
value_ %= mod();
if (value_ == 0) return 0;
return mod() - value_;
}
return value_ % mod();
}
private:
value_type value;
public:
constexpr modular() noexcept : value(0) { }
template <class T>
explicit constexpr modular(T value_) noexcept : value(normalize(value_)) { }
template <class T>
explicit constexpr operator T() const noexcept { return static_cast<T>(value); }
constexpr value_type get() const noexcept { return value; }
constexpr value_type &extract() noexcept { return value; }
constexpr modular operator - () const noexcept { return modular(mod() - value); }
constexpr modular operator ~ () const noexcept { return inverse(*this); }
constexpr modular operator + (const modular &rhs) const noexcept { return modular(*this) += rhs; }
constexpr modular& operator += (const modular &rhs) noexcept {
if ((value += rhs.value) >= mod()) value -= mod();
return *this;
}
constexpr modular operator - (const modular &rhs) const noexcept { return modular(*this) -= rhs; }
constexpr modular& operator -= (const modular &rhs) noexcept {
if ((value += mod() - rhs.value) >= mod()) value -= mod();
return *this;
}
constexpr modular operator * (const modular &rhs) const noexcept { return modular(*this) *= rhs; }
constexpr modular& operator *= (const modular &rhs) noexcept {
value = (cover_type) value * rhs.value % mod();
return *this;
}
constexpr modular operator / (const modular &rhs) const noexcept { return modular(*this) /= rhs; }
constexpr modular& operator /= (const modular &rhs) noexcept { return (*this) *= rhs.inverse(); }
constexpr bool zero() const noexcept { return value == 0; }
constexpr bool operator == (const modular &rhs) const noexcept { return value == rhs.value; }
constexpr bool operator != (const modular &rhs) const noexcept { return value != rhs.value; }
friend std::ostream& operator << (std::ostream &stream, const modular &rhs) { return stream << rhs.value; }
friend constexpr modular inverse(modular val) noexcept { return power(val, mod() - 2); }
friend constexpr modular power(modular val, cover_type exp) noexcept {
modular res(1);
for (; exp > 0; exp >>= 1, val *= val) if (exp & 1) res *= val;
return res;
}
};
template <uint32_t Val>
struct modulus_impl { static constexpr uint32_t value() noexcept { return Val; } };
template <uint32_t Val>
using mint32_t = modular<modulus_impl<Val>>;
struct runtime_mod { static uint32_t &value() noexcept { static uint32_t val = 0; return val; } };
using rmint32_t = modular<runtime_mod>;
/**
* @title Modint
*/
#line 2 "/Users/kodamankod/Desktop/Programming/Library/algebraic/ntt.cpp"
#line 2 "/Users/kodamankod/Desktop/Programming/Library/other/bit_operation.cpp"
#include <cstddef>
#line 5 "/Users/kodamankod/Desktop/Programming/Library/other/bit_operation.cpp"
constexpr size_t bit_ppc(const uint64_t x) { return __builtin_popcountll(x); }
constexpr size_t bit_ctzr(const uint64_t x) { return x == 0 ? 64 : __builtin_ctzll(x); }
constexpr size_t bit_ctzl(const uint64_t x) { return x == 0 ? 64 : __builtin_clzll(x); }
constexpr size_t bit_width(const uint64_t x) { return 64 - bit_ctzl(x); }
constexpr uint64_t bit_msb(const uint64_t x) { return x == 0 ? 0 : uint64_t(1) << (bit_width(x) - 1); }
constexpr uint64_t bit_lsb(const uint64_t x) { return x & (-x); }
constexpr uint64_t bit_cover(const uint64_t x) { return x == 0 ? 0 : bit_msb(2 * x - 1); }
constexpr uint64_t bit_rev(uint64_t x) {
x = ((x >> 1) & 0x5555555555555555) | ((x & 0x5555555555555555) << 1);
x = ((x >> 2) & 0x3333333333333333) | ((x & 0x3333333333333333) << 2);
x = ((x >> 4) & 0x0F0F0F0F0F0F0F0F) | ((x & 0x0F0F0F0F0F0F0F0F) << 4);
x = ((x >> 8) & 0x00FF00FF00FF00FF) | ((x & 0x00FF00FF00FF00FF) << 8);
x = ((x >> 16) & 0x0000FFFF0000FFFF) | ((x & 0x0000FFFF0000FFFF) << 16);
x = (x >> 32) | (x << 32);
return x;
}
/**
* @title Bit Operations
*/
#line 4 "/Users/kodamankod/Desktop/Programming/Library/algebraic/ntt.cpp"
#line 10 "/Users/kodamankod/Desktop/Programming/Library/algebraic/ntt.cpp"
namespace ntt_detail {
constexpr uint32_t primitive_root(const uint32_t mod) {
std::array<uint32_t, 32> exp{};
uint32_t cur = mod - 1;
size_t size = 0;
for (uint32_t i = 2; i * i <= cur; ++i) {
if (cur % i == 0) {
exp[size++] = (mod - 1) / i;
while (cur % i == 0) cur /= i;
}
}
if (cur != 1) exp[size++] = (mod - 1) / cur;
for (uint32_t check = 1; check < mod; ++check) {
for (auto e: exp) {
if (e == 0) return check;
uint64_t a = check, x = 1;
while (e > 0) {
if (e & 1) (x *= a) %= mod;
(a *= a) %= mod;
e >>= 1;
}
if (x == 1) break;
}
}
return mod;
};
template <size_t N, class T>
constexpr std::array<T, N> compute_roots(T omega) {
std::array<T, N> res;
res[N - 1] = omega;
for (size_t i = N - 1; i > 0; --i) {
res[i - 1] = res[i] * res[i];
}
return res;
}
}
template <class Modular>
class number_theoretic_transform {
public:
using value_type = Modular;
static constexpr uint32_t mod = Modular::mod();
static constexpr uint32_t prim = ntt_detail::primitive_root(mod);
private:
static constexpr size_t level = bit_ctzr(mod - 1);
static constexpr value_type omega = power(value_type(prim), ((mod - 1) >> level));
static constexpr auto roots = ntt_detail::compute_roots<level>(omega);
static constexpr auto inv_roots = ntt_detail::compute_roots<level>(inverse(omega));
public:
static void transform(std::vector<value_type> &F) {
const size_t size = F.size();
const size_t logn = bit_ctzr(size);
for (size_t i = 0; i < size; ++i) {
const size_t j = bit_rev(i) >> (64 - logn);
if (i < j) std::swap(F[i], F[j]);
}
value_type coeff(1);
for (size_t s = 0; s < logn; ++s) {
const size_t mh = 1 << s;
const size_t m = mh << 1;
for (size_t i = 0; i < size; i += m) {
coeff = value_type(1);
for (size_t j = i; j < i + mh; ++j) {
const auto a = F[j];
const auto b = F[j + mh] * coeff;
F[j] = a + b;
F[j + mh] = a - b;
coeff *= roots[s];
}
}
}
}
static void inv_transform(std::vector<value_type> &F) {
const size_t size = F.size();
const size_t logn = bit_ctzr(size);
for (size_t i = 0; i < size; ++i) {
const size_t j = bit_rev(i) >> (64 - logn);
if (i < j) std::swap(F[i], F[j]);
}
value_type coeff(1);
for (size_t s = 0; s < logn; ++s) {
const size_t mh = 1 << s;
const size_t m = mh << 1;
for (size_t i = 0; i < size; i += m) {
coeff = value_type(1);
for (size_t j = i; j < i + mh; ++j) {
const auto a = F[j];
const auto b = F[j + mh] * coeff;
F[j] = a + b;
F[j + mh] = a - b;
coeff *= inv_roots[s];
}
}
}
coeff = inverse(value_type(size));
for (auto &x: F) x *= coeff;
}
};
/**
* @title Number Theoretic Transform
*/
#line 19 "main.cpp"
using i32 = int32_t;
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;
constexpr i32 inf32 = (i32(1) << 30) - 1;
constexpr i64 inf64 = (i64(1) << 62) - 1;
using m32 = mint32_t<998244353>;
using ntt = number_theoretic_transform<m32>;
std::vector<m32> convolve(std::vector<m32> A, std::vector<m32> B) {
if (A.empty() || B.empty()) return { };
const size_t res_size = A.size() + B.size() - 1;
const size_t fix_size = 1 << (31 - __builtin_clz(2 * res_size - 1));
A.resize(fix_size);
B.resize(fix_size);
ntt::transform(A);
ntt::transform(B);
for (size_t i = 0; i < fix_size; ++i) {
A[i] *= B[i];
}
ntt::inv_transform(A);
A.resize(res_size);
return A;
}
int main() {
std::string S;
std::cin >> S;
std::array<std::vector<m32>, 26> arr;
for (auto &v: arr) {
v = { m32(1) };
}
for (auto c: S) {
auto &v = arr[c - 'a'];
v.push_back(v.back() * inverse(m32(v.size())));
}
auto &v = arr[0];
for (auto i: range(1, 26)) {
v = convolve(std::move(v), arr[i]);
}
m32 cur(1), ans;
for (auto i: range(0, v.size())) {
ans += cur * v[i];
cur *= m32(i + 1);
}
std::cout << ans - m32(1) << '\n';
return 0;
}