結果
問題 | No.1702 count good string |
ユーザー |
![]() |
提出日時 | 2021-10-08 22:13:04 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 8 ms / 2,000 ms |
コード長 | 4,946 bytes |
コンパイル時間 | 2,788 ms |
コンパイル使用メモリ | 248,872 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-23 04:38:21 |
合計ジャッジ時間 | 4,150 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 47 |
ソースコード
#include <bits/stdc++.h>using i32 = std::int32_t;using u32 = std::uint32_t;using i64 = std::int64_t;using u64 = std::uint64_t;using isize = std::ptrdiff_t;using usize = std::size_t;class rep {struct Iter {usize itr;constexpr Iter(const usize pos) noexcept : itr(pos) {}constexpr void operator++() noexcept { ++itr; }constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; }constexpr usize operator*() const noexcept { return itr; }};const Iter first, last;public:explicit constexpr rep(const usize first, const usize last) noexcept : first(first), last(std::max(first, last)) {}constexpr Iter begin() const noexcept { return first; }constexpr Iter end() const noexcept { return last; }};template <class T> constexpr T totient(T x) {T ret = x;for (T i = 2; i * i <= x; ++i) {if (x % i == 0) {ret /= i;ret *= i - 1;while (x % i == 0) x /= i;}}if (x > 1) {ret /= x;ret *= x - 1;}return ret;}template <class T> constexpr T rem_euclid(T value, const T& mod) { return (value %= mod) >= 0 ? value : value + mod; }template <u32 MOD, std::enable_if_t<((u32)1 <= MOD and MOD <= ((u32)1 << 31))>* = nullptr> class StaticModint {using Mint = StaticModint;static inline constexpr u32 PHI = totient(MOD);u32 v;public:static constexpr u32 mod() noexcept { return MOD; }template <class T, std::enable_if_t<std::is_signed_v<T> and std::is_integral_v<T>>* = nullptr>static constexpr T normalize(const T x) noexcept {return rem_euclid<std::common_type_t<T, i64>>(x, MOD);}template <class T, std::enable_if_t<std::is_unsigned_v<T> and std::is_integral_v<T>>* = nullptr>static constexpr T normalize(const T x) noexcept {return x % MOD;}constexpr StaticModint() noexcept : v(0) {}template <class T> constexpr StaticModint(const T x) noexcept : v(normalize(x)) {}template <class T> static constexpr Mint raw(const T x) noexcept {Mint ret;ret.v = x;return ret;}constexpr u32 get() const noexcept { return v; }constexpr Mint neg() const noexcept { return raw(v == 0 ? 0 : MOD - v); }constexpr Mint inv() const noexcept { return pow(PHI - 1); }constexpr Mint pow(u64 exp) const noexcept {Mint ret(1), mult(*this);for (; exp > 0; exp >>= 1) {if (exp & 1) ret *= mult;mult *= mult;}return ret;}constexpr Mint operator-() const noexcept { return neg(); }constexpr Mint operator~() const noexcept { return inv(); }constexpr Mint operator+(const Mint& rhs) const noexcept { return Mint(*this) += rhs; }constexpr Mint& operator+=(const Mint& rhs) noexcept {if ((v += rhs.v) >= MOD) v -= MOD;return *this;}constexpr Mint operator-(const Mint& rhs) const noexcept { return Mint(*this) -= rhs; }constexpr Mint& operator-=(const Mint& rhs) noexcept {if (v < rhs.v) v += MOD;v -= rhs.v;return *this;}constexpr Mint operator*(const Mint& rhs) const noexcept { return Mint(*this) *= rhs; }constexpr Mint& operator*=(const Mint& rhs) noexcept {v = (u64)v * rhs.v % MOD;return *this;}constexpr Mint operator/(const Mint& rhs) const noexcept { return Mint(*this) /= rhs; }constexpr Mint& operator/=(const Mint& rhs) noexcept { return *this *= rhs.inv(); }constexpr bool operator==(const Mint& rhs) const noexcept { return v == rhs.v; }constexpr bool operator!=(const Mint& rhs) const noexcept { return v != rhs.v; }friend std::ostream& operator<<(std::ostream& stream, const Mint& rhs) { return stream << rhs.v; }};using Modint1000000007 = StaticModint<1000000007>;using Modint998244353 = StaticModint<998244353>;template <class T> using Vec = std::vector<T>;using Fp = Modint1000000007;void main_() {usize N;std::cin >> N;Vec<char> S(N);for (auto& x : S) {std::cin >> x;}const std::string T = "yukicoder";std::array<Fp, 19> dp{};dp[0] = 1;for (const auto x : S) {std::array<Fp, 19> next{};for (const auto i : rep(0, 19)) {next[i] += dp[i];}for (const auto i : rep(0, 9)) {if (T[i] == x) {next[i + 1] += dp[i];if (i != 0) {next[i + 10] += dp[i + 9];}}}if (x == '?') {for (const auto i : rep(0, 9)) {next[i + 10] += dp[i];}}dp = std::move(next);}std::cout << dp[9] + dp[18] << '\n';}int main() {std::ios_base::sync_with_stdio(false);std::cin.tie(nullptr);main_();return 0;}