結果
問題 | No.269 見栄っ張りの募金活動 |
ユーザー |
|
提出日時 | 2024-04-02 23:07:57 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 7,296 bytes |
コンパイル時間 | 2,238 ms |
コンパイル使用メモリ | 204,372 KB |
最終ジャッジ日時 | 2025-02-20 19:42:47 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 4 TLE * 1 -- * 17 |
ソースコード
#include <bits/stdc++.h>using namespace std;template <typename T> using min_priority_queue = priority_queue<T,vector<T>,greater<T>>;template<typename T>void outvec(vector<T> &v){bool b = false;for(auto i : v){if(b) cout << " ";else b = true;cout << i;}cout << endl;}template<typename T>void invec(vector<T> &v){for(auto &i : v){cin >> i;}}template <typename T>bool chmin(T &a, const T& b) {if (a > b) {a = b; // aをbで更新return true;}return false;}template <typename T>bool chmax(T &a, const T& b) {if (a < b) {a = b; // aをbで更新return true;}return false;}template <typename T>T exEuclid(T a, T b, T &x, T &y){T d = a;if(b != 0){d = exEuclid(b, a%b, y, x);y -= (a/b)*x;}else{x = 1;y = 0;}//cout << a << " * " << x << " + " << b << " * " << y << " = " << d << endl;return d;}int64_t mod;struct modint{int64_t n;int64_t p;modint(){n = 0;p = mod;}modint(int64_t a){if(a <= -mod) a %= mod;else if(a >= mod) a %= mod;if(a < 0) a += mod;n = a;p = mod;}modint(int64_t a, int64_t q){if(a <= -q) a %= q;else if(a >= q) a %= q;if(a < 0) a += q;n = a;p = q;}modint pow(int64_t a){if(a <= 1-p) a %= p-1;else if(a >= p-1) a %= p-1;if(a < 0) a += p-1;modint rtn;if(n == 0) {rtn.n = 0;return rtn;}if(n == 1) {rtn.n = 1;return rtn;}if(a == 0) {rtn.n = 1;return rtn;}if(a == 1) {rtn.n = n;return rtn;}int64_t b = a/2;int64_t c = a%2;rtn = pow(b);rtn *= rtn;if(c){rtn *= modint(n);}return rtn;}bool operator==(modint other){return n == other.n && p == other.p;}bool operator!=(modint other){return !(n == other.n && p == other.p);}modint operator+(modint other){modint rtn(n+other.n, p);return rtn;}modint operator-(modint other){modint rtn(n-other.n, p);return rtn;}modint operator*(modint other){modint rtn(n*other.n, p);return rtn;}modint operator/(modint other){int64_t x, y, d;d = exEuclid(other.n, p, x, y);int64_t rtn = x*n;if(d > 1) rtn /= d;return modint(rtn);}void operator+=(modint other){n += other.n;if(n >= p) n %= p;}void operator-=(modint other){n -= other.n;if(n < 0) n += p;}void operator*=(modint other){n *= other.n;if(n >= p) n %= p;}void operator/=(modint other){int64_t x, y, d;d = exEuclid(other.n, p, x, y);n *= x;if(d > 1) n /= d;if(n <= p || p <= n) n %= p;if(n < 0) n += p;return;}void operator++(){n++;if(n == p) n = 0;return;}void operator--(){n--;if(n == -1) n = p-1;return;}};vector<modint> fact_mod_v;vector<modint> inv_fact_mod_v;modint comb_mod(int64_t n, int64_t m){if(n < 0 || m < 0 || m > n) return 0;modint rtn = fact_mod_v[n]*inv_fact_mod_v[m]*inv_fact_mod_v[n-m];return rtn;}modint comb_mod_small(int64_t n, int64_t m){if(m < mod){return comb_mod(n%mod, m);}return comb_mod_small(n/mod, m/mod)*comb_mod(n%mod, m%mod);}void init_fact(int64_t n){fact_mod_v.resize(n+1,0);inv_fact_mod_v.resize(n+1,0);for(int64_t i = 0; i <= n; i++){if(i == 0){fact_mod_v[i] = modint(1);}else{fact_mod_v[i] = modint(i*fact_mod_v[i-1].n);}//cout << i << endl;}for(int64_t i = min(n, mod-1); i >= 0; i--){if(i == min(n, mod-1)){inv_fact_mod_v[i] = modint(fact_mod_v[i]).pow(-1);}else{inv_fact_mod_v[i] = modint(inv_fact_mod_v[i+1].n*(i+1));}//cout << i << endl;}}template <typename T>struct monoid_plus{T val;monoid_plus(){;}monoid_plus(T x){val = x;}monoid_plus e(){return monoid_plus(0);}monoid_plus operator*(monoid_plus other){return monoid_plus(val + other.val);}};template <typename monoid>struct segtree{int sz;vector<monoid> dat;segtree(){;}segtree(int n){sz = 1;while(sz <= n) sz *= 2;dat.resize(2*sz-1, monoid().e());}void update(int k, monoid a){k += sz-1;dat[k] = a;while(k > 0){k = (k-1)/2;dat[k] = dat[2*k+1]*dat[2*k+2];}}void plus(int k, monoid a){update(k, get(k, k+1)*a);}//[a,b)monoid get(int a, int b){return sub_get(a, b, 0, 0, sz);}monoid sub_get(int a, int b, int k, int l, int r){if(r <= a || b <= l) return monoid().e();if(a <= l && r <= b) return dat[k];monoid vl = sub_get(a, b, 2*k+1, l, (l+r)/2);monoid vr = sub_get(a, b, 2*k+2, (l+r)/2, r);return vl*vr;}};void yn(bool b){if(b) cout << "Yes" << endl;else cout << "No" << endl;}bool debug;bool randomInput;bool debugOutput;int numOfTestCase;using ans_type = int;void input(){if(numOfTestCase > 1){;}if(randomInput){}else{}return;}void output_input(){;}ans_type calc(){mod = 1'000'000'007;int N, S, K;cin >> N >> S >> K;int M = S - N * (N - 1) / 2 * K;if(M < 0){cout << 0 << endl;return 0;}vector<vector<modint>> dp(N+1, vector<modint>(M+1, 0));dp[0][0] = 1;for(int i = 0; i < N; i++){for(int j = 0; j <= M; j++){for(int k = 0; j+k <= M; k += N-i){dp[i+1][j+k] += dp[i][j];}}}cout << dp[N][M].n << endl;/*for(auto i : dp){for(auto j : i){cout << j.n << " ";}cout << endl;}*/return ans_type();}ans_type calc_simple(){return ans_type();}void output(ans_type ans){return;}int main(){debug = 0;randomInput = 0;debugOutput = 0;numOfTestCase = 1;srand(time(NULL));cout << fixed << setprecision(12);if(numOfTestCase == 0) cin >> numOfTestCase;if(debug){for(int i = 0; i < numOfTestCase; i++){input();ans_type ans = calc();ans_type ansSimple = calc_simple();if(ans != ansSimple){output_input();output(ans);output(ansSimple);}}}else{for(int i = 0; i < numOfTestCase; i++){input();output(calc());}}return 0;}