結果
問題 | No.269 見栄っ張りの募金活動 |
ユーザー |
![]() |
提出日時 | 2024-07-17 17:18:47 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 41 ms / 5,000 ms |
コード長 | 3,668 bytes |
コンパイル時間 | 10,208 ms |
コンパイル使用メモリ | 547,796 KB |
実行使用メモリ | 13,568 KB |
最終ジャッジ日時 | 2024-07-17 17:19:03 |
合計ジャッジ時間 | 11,943 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>#include <boost/multiprecision/cpp_dec_float.hpp>#include <boost/multiprecision/cpp_int.hpp>#include <boost/rational.hpp>using Bint = boost::multiprecision::cpp_int;// 仮数部が10進数で1024桁の浮動小数点数型(TLEしたら小さくする)using Real = boost::multiprecision::number<boost::multiprecision::cpp_dec_float<1024>>;using Rat = boost::rational<Bint>;using namespace std;using ll = long long;#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)#define all(x) begin(x), end(x)#define TT template <typename T>TT using vec = vector<T>;TT using minheap = priority_queue<T, vector<T>, greater<T>>;TT using maxheap = priority_queue<T>;template <class T1, class T2> bool chmin(T1 &x, T2 y) {return x > y ? (x = y, true) : false;}template <class T1, class T2> bool chmax(T1 &x, T2 y) {return x < y ? (x = y, true) : false;}TT int pre_id(vec<T> &A, T x) { // must sortedreturn lower_bound(all(A), x) - A.begin() - 1;}TT int nex_id(vec<T> &A, T x) { // must sortedreturn upper_bound(all(A), x) - A.begin();}struct io_setup {io_setup() {ios::sync_with_stdio(false);std::cin.tie(nullptr);cout << fixed << setprecision(15);}} io_setup;//動的mod : template<int mod> を消して、上の方で変数modを宣言template<uint32_t mod>struct modint{using mm = modint;uint32_t x;modint() : x(0) {}TT modint(T a=0) : x((a % mod + mod) % mod){}friend mm operator+(mm a, mm b) {a.x += b.x;if(a.x >= mod) a.x -= mod;return a;}friend mm operator-(mm a, mm b) {a.x -= b.x;if(a.x >= mod) a.x += mod;return a;}//+と-だけで十分な場合、以下は省略して良いです。friend mm operator*(mm a, mm b) { return (uint64_t)(a.x) * b.x; }friend mm operator/(mm a, mm b) { return a * b.inv(); }friend mm& operator+=(mm& a, mm b) { return a = a + b; }friend mm& operator-=(mm& a, mm b) { return a = a - b; }friend mm& operator*=(mm& a, mm b) { return a = a * b; }friend mm& operator/=(mm& a, mm b) { return a = a * b.inv(); }mm inv() const {return pow(mod-2);}mm pow(const ll& y) const {if(!y) return 1;mm res = pow(y >> 1);res *= res;if(y & 1) res *= *this;return res;}friend istream& operator>>(istream &is, mm &a) {ll t;cin >> t;a = mm(t);return is;}friend ostream& operator<<(ostream &os, mm a) {return os << a.x;}bool operator==(mm a) {return x == a.x;}bool operator!=(mm a) {return x != a.x;}bool operator<(const mm& a) const {return x < a.x;}};using modint998244353 = modint<998244353>;using modint1000000007 = modint<1'000'000'007>;/*@brief modint*/using mint = modint1000000007;int main() {ll n, s, k;cin >> n >> s >> k;vec<vec<mint>> dp(n + 1, vec<mint>(s + 1, 0));// [i][j] .. i人で総和sを払う場合の和。vec<vec<bool>> memo(n + 1, vec<bool>(s + 1, false));auto dfs = [&](auto f, ll N, ll S) -> mint {if(N == 0) {if(S == 0) return 1;else return 0;}if(N < 0 || S < 0) return 0;if(memo[N][S]) return dp[N][S];//0円が入る場合dp[N][S] += f(f, N-1, S - (N-1) * k);//0円が入らない場合dp[N][S] += f(f, N, S - N);memo[N][S] = true;return dp[N][S];};cout << dfs(dfs, n, s) << endl;}