結果

問題 No.3242 Count 8 Included Numbers (Hard)
ユーザー elphe
提出日時 2025-08-22 22:39:02
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 51 ms / 2,000 ms
コード長 13,684 bytes
コンパイル時間 3,100 ms
コンパイル使用メモリ 279,336 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-08-22 22:39:08
合計ジャッジ時間 4,895 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

namespace MyLib
{
	template<uint_fast32_t MOD> class mod_int
	{
	private:
		uint_fast32_t value = 0;
		[[nodiscard]] static inline constexpr bool is_prime(const uint_fast32_t arg) noexcept
		{
			for (uint_fast32_t i = 2; i * i <= arg; ++i)
				if (arg % i == 0) [[unlikely]] return false;
			return true;
		}
		[[nodiscard]] static inline constexpr uint_fast32_t pow_mod(uint_fast32_t a, size_t b) noexcept
		{
			if constexpr (MOD == 1) return 0;
			uint_fast32_t ans = 1;
			a %= MOD;
			for (; b != 0; b >>= 1, a = static_cast<uint_fast64_t>(a) * a % MOD)
				if (b & 1) ans = ans * static_cast<uint_fast64_t>(a) % MOD;

			return ans;
		}

	public:
		constexpr mod_int() noexcept { static_assert(MOD != 0, "0 cannot be set as \'MOD.\'"); }
		template<typename T> constexpr mod_int(const T arg) noexcept { static_assert(MOD != 0, "0 cannot be set as \'MOD.\'"); value = (uint_fast32_t)(arg % MOD); }

		[[nodiscard]] constexpr mod_int<MOD> operator+() const noexcept { return mod_int<MOD>(value); }
		[[nodiscard]] constexpr mod_int<MOD> operator-() const noexcept { [[assume(value < MOD)]]; return mod_int<MOD>(value == 0 ? 0 : MOD - value); }

		[[nodiscard]] friend constexpr mod_int<MOD> operator+(const mod_int<MOD> mi1, const mod_int<MOD> mi2) noexcept { [[assume(mi1.value < MOD && mi2.value < MOD)]]; return mod_int<MOD>(mi1.value >= MOD - mi2.value ? mi1.value - (MOD - mi2.value) : mi1.value + mi2.value); }
		[[nodiscard]] friend constexpr mod_int<MOD> operator-(const mod_int<MOD> mi1, const mod_int<MOD> mi2) noexcept { [[assume(mi1.value < MOD && mi2.value < MOD)]]; return mod_int<MOD>(mi1.value >= mi2.value ? mi1.value - mi2.value : MOD - (mi2.value - mi1.value)); }
		[[nodiscard]] friend constexpr mod_int<MOD> operator*(const mod_int<MOD> mi1, const mod_int<MOD> mi2) noexcept { [[assume(mi1.value < MOD && mi2.value < MOD)]]; if constexpr (MOD >= (1u << 16)) return mod_int<MOD>(static_cast<uint_fast64_t>(mi1.value) * mi2.value % MOD); else return mod_int<MOD>(mi1.value * mi2.value % MOD); }
		[[nodiscard]] friend constexpr mod_int<MOD> operator/(const mod_int<MOD> mi1, const mod_int<MOD> mi2) noexcept { [[assume(mi1.value < MOD && mi2.value < MOD)]]; static_assert(is_prime(MOD), "\'MOD\' is not a prime number."); if constexpr (MOD >= (1u << 16)) return mod_int<MOD>(static_cast<uint_fast64_t>(mi1.value) * pow_mod(mi2.value, MOD - 2) % MOD); else return mod_int<MOD>(mi1.value * pow_mod(mi2.value, MOD - 2) % MOD); }
		template<typename T> [[nodiscard]] friend constexpr mod_int<MOD> operator+(const mod_int<MOD> mi, T arg) noexcept { [[assume(mi.value < MOD)]]; arg %= MOD; return mod_int<MOD>(mi.value >= MOD - static_cast<uint_fast32_t>(arg) ? mi.value - (MOD - static_cast<uint_fast32_t>(arg)) : mi.value + static_cast<uint_fast32_t>(arg)); }
		template<typename T> [[nodiscard]] friend constexpr mod_int<MOD> operator-(const mod_int<MOD> mi, T arg) noexcept { [[assume(mi.value < MOD)]]; arg %= MOD; return mod_int<MOD>(mi.value >= static_cast<uint_fast32_t>(arg) ? mi.value - static_cast<uint_fast32_t>(arg) : MOD - (static_cast<uint_fast32_t>(arg) - mi.value)); }
		template<typename T> [[nodiscard]] friend constexpr mod_int<MOD> operator*(const mod_int<MOD> mi, const T arg) noexcept { [[assume(mi.value < MOD)]]; if constexpr (MOD >= (1u << 16)) return mod_int<MOD>(static_cast<uint_fast64_t>(mi.value) * (arg % MOD) % MOD); else return mod_int<MOD>(mi.value * static_cast<uint_fast32_t>(arg % MOD) % MOD); }
		template<typename T> [[nodiscard]] friend constexpr mod_int<MOD> operator/(const mod_int<MOD> mi, const T arg) noexcept { [[assume(mi.value < MOD)]]; static_assert(is_prime(MOD), "\'MOD\' is not a prime number."); if constexpr (MOD >= (1u << 16)) return mod_int<MOD>(static_cast<uint_fast64_t>(mi.value) * pow_mod(static_cast<uint_fast32_t>(arg % MOD), MOD - 2) % MOD); else return mod_int<MOD>(mi.value * pow_mod(static_cast<uint_fast32_t>(arg % MOD), MOD - 2) % MOD); }
		template<typename T> [[nodiscard]] friend constexpr mod_int<MOD> operator+(T arg, const mod_int<MOD> mi) noexcept { [[assume(mi.value < MOD)]]; return mi + arg; }
		template<typename T> [[nodiscard]] friend constexpr mod_int<MOD> operator-(T arg, const mod_int<MOD> mi) noexcept { [[assume(mi.value < MOD)]]; return (-mi) + arg; }
		template<typename T> [[nodiscard]] friend constexpr mod_int<MOD> operator*(const T arg, const mod_int<MOD> mi) noexcept { [[assume(mi.value < MOD)]]; return mi * arg; }
		template<typename T> [[nodiscard]] friend constexpr mod_int<MOD> operator/(const T arg, const mod_int<MOD> mi) noexcept { [[assume(mi.value < MOD)]]; return mi.pow_mod(MOD - 2) * arg; }

		constexpr mod_int<MOD>& operator+=(const mod_int<MOD> other) noexcept { [[assume(value < MOD && other.value < MOD)]]; if (value >= MOD - other.value) value -= (MOD - other.value); else value += other.value; return *this; }
		constexpr mod_int<MOD>& operator-=(const mod_int<MOD> other) noexcept { [[assume(value < MOD && other.value < MOD)]]; if (value >= other.value) value -= other.value; else value += (MOD - other.value); return *this; }
		constexpr mod_int<MOD>& operator*=(const mod_int<MOD> other) noexcept { [[assume(value < MOD && other.value < MOD)]]; if constexpr (MOD >= (1u << 16)) value = static_cast<uint_fast64_t>(value) * other.value % MOD; else value = value * other.value % MOD; return *this; }
		constexpr mod_int<MOD>& operator/=(const mod_int<MOD> other) noexcept { [[assume(value < MOD && other.value < MOD)]]; static_assert(is_prime(MOD), "\'MOD\' is not a prime number."); if constexpr (MOD >= (1u << 16)) value = static_cast<uint_fast64_t>(value) * pow_mod(other.value, MOD - 2) % MOD; else value = value * pow_mod(other.value, MOD - 2) % MOD; return *this; }
		template<typename T> constexpr mod_int<MOD>& operator+=(T arg) noexcept { [[assume(value < MOD)]]; arg %= MOD; if (value >= MOD - arg) value -= (MOD - arg); else value += arg; return *this; }
		template<typename T> constexpr mod_int<MOD>& operator-=(T arg) noexcept { [[assume(value < MOD)]]; arg %= MOD; if (value >= arg) value -= arg; else value += (MOD - arg); return *this; }
		template<typename T> constexpr mod_int<MOD>& operator*=(const T arg) noexcept { [[assume(value < MOD)]]; if constexpr (MOD >= (1u << 16)) value = static_cast<uint_fast64_t>(value) * (arg % MOD) % MOD; else value = value * (arg % MOD) % MOD; return *this; }
		template<typename T> constexpr mod_int<MOD>& operator/=(const T arg) noexcept { [[assume(value < MOD)]]; static_assert(is_prime(MOD), "\'MOD\' is not a prime number."); if constexpr (MOD >= (1u << 16)) value = static_cast<uint_fast64_t>(value) * pow_mod(static_cast<uint_fast32_t>(arg % MOD), MOD - 2) % MOD; else value = value * pow_mod(static_cast<uint_fast32_t>(arg % MOD), MOD - 2) % MOD; return *this; }
		template<typename T> friend constexpr T& operator+=(T& arg, const mod_int<MOD> mi) noexcept { [[assume(mi.value < MOD)]]; return arg += mi.value; }
		template<typename T> friend constexpr T& operator-=(T& arg, const mod_int<MOD> mi) noexcept { [[assume(mi.value < MOD)]]; return arg -= mi.value; }
		template<typename T> friend constexpr T& operator*=(T& arg, const mod_int<MOD> mi) noexcept { [[assume(mi.value < MOD)]]; return arg *= mi.value; }
		template<typename T> friend constexpr T& operator/=(T& arg, const mod_int<MOD> mi) noexcept { [[assume(mi.value < MOD)]]; return arg /= mi.value; }

		constexpr mod_int<MOD>& operator++() noexcept { [[assume(value < MOD)]]; if (value + 1 == MOD) [[unlikely]] value = 0; else ++value; return *this; }
		constexpr mod_int<MOD> operator++(int) noexcept { [[assume(value < MOD)]]; const auto temp = value; if (value + 1 == MOD) [[unlikely]] value = 0; else ++value; return mod_int<MOD>(temp); }
		constexpr mod_int<MOD>& operator--() noexcept { [[assume(value < MOD)]]; if (value == 0) [[unlikely]] value = MOD - 1; else --value; return *this; }
		constexpr mod_int<MOD> operator--(int) noexcept { [[assume(value < MOD)]]; const auto temp = value; if (value == 0) [[unlikely]] value = MOD - 1; else --value; return *this; }

		[[nodiscard]] friend constexpr bool operator==(const mod_int<MOD> mi1, const mod_int<MOD> mi2) noexcept { [[assume(mi1.value < MOD && mi2.value < MOD)]]; return mi1.value == mi2.value; }
		[[nodiscard]] friend constexpr bool operator!=(const mod_int<MOD> mi1, const mod_int<MOD> mi2) noexcept { [[assume(mi1.value < MOD && mi2.value < MOD)]]; return mi1.value != mi2.value; }
		[[nodiscard]] friend constexpr bool operator<(const mod_int<MOD> mi1, const mod_int<MOD> mi2) noexcept { [[assume(mi1.value < MOD && mi2.value < MOD)]]; return mi1.value < mi2.value; }
		[[nodiscard]] friend constexpr bool operator<=(const mod_int<MOD> mi1, const mod_int<MOD> mi2) noexcept { [[assume(mi1.value < MOD && mi2.value < MOD)]]; return mi1.value <= mi2.value; }
		[[nodiscard]] friend constexpr bool operator>(const mod_int<MOD> mi1, const mod_int<MOD> mi2) noexcept { [[assume(mi1.value < MOD && mi2.value < MOD)]]; return mi1.value > mi2.value; }
		[[nodiscard]] friend constexpr bool operator>=(const mod_int<MOD> mi1, const mod_int<MOD> mi2) noexcept { [[assume(mi1.value < MOD && mi2.value < MOD)]]; return mi1.value >= mi2.value; }
		template<typename T> [[nodiscard]] friend constexpr bool operator==(const mod_int<MOD> mi, const T arg) noexcept { [[assume(mi.value < MOD)]]; static_assert(std::is_integral<T>::value, "T is not an integral type."); return mi.value == arg; }
		template<typename T> [[nodiscard]] friend constexpr bool operator!=(const mod_int<MOD> mi, const T arg) noexcept { [[assume(mi.value < MOD)]]; static_assert(std::is_integral<T>::value, "T is not an integral type."); return mi.value != arg; }
		template<typename T> [[nodiscard]] friend constexpr bool operator<(const mod_int<MOD> mi, const T arg) noexcept { [[assume(mi.value < MOD)]]; static_assert(std::is_integral<T>::value, "T is not an integral type."); return mi.value < arg; }
		template<typename T> [[nodiscard]] friend constexpr bool operator<=(const mod_int<MOD> mi, const T arg) noexcept { [[assume(mi.value < MOD)]]; static_assert(std::is_integral<T>::value, "T is not an integral type."); return mi.value <= arg; }
		template<typename T> [[nodiscard]] friend constexpr bool operator>(const mod_int<MOD> mi, const T arg) noexcept { [[assume(mi.value < MOD)]]; static_assert(std::is_integral<T>::value, "T is not an integral type."); return mi.value > arg; }
		template<typename T> [[nodiscard]] friend constexpr bool operator>=(const mod_int<MOD> mi, const T arg) noexcept { [[assume(mi.value < MOD)]]; static_assert(std::is_integral<T>::value, "T is not an integral type."); return mi.value >= arg; }
		template<typename T> [[nodiscard]] friend constexpr bool operator==(const T arg, const mod_int<MOD> mi) noexcept { [[assume(mi.value < MOD)]]; return mi == arg; }
		template<typename T> [[nodiscard]] friend constexpr bool operator!=(const T arg, const mod_int<MOD> mi) noexcept { [[assume(mi.value < MOD)]]; return mi != arg; }
		template<typename T> [[nodiscard]] friend constexpr bool operator<(const T arg, const mod_int<MOD> mi) noexcept { [[assume(mi.value < MOD)]]; return mi > arg; }
		template<typename T> [[nodiscard]] friend constexpr bool operator<=(const T arg, const mod_int<MOD> mi) noexcept { [[assume(mi.value < MOD)]]; return mi >= arg; }
		template<typename T> [[nodiscard]] friend constexpr bool operator>(const T arg, const mod_int<MOD> mi) noexcept { [[assume(mi.value < MOD)]]; return mi < arg; }
		template<typename T> [[nodiscard]] friend constexpr bool operator>=(const T arg, const mod_int<MOD> mi) noexcept { [[assume(mi.value < MOD)]]; return mi <= arg; }

		[[nodiscard]] constexpr operator unsigned int() const noexcept { [[assume(value < MOD)]]; return this->value; }

		[[nodiscard]] constexpr mod_int<MOD> pow_mod(uint_fast64_t times) const noexcept
		{
			[[assume(value < MOD)]];
			if constexpr (MOD == 1) return 0;
			mod_int<MOD> ans = 1, a = value;
			for (; times != 0; times >>= 1, a *= a)
				if (times & 1) ans *= a;

			return ans;
		}
	};
}

[[nodiscard]] static inline constexpr uint_fast32_t solve(const std::string& S) noexcept
{
	std::array<std::array<std::array<MyLib::mod_int<998244353>, 2>, 2>, 2> dp = { { std::array<MyLib::mod_int<998244353>, 2>{ 0, 1 }, std::array<MyLib::mod_int<998244353>, 2>{ 0, 0 } }, };
	for (uint_fast32_t i = 0; i != S.size(); ++i)
	{
		dp[(i & 1) ^ 1] = { std::array<MyLib::mod_int<998244353>, 2>{ 0, 0 }, std::array<MyLib::mod_int<998244353>, 2>{ 0, 0 } };
		for (uint_fast32_t j = 0; j != (S[i] - '0'); ++j)
		{
			if (j != 8) [[likely]]
			{
				dp[(i & 1) ^ 1][0][0] += dp[i & 1][0][0] + dp[i & 1][0][1];
				dp[(i & 1) ^ 1][1][0] += dp[i & 1][1][0] + dp[i & 1][1][1];
			}
			else
				dp[(i & 1) ^ 1][1][0] += dp[i & 1][0][0] + dp[i & 1][0][1] + dp[i & 1][1][0] + dp[i & 1][1][1];
		}

		if (S[i] - '0' != 8) [[likely]]
		{
			dp[(i & 1) ^ 1][0][0] += dp[i & 1][0][0];
			dp[(i & 1) ^ 1][0][1] += dp[i & 1][0][1];
			dp[(i & 1) ^ 1][1][0] += dp[i & 1][1][0];
			dp[(i & 1) ^ 1][1][1] += dp[i & 1][1][1];
		}
		else
		{
			dp[(i & 1) ^ 1][1][0] += dp[i & 1][0][0] + dp[i & 1][1][0];
			dp[(i & 1) ^ 1][1][1] += dp[i & 1][0][1] + dp[i & 1][1][1];
		}

		for (uint_fast32_t j = S[i] - '0' + 1; j != 10; ++j)
		{
			if (j != 8) [[likely]]
			{
				dp[(i & 1) ^ 1][0][0] += dp[i & 1][0][0];
				dp[(i & 1) ^ 1][1][0] += dp[i & 1][1][0];
			}
			else
				dp[(i & 1) ^ 1][1][0] += dp[i & 1][0][0] + dp[i & 1][1][0];
		}
	}

	return dp[S.size() & 1][1][0] + dp[S.size() & 1][1][1];
}

int main()
{
	std::cin.tie(nullptr);
	std::ios::sync_with_stdio(false);
	
	std::string S;
	S.reserve(888'888);
	std::cin >> S;

	std::cout << solve(S) << '\n';
	return 0;
}
0