結果
問題 |
No.269 見栄っ張りの募金活動
|
ユーザー |
![]() |
提出日時 | 2019-08-25 17:27:58 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,750 ms / 5,000 ms |
コード長 | 2,439 bytes |
コンパイル時間 | 981 ms |
コンパイル使用メモリ | 104,780 KB |
実行使用メモリ | 19,456 KB |
最終ジャッジ日時 | 2024-11-06 20:15:04 |
合計ジャッジ時間 | 7,967 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
#include <iostream> // cin, cout, cerr, clog #include <algorithm> // minmax, sort, swap #include <numeric> // iota, accumulate, inner_product #include <cstdio> // printf, scanf #include <climits> // INT_MIN, LLONG_MIN #include <cmath> // long, trig, pow #include <string> // string, stoi, to_string #include <vector> // vector #include <queue> // queue, priority_queue #include <deque> // deque #include <stack> // stack #include <map> // key-value pairs sorted by keys #include <set> // set #include <unordered_map> // hashed by keys #include <unordered_set> // hashed by keys #include <iomanip> // cout<<setprecision(n) #include <functional> // std::function<void(int)> #define rep(i,n) for(int i = 0; i < (n); i++) #define ENDL '\n' #define print(i) std::cout << (i) << '\n' #define int long long // at least int64 > 9*10^18 #define all(v) (v).begin(), (v).end() #define dump2(v) for(auto i:v) { for(auto j:i) std::cout << j << ' '; std::cout << "\n"; } constexpr int MOD = 1e9+7; struct mint { int v; mint():v(0){} mint(int v):v((v+MOD)%MOD){} mint operator-()const{ return mint(0) - *this;} mint& operator+=(const mint& a){ if((v+=a.v)>=MOD) v-=MOD; return *this;} mint& operator-=(const mint& a){ if((v+=MOD-a.v)>=MOD) v-=MOD; return *this;} mint& operator*=(const mint& a){ (v*=a.v)%=MOD; return *this;} mint& operator/=(const mint& a){ (*this) *= a.inv(); return *this;} mint operator+(const mint& a)const{ return mint(*this) += a;} mint operator-(const mint& a)const{ return mint(*this) -= a;} mint operator*(const mint& a)const{ return mint(*this) *= a;} mint operator/(const mint& a)const{ return mint(*this) /= a;} bool operator<(const mint& a)const{ return v < a.v;} bool operator==(const mint& a)const{ return v == a.v;} mint pow(int k)const{mint r(1),t(v);while(k){if(k&1)r*=t;t*=t;k>>=1;} return r;} mint inv()const{return pow(MOD-2);} }; std::istream& operator>>(std::istream&i,mint&a){int t;i>>t;a=mint(t);return i;} std::ostream& operator<<(std::ostream&o,const mint&a){o<<a.v;return o;} signed main() { std::ios_base::sync_with_stdio(0); std::cin.tie(0); int n,s,k; std::cin >> n >> s >> k; s -= k*(n-1)*n/2; if(s<0) { print(0); return 0; } std::vector<std::vector<mint> > dp(n+1,std::vector<mint>(s+1,0)); dp[0][0] = 1; rep(i,n) { rep(j,s+1) { int c = 0; while(j+(n-i)*c<=s) { dp[i+1][j+(n-i)*c] += dp[i][j]; c++; } } } print(dp[n][s]); return 0; }