結果

問題 No.269 見栄っ張りの募金活動
ユーザー yasunori
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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; // ab
return true;
}
return false;
}
template <typename T>
bool chmax(T &a, const T& b) {
if (a < b) {
a = b; // ab
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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0