#1150343 (C++23) No.3457 Fibo-shrink

提出ソース

結果

問題	No.3457 Fibo-shrink
コンテスト
ユーザー	tomolatoon
提出日時	2026-02-28 14:55:32
言語	C++23 (gcc 15.2.0 + boost 1.89.0) コンパイル: `g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_` 実行: `./a.out`
結果	RE
実行時間	-
コード長	7,279 bytes
記録記録タグの例: 初AC ショートコード純ショートコード純主流ショートコード最速実行時間
コンパイル時間	5,583 ms
コンパイル使用メモリ	285,056 KB
実行使用メモリ	7,844 KB
最終ジャッジ日時	2026-02-28 14:55:41
合計ジャッジ時間	6,995 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

このコードへのチャレンジ
（要ログイン）

ファイルパターン	結果
sample	AC * 2
other	AC * 11 RE * 1

権限があれば一括ダウンロードができます

ソースコード

raw source code

//#include <bits/stdc++.h>
#include <algorithm>
#include <bit>
#include <cassert>
#include <charconv>
#include <cmath>
#include <cstdint>
#include <deque>
#include <functional>
#include <initializer_list>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <ranges>
#include <set>
#include <span>
#include <stack>
#include <string>
#include <string_view>
#include <tuple>
#include <vector>

#include <atcoder/modint.hpp>

// #define OLD_JUDGE

#ifdef OLD_JUDGE
# define USE_ISTREAM
# define USE_OSTREAM
#else
# define USE_ISTREAM
# define USE_PRINT
#endif

#if defined(USE_ISTREAM) || defined(USE_OSTREAM)
# include <iomanip>
# include <iostream>
#endif

#ifdef USE_PRINT
# include <format>
# include <print>
#endif

namespace tomolatoon
{
	using namespace std::views;
	namespace rng = std::ranges;

#ifdef USE_ISTREAM
	using std::cin;
#endif

#ifdef USE_OSTREAM
	using std::cout;
	using std::endl;
#endif

#ifdef USE_PRINT
	using std::format;
	using std::print;
	using std::println;

	template <class T>
	void pr(T&& t)
	{
		print("{}", std::forward<T>(t));
	}

	template <class T>
	void prn(T&& t)
	{
		println("{}", std::forward<T>(t));
	}
#endif

	using rng::subrange;
	using std::array;
	using std::deque;
	using std::list;
	using std::map;
	using std::multimap;
	using std::multiset;
	using std::pair;
	using std::queue;
	using std::set;
	using std::span;
	using std::stack;
	using std::string;
	using std::string_view;
	using std::tuple;
	using std::vector;

	template <class T>
	using vec = vector<T>;

	using uint = std::uint32_t;

	using ull = std::uint64_t;
	using ll  = std::int64_t;

	using std::size_t;

	// clang-format off
	using rng::all_of;
	using rng::any_of;
#ifndef OLD_JUDGE
	using rng::none_of;
	using rng::contains;
	using rng::contains_subrange;
#endif
	using rng::for_each;
	using rng::for_each_n;

	using rng::find;
	using rng::find_if;
	using rng::find_if_not;
#ifndef OLD_JUDGE
	using rng::find_last;
	using rng::find_last_if;
	using rng::find_last_if_not;
#endif
	using rng::find_end;
	using rng::find_first_of;
	using rng::adjacent_find;
	using rng::count;
	using rng::count_if;
	using rng::mismatch;
	using rng::equal;
	using rng::search;
	using rng::search_n;
	// clang-format on

	using rng::sort;
	using rng::stable_sort;
	using rng::unique;

	using rng::max_element;
	using rng::min_element;

	using rng::binary_search;
	using rng::equal_range;
	using rng::lower_bound;
	using rng::upper_bound;

	using rng::next_permutation;
	using rng::prev_permutation;

	using rng::begin;
	using rng::distance;
	using rng::end;
	using rng::ssize;
	using rng::swap;

	using std::abs;
	using std::midpoint;

	using std::back_inserter;
	using std::front_inserter;
	using std::inserter;

	using namespace std::placeholders;

	void yn(bool f)
	{
#ifdef USE_OSTREAM
		cout << (f ? "Yes" : "No") << "\n";
#elifdef USE_PRINT
		println("{}", (f ? "Yes" : "No"));
#endif
	}

	string yns(bool f)
	{
		return f ? "Yes" : "No";
	}

	// clang-format off
	struct P
	{
		using type = ll;

		type i;
		type j;

		P moved(type id, type jd) const { return {i + id, j + jd}; }
		P moved(P pd) const { return moved(pd.i, pd.j); }

		template <class T>
		T& operator[](vec<vec<T>>& v) const { return v[i][j]; }
		char& operator[](vec<string>& v) const { return v[i][j]; }

		friend P operator+(const P& lhs, const P& rhs) { return lhs.moved(rhs); }
		friend P operator-(const P& lhs, const P& rhs) { return lhs.moved(-rhs); }
		P operator-() const { return P{-i, -j}; }

