結果
問題 | No.269 見栄っ張りの募金活動 |
ユーザー |
|
提出日時 | 2020-09-22 18:54:56 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 20 ms / 5,000 ms |
コード長 | 2,865 bytes |
コンパイル時間 | 1,734 ms |
コンパイル使用メモリ | 171,284 KB |
実行使用メモリ | 19,712 KB |
最終ジャッジ日時 | 2024-06-26 08:46:57 |
合計ジャッジ時間 | 2,744 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
// 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 N_MAX, int K_MAX) noexcept : P(N_MAX + 1, vector<T>(K_MAX + 1, 0)) {for (int k = 0; k <= K_MAX; k++) P[0][k] = 1;for (int n = 1; n <= N_MAX; n++) {for (int k = 1; k <= 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, N);mint ans = pt.get(S - fixed, N);cout << ans << endl;return 0;}