結果
問題 |
No.269 見栄っ張りの募金活動
|
ユーザー |
|
提出日時 | 2020-09-22 16:52:35 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 2,834 bytes |
コンパイル時間 | 1,690 ms |
コンパイル使用メモリ | 171,208 KB |
実行使用メモリ | 817,408 KB |
最終ジャッジ日時 | 2024-06-26 06:25:56 |
合計ジャッジ時間 | 4,545 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 1 MLE * 1 -- * 20 |
ソースコード
// No.269 見栄っ張りの募金活動 // 分割数による解法 #include <bits/stdc++.h> using namespace std; typedef long long ll; // const int INF = 2147483647; // const ll INF = 9223372036854775807; // modint: mod 計算を int を扱うように扱える構造体 template<int MOD> struct ModInt { long long val; constexpr ModInt(long long v = 0) noexcept : val(v % MOD) { if (val < 0) val += MOD; } constexpr int getmod() { return MOD; } constexpr ModInt operator - () const noexcept { return val ? MOD - val : 0; } constexpr ModInt operator + (const ModInt& r) const noexcept { return ModInt(*this) += r; } constexpr ModInt operator - (const ModInt& r) const noexcept { return ModInt(*this) -= r; } constexpr ModInt operator * (const ModInt& r) const noexcept { return ModInt(*this) *= r; } constexpr ModInt operator / (const ModInt& r) const noexcept { return ModInt(*this) /= r; } constexpr ModInt& operator += (const ModInt& r) noexcept { val += r.val; if (val >= MOD) val -= MOD; return *this; } constexpr ModInt& operator -= (const ModInt& r) noexcept { val -= r.val; if (val < 0) val += MOD; return *this; } constexpr ModInt& operator *= (const ModInt& r) noexcept { val = val * r.val % MOD; return *this; } constexpr ModInt& operator /= (const ModInt& r) noexcept { long long a = r.val, b = MOD, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } val = val * u % MOD; if (val < 0) val += MOD; return *this; } constexpr bool operator == (const ModInt& r) const noexcept { return this->val == r.val; } constexpr bool operator != (const ModInt& r) const noexcept { return this->val != r.val; } friend constexpr ostream& operator << (ostream &os, const ModInt<MOD>& x) noexcept { return os << x.val; } friend constexpr ModInt<MOD> modpow(const ModInt<MOD> &a, long long n) noexcept { if (n == 0) return 1; auto t = modpow(a, n / 2); t = t * t; if (n & 1) t = t * a; return t; } }; const int MOD = 1000000007; using mint = ModInt<MOD>; // 分割数 template<class T> struct Partition { vector<vector<T>> P; constexpr Partition(int MAX) noexcept : P(MAX+1, vector<T>(MAX+1, 0)) { for (int k = 0; k <= MAX; ++k) P[0][k] = 1; for (int n = 1; n <= MAX; ++n) { for (int k = 1; k <= MAX; ++k) { P[n][k] = P[n][k-1] + (n-k >= 0 ? P[n-k][k] : 0); } } } constexpr T get(int n, int k) { if (n < 0 || k < 0) return 0; return P[n][k]; } }; int main() { int N, S, K; cin >> N >> S >> K; ll fixed = 0; for (int i=1; i<N; i++) { fixed += K * i; } //cout << "fixed = " << fixed << endl; // **** debug **** if (fixed > S) { cout << 0 << endl; return 0; } Partition<mint> pt(S - fixed); mint ans = pt.get(S - fixed, N); cout << ans << endl; return 0; }