結果
問題 | No.269 見栄っ張りの募金活動 |
ユーザー |
![]() |
提出日時 | 2024-02-03 10:35:59 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,858 ms / 5,000 ms |
コード長 | 22,602 bytes |
コンパイル時間 | 2,950 ms |
コンパイル使用メモリ | 249,028 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-28 10:46:03 |
合計ジャッジ時間 | 12,401 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
#line 1 "Library/src/atcoder/modint.hpp"#include <cassert>#include <numeric>#include <type_traits>#ifdef _MSC_VER#include <intrin.h>#endif#line 1 "Library/src/atcoder/internal_math.hpp"#include <utility>#ifdef _MSC_VER#include <intrin.h>#endifnamespace atcoder {namespace internal {// @param m `1 <= m`// @return x mod mconstexpr 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 Lakestruct 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 munsigned 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 + 1unsigned long long z = a;z *= b;#ifdef _MSC_VERunsigned long long x;_umul128(z, im, &x);#elseunsigned long long x =(unsigned long long)(((unsigned __int128)(z)*im) >> 64);#endifunsigned 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/gconstexpr 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| <= blong 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| <= bauto tmp = s;s = t;t = tmp;tmp = m0;m0 = m1;m1 = tmp;}// by [3]: |m0| <= b/g// by g != b: |m0| < b/gif (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) <= nn = (unsigned long long)(y_max / m);b = (unsigned long long)(y_max % m);std::swap(m, a);}return ans;}} // namespace internal} // namespace atcoder#line 1 "Library/src/atcoder/internal_type_traits.hpp"#line 7 "Library/src/atcoder/internal_type_traits.hpp"namespace atcoder {namespace internal {#ifndef _MSC_VERtemplate <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;#elsetemplate <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;#endiftemplate <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#line 14 "Library/src/atcoder/modint.hpp"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 internaltemplate <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#line 1 "Library/src/debug.hpp"#ifdef ONLINE_JUDGE#define debug(x) void(0)#else#define _GLIBCXX_DEBUG#define debug(x) std::cerr << __LINE__ << " : " << #x << " = " << (x) << std::endl#endif#line 2 "Library/src/stream.hpp"#include <ctype.h>#include <stdio.h>#include <string>#line 2 "Library/src/internal/type_traits.hpp"#include <iostream>#include <limits>#line 5 "Library/src/internal/type_traits.hpp"#include <typeinfo>#include <cstdint>namespace kyopro {namespace internal {template <typename... Args> struct first_enabled {};template <typename T, typename... Args>struct first_enabled<std::enable_if<true, T>, Args...> {using type = T;};template <typename T, typename... Args>struct first_enabled<std::enable_if<false, T>, Args...>: first_enabled<Args...> {};template <typename T, typename... Args> struct first_enabled<T, Args...> {using type = T;};template <typename... Args>using first_enabled_t = typename first_enabled<Args...>::type;template <int dgt, std::enable_if_t<dgt <= 128>* = nullptr> struct int_least {using type = first_enabled_t<std::enable_if<dgt <= 8, std::int8_t>,std::enable_if<dgt <= 16, std::int16_t>,std::enable_if<dgt <= 32, std::int32_t>,std::enable_if<dgt <= 64, std::int64_t>,std::enable_if<dgt <= 128, __int128_t>>;};template <int dgt, std::enable_if_t<dgt <= 128>* = nullptr> struct uint_least {using type = first_enabled_t<std::enable_if<dgt <= 8, std::uint8_t>,std::enable_if<dgt <= 16, std::uint16_t>,std::enable_if<dgt <= 32, std::uint32_t>,std::enable_if<dgt <= 64, std::uint64_t>,std::enable_if<dgt <= 128, __uint128_t>>;};template <int dgt> using int_least_t = typename int_least<dgt>::type;template <int dgt> using uint_least_t = typename uint_least<dgt>::type;template <typename T>using double_size_uint_t = uint_least_t<2 * std::numeric_limits<T>::digits>;template <typename T>using double_size_int_t = int_least_t<2 * std::numeric_limits<T>::digits>;struct modint_base {};template <typename T> using is_modint = std::is_base_of<modint_base, T>;template <typename T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;// is_integraltemplate <typename T>using is_integral_t =std::enable_if_t<std::is_integral_v<T> || std::is_same_v<T, __int128_t> ||std::is_same_v<T, __uint128_t>>;}; // namespace internal}; // namespace kyopro/** @ref https://qiita.com/kazatsuyu/items/f8c3b304e7f8b35263d8*/#line 6 "Library/src/stream.hpp"namespace kyopro {inline void single_read(char& c) {c = getchar_unlocked();while (isspace(c)) c = getchar_unlocked();}template <typename T, internal::is_integral_t<T>* = nullptr>inline void single_read(T& a) {a = 0;bool is_negative = false;char c = getchar_unlocked();while (isspace(c)) {c = getchar_unlocked();}if (c == '-') is_negative = true, c = getchar_unlocked();while (isdigit(c)) {a = 10 * a + (c - '0');c = getchar_unlocked();}if (is_negative) a *= -1;}template <typename T, internal::is_modint_t<T>* = nullptr>inline void single_read(T& a) {long long x;single_read(x);a = T(x);}inline void single_read(std::string& str) noexcept {char c = getchar_unlocked();while (isspace(c)) c = getchar_unlocked();while (!isspace(c)) {str += c;c = getchar_unlocked();}}template<typename T>inline void read(T& x) noexcept {single_read(x);}template <typename Head, typename... Tail>inline void read(Head& head, Tail&... tail) noexcept {single_read(head), read(tail...);}inline void single_write(char c) noexcept { putchar_unlocked(c); }template <typename T, internal::is_integral_t<T>* = nullptr>inline void single_write(T a) noexcept {if (!a) {putchar_unlocked('0');return;}if constexpr (std::is_signed_v<T>) {if (a < 0) putchar_unlocked('-'), a *= -1;}constexpr int d = std::numeric_limits<T>::digits10;char s[d + 1];int now = d + 1;while (a) {s[--now] = (char)'0' + a % 10;a /= 10;}while (now <= d) putchar_unlocked(s[now++]);}template <typename T, internal::is_modint_t<T>* = nullptr>inline void single_write(T a) noexcept {single_write(a.val());}inline void single_write(const std::string& str) noexcept {for (auto c : str) {putchar_unlocked(c);}}template <typename T> inline void write(T x) noexcept { single_write(x); }template <typename Head, typename... Tail>inline void write(Head head, Tail... tail) noexcept {single_write(head);putchar_unlocked(' ');write(tail...);}template <typename... Args> inline void put(Args... x) noexcept {write(x...);putchar_unlocked('\n');}}; // namespace kyopro/*** @brief 高速入出力*/#line 2 "Library/src/template.hpp"#include <bits/stdc++.h>#define rep(i, n) for (int i = 0; i < (n); i++)#define all(x) std::begin(x), std::end(x)#define popcount(x) __builtin_popcountll(x)using i128 = __int128_t;using ll = long long;using ld = long double;using graph = std::vector<std::vector<int>>;using P = std::pair<int, int>;constexpr int inf = std::numeric_limits<int>::max() / 2;constexpr ll infl = std::numeric_limits<ll>::max() / 2;const long double pi = acosl(-1);constexpr uint64_t MOD = 1e9 + 7;constexpr uint64_t MOD2 = 998244353;constexpr int dx[] = {1, 0, -1, 0, 1, -1, -1, 1, 0};constexpr int dy[] = {0, 1, 0, -1, 1, 1, -1, -1, 0};template <typename T1, typename T2> constexpr inline bool chmax(T1& a, T2 b) {return a < b && (a = b, true);}template <typename T1, typename T2> constexpr inline bool chmin(T1& a, T2 b) {return a > b && (a = b, true);}#line 5 "a.cpp"using namespace std;using namespace kyopro;using mint = atcoder::modint1000000007;int main() {int n, s, k;read(n, s, k);vector dp(s + 1, mint());for (int i = 0; n * i <= s; ++i) dp[n * i] = mint::raw(1);for (int i = 1; i < n; ++i) {vector ndp(s + 1, mint());rep(t, s + 1) {for (int x = k; (ll)t + (n - i) * x <= s; ++x) {ndp[t + (n - i) * x] += dp[t];}}swap(dp, ndp);}put(dp[s].val());}