結果
問題 |
No.269 見栄っ張りの募金活動
|
ユーザー |
![]() |
提出日時 | 2023-03-01 05:30:16 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 31 ms / 5,000 ms |
コード長 | 871 bytes |
コンパイル時間 | 4,030 ms |
コンパイル使用メモリ | 250,904 KB |
最終ジャッジ日時 | 2025-02-11 00:28:11 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; using ll=int; using ld=long double; ld pie=3.14159265359; ll inf=80010010; ll mod=1000000007; template<class T> struct Partition { vector<vector<T> > P; constexpr Partition(int MAX) noexcept : P(MAX, vector<T>(101, 0)) { for (int k = 0; k < 101; ++k) P[0][k] = 1; for (int n = 1; n < MAX; ++n) { for (int k = 1; k < 101; ++k) { P[n][k] = (P[n][k-1] + (n-k >= 0 ? P[n-k][k] : 0))%mod; } } } constexpr T get(int n, int k) { if (n < 0 || k < 0) return 0; return P[n][k]; } }; int main(){ ll n,k,s; cin >> n >> s >> k; s-=((n*(n-1))/2)*k; if (s<0) { cout << 0 << endl; return 0; } Partition<ll>pt(s+1); cout << pt.get(s,n) << endl; }