		friend bool operator==(const P& lhs, const P& rhs) { return lhs.i == rhs.i && lhs.j == rhs.j; }
		friend auto operator<=>(const P& lhs, const P& rhs) { return lhs.i != rhs.i ? lhs.i <=> rhs.i : lhs.j <=> rhs.j; }
	
		ll L1() const { return std::abs(i) + std::abs(j); }
		friend ll ip(const P& lhs, const P& rhs) { return lhs.i * rhs.i + lhs.j * rhs.j; }
	};

	const auto in_f = [](P::type h, P::type w) { return [=](P p) { return 0 <= p.i && p.i < h && 0 <= p.j && p.j < w; }; };

	static const auto P4 = array<P, 4>{P{-1,  0}, P{ 0, -1}, P{ 1,  0}, P{ 0,  1}};
	static const auto P8 = array<P, 8>{P{-1,  0}, P{-1, -1}, P{ 0, -1}, P{ 1, -1}, P{ 1,  0}, P{ 1,  1}, P{ 0,  1}, P{-1,  1}};
	// clang-format on

	ll pow(ll base, size_t n)
	{
		assert(not(base == 0 && n == 0));
		if (n == 0) return 1;
		if (n == 1) return base;
		ll prev = pow(base, n / 2);
		return prev * prev * (n % 2 ? base : 1);
	}

	ll pow(ll base, size_t n, ll mod)
	{
		assert(not(base == 0 && n == 0));
		constexpr auto modf = [](ll x, ll mod) {
			return (x % mod + mod) % mod;
		};

		if (base >= mod) base %= mod;
		if (n == 0) return 1;
		if (n == 1) return base;
		ll prev = pow(base, n / 2);
		ll pp   = modf(prev * prev, mod);
		return (n % 2 ? modf(pp * base, mod) : pp);
	}

	template <class T>
	T shared_length_signed(T l1, T r1, T l2, T r2)
	{
		return rng::min(r1, r2) - rng::max(l1, l2);
	}

	template <class T>
	T shared_length(T l1, T r1, T l2, T r2)
	{
		return rng::max(0, rng::min(r1, r2) - rng::max(l1, l2));
	}

	/// @brief ランレングス圧縮（RLE: Run Length Encoding）を行い，出力イテレータへ書き込む
	/// @note vec<pair<T, size_t>>をreserveし，それのback_inserter(back_insert_iterator)を渡すことが想定される
	/// @param r ランレングス圧縮したいrange
	/// @param out 出力イテレータ
	template <rng::forward_range R, std::output_iterator<std::pair<rng::range_value_t<R>, size_t>> I>
	requires std::copyable<rng::range_value_t<R>> && std::equality_comparable<rng::range_value_t<R>>
	void rle(R&& r, I out)
	{
		using pair = std::pair<rng::range_value_t<R>, size_t>;

		auto it = begin(r);
		auto e  = end(r);

		if (it == e)
		{
			return;
		}

		size_t                size = 1;
		rng::range_value_t<R> prev = *it;

		++it;

		for (; it != e; ++it)
		{
			if (*it == prev)
			{
				++size;
			}
			else
			{
				*out++ = pair(std::move(prev), size);
				prev   = *it;
				size   = 1;
			}
		}

		*out++ = pair(std::move(prev), size);
	}

	namespace detail
	{
		template <size_t N>
		struct get
		{
			template <class T>
			// static
			constexpr decltype(auto) operator()(T&& t) noexcept(noexcept(std::get<N>(t)))
			{
				return std::get<N>(t);
			}
		};
	} // namespace detail

	template <size_t N>
	inline constexpr auto get = detail::get<N>{};

	constexpr ll INF = 3e18;
} // namespace tomolatoon

namespace tomolatoon
{
	using namespace atcoder;

	using mint = static_modint<10007>;

	void solve()
	{
		ll k, s, n;
		cin >> k >> s >> n;

		vec<mint> fib(rng::max(k, n) + 100);
		fib[0] = 1;
		fib[1] = 1;
		for (auto i : iota(2, ssize(fib)))
		{
			fib[i] = fib[i - 1] + fib[i - 2];
		}

		vec<mint> fib_inv(ssize(fib));
		for (auto i : iota(0, ssize(fib)))
		{
			fib_inv[i] = fib[i].inv();
		}

		vec<mint> sfib(n);
		sfib[0] = s;
		for (auto i : iota(0, n - 1))
		{
			for (auto j : iota(0, k + 1))
			{
				if (i - j >= 0)
				{
					sfib[i + 1] += sfib[i - j] * fib_inv[j];
				}
			}
		}

		prn(sfib.back().val());
	}
} // namespace tomolatoon

int main()
{
#ifdef USE_ISTREAM
	std::cin.tie(nullptr);
	std::ios::sync_with_stdio(false);
#endif

#ifdef USE_OSTREAM
	std::cout << std::fixed << std::setprecision(16);
#endif

	tomolatoon::solve();

#ifdef USE_OSTREAM
	std::cout << std::flush;
#endif
}

yukicoder

結果

ソースコード