結果
| 問題 | No.42 貯金箱の溜息 |
| ユーザー |
 ferin
|
| 提出日時 | 2019-08-11 07:39:09 |
| 言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 41 ms / 5,000 ms |
| コード長 | 8,238 bytes |
| コンパイル時間 | 2,111 ms |
| コンパイル使用メモリ | 185,324 KB |
| 実行使用メモリ | 4,380 KB |
| 最終ジャッジ日時 | 2023-09-29 01:23:01 |
| 合計ジャッジ時間 | 2,904 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 22 ms
4,376 KB |
| testcase_01 | AC | 36 ms
4,380 KB |
| testcase_02 | AC | 41 ms
4,376 KB |
コンパイルメッセージ
次のファイルから読み込み: /usr/local/gcc7/include/c++/12.2.0/x86_64-pc-linux-gnu/bits/c++allocator.h:33,
次から読み込み: /usr/local/gcc7/include/c++/12.2.0/bits/allocator.h:46,
次から読み込み: /usr/local/gcc7/include/c++/12.2.0/string:41,
次から読み込み: /usr/local/gcc7/include/c++/12.2.0/bits/locale_classes.h:40,
次から読み込み: /usr/local/gcc7/include/c++/12.2.0/bits/ios_base.h:41,
次から読み込み: /usr/local/gcc7/include/c++/12.2.0/ios:42,
次から読み込み: /usr/local/gcc7/include/c++/12.2.0/istream:38,
次から読み込み: /usr/local/gcc7/include/c++/12.2.0/sstream:38,
次から読み込み: /usr/local/gcc7/include/c++/12.2.0/complex:45,
次から読み込み: /usr/local/gcc7/include/c++/12.2.0/ccomplex:39,
次から読み込み: /usr/local/gcc7/include/c++/12.2.0/x86_64-pc-linux-gnu/bits/stdc++.h:54,
次から読み込み: main.cpp:1:
メンバ関数 ‘_Tp* std::__new_allocator<_Tp>::allocate(size_type, const void*) [with _Tp = std::vector<modint<1000000009> >]’ 内,
inlined from ‘static _Tp* std::allocator_traits<std::allocator<_CharT> >::allocate(allocator_type&, size_type) [with _Tp = std::vector<modint<1000000009> >]’ at /usr/local/gcc7/include/c++/12.2.0/bits/alloc_traits.h:464:28,
inlined from ‘std::_Vector_base<_Tp, _Alloc>::pointer std::_Vector_base<_Tp, _Alloc>::_M_allocate(std::size_t) [with _Tp = std::vector<modint<1000000009> >; _Alloc = std::allocator<std::vector<modint<1000000009> > >]’ at /usr/local/gcc7/include/c++/12.2.0/bits/stl_vector.h:378:33,
inlined from ‘void std::_Vector_base<_Tp, _Alloc>::_M_create_storage(std::size_t) [with _Tp = std::vector<modint<1000000009> >; _Alloc = std::allocator<std::vector<modint<1000000009> > >]’ at /usr/local/gcc7/include/c++/12.2.0/bits/stl_vector.h:395:44,
inlined from ‘std::_Vector_base<_Tp, _Alloc>::_Vector_bas
ソースコード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a) {
out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
out<<'[';
for(const T &i: a) out<<i<<',';
out<<']';
return out;
}
template<class T>
ostream &operator <<(ostream& out, const set<T>& a) {
out<<'{';
for(const T &i: a) out<<i<<',';
out<<'}';
return out;
}
template<class T, class S>
ostream &operator <<(ostream& out, const map<T,S>& a) {
out<<'{';
for(auto &i: a) out<<i<<',';
out<<'}';
return out;
}
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000009;
template<ll MOD>
struct modint {
ll x;
modint(): x(0) {}
modint(ll y) : x(y>=0 ? y%MOD : y%MOD+MOD) {}
static constexpr ll mod() { return MOD; }
// e乗
modint pow(ll e) {
ll a = 1, p = x;
while(e > 0) {
if(e%2 == 0) {p = (p*p) % MOD; e /= 2;}
else {a = (a*p) % MOD; e--;}
}
return modint(a);
}
modint inv() const {
ll a=x, b=MOD, u=1, y=1, v=0, z=0;
while(a) {
ll q = b/a;
swap(z -= q*u, u);
swap(y -= q*v, v);
swap(b -= q*a, a);
}
return z;
}
// Comparators
bool operator <(modint b) { return x < b.x; }
bool operator >(modint b) { return x > b.x; }
bool operator<=(modint b) { return x <= b.x; }
bool operator>=(modint b) { return x >= b.x; }
bool operator!=(modint b) { return x != b.x; }
bool operator==(modint b) { return x == b.x; }
// Basic Operations
modint operator+(modint r) const { return modint(*this) += r; }
modint operator-(modint r) const { return modint(*this) -= r; }
modint operator*(modint r) const { return modint(*this) *= r; }
modint operator/(modint r) const { return modint(*this) /= r; }
modint &operator+=(modint r) {
if((x += r.x) >= MOD) x -= MOD;
return *this;
}
modint &operator-=(modint r) {
if((x -= r.x) < 0) x += MOD;
return *this;
}
modint &operator*=(modint r) {
#if !defined(_WIN32) || defined(_WIN64)
x = x * r.x % MOD; return *this;
#endif
unsigned long long y = x * r.x;
unsigned xh = (unsigned) (y >> 32), xl = (unsigned) y, d, m;
asm(
"divl %4; \n\t"
: "=a" (d), "=d" (m)
: "d" (xh), "a" (xl), "r" (MOD)
);
x = m;
return *this;
}
modint &operator/=(modint r) { return *this *= r.inv(); }
// increment, decrement
modint operator++() { x++; return *this; }
modint operator++(signed) { modint t = *this; x++; return t; }
modint operator--() { x--; return *this; }
modint operator--(signed) { modint t = *this; x--; return t; }
};
using mint = modint<1000000009>;
template<class T> mint operator*(T l, mint r) { return mint(l) *= r; }
template<class T> mint operator+(T l, mint r) { return mint(l) += r; }
template<class T> mint operator-(T l, mint r) { return mint(l) -= r; }
template<class T> mint operator/(T l, mint r) { return mint(l) /= r; }
template<class T> bool operator==(T l, mint r) { return mint(l) == r; }
template<class T> bool operator!=(T l, mint r) { return mint(l) != r; }
// Input/Output
ostream &operator<<(ostream& os, mint a) { return os << a.x; }
istream &operator>>(istream& is, mint &a) { return is >> a.x; }
string to_frac(mint v) {
static map<ll, PII> mp;
if(mp.empty()) {
mp[0] = mp[mint::mod()] = {0, 1};
FOR(i, 2, 1001) FOR(j, 1, i) if(__gcd(i, j) == 1) {
mp[(mint(i) / j).x] = {i, j};
}
}
auto itr = mp.lower_bound(v.x);
if(itr != mp.begin() && v.x - prev(itr)->first < itr->first - v.x) --itr;
string ret = to_string(itr->second.first + itr->second.second * ((int)v.x - itr->first));
if(itr->second.second > 1) {
ret += '/';
ret += to_string(itr->second.second);
}
return ret;
}
// x座標が相異なるn+1点(x_i,y_i)を通るn次以下の多項式f(T)の値を返す
// x_i = a + i*d 0<=i<=n (等差数列)
// O(nlog(MOD))
mint lagrange_interpolation_arithmetic(mint a, mint d, vector<mint> y, mint T) {
const ll n = y.size() - 1;
vector<mint> c(n+1);
// f_0(x_0)
mint f = 1;
FOR(i, 1, n+1) f *= a - (a+i*d);
c[0] = y[0] / f;
// f_i(x_i) → f_{i+1}(x_{i+1})
REP(i, n) {
f *= d*(i+1);
f /= d*(i-n);
c[i+1] = y[i+1] / f;
}
// f(T)
mint ret = 0, ft = 1;
REP(i, n+1) ft *= T-(a+i*d);
REP(i, n+1) ret += c[i] * ft / (T-(a+i*d));
return ret;
}
// x座標が相異なるn+1点(x_i,y_i)を通るn次以下の多項式f(T)の値を返す
// O(n^2)
mint lagrange_interpolation(vector<mint> x, vector<mint> y, mint T) {
const ll n = x.size() - 1;
vector<mint> c(n+1);
REP(i, n+1) {
mint t = 1; // f_i(x_i)
REP(j, n+1) {
if(i == j) continue;
t *= x[i]-x[j];
}
c[i] = y[i] / t;
}
// f(T)
mint ret = 0, ft = 1;
REP(i, n+1) ft *= T-x[i];
REP(i, n+1) ret += c[i] * ft / (T-x[i]);
return ret;
}
// x座標が相異なるn+1点(x_i,y_i)を通るn次以下の多項式f(x)を返す
// O(n^2)
vector<mint> lagrange_interpolation(vector<mint> x, vector<mint> y) {
const ll n = x.size() - 1;
vector<mint> c(n+1);
REP(i, n+1) {
mint t = 1; // f_i(x_i) を求める
REP(j, n+1) {
if(i == j) continue;
t *= x[i]-x[j];
}
c[i] = y[i] / t;
}
// dpを計算
vector<vector<mint>> dp(n+1, vector<mint>(n+2));
dp[0][0] = -1 * x[0], dp[0][1] = 1;
FOR(i, 1, n+1) REP(j, n+2) {
dp[i][j] = dp[i-1][j] * -1 * x[i];
if(j >= 1) dp[i][j] += dp[i-1][j-1];
}
vector<mint> xinv(n+1);
REP(i, n+1) xinv[i] = x[i].inv();
vector<mint> ret(n+1); // f(x)
REP(i, n+1) {
if(c[i]==0) continue;
// 0割り対策の場合分け
if(x[i] == 0) {
REP(j, n+1) ret[j] += dp[n][j+1] * c[i];
} else {
ret[0] -= dp[n][0] * xinv[i] * c[i];
mint pre = -1 * dp[n][0] * xinv[i];
FOR(j, 1, n+1) {
ret[j] -= (dp[n][j] - pre) * xinv[i] * c[i];
pre = -1 * (dp[n][j] - pre) * xinv[i];
}
}
}
return ret;
}
namespace yukicoder42 {
void solve() {
vector<ll> c({1, 5, 10, 50, 100, 500});
vector<mint> dp(3010, 1);
FOR(i, 1, 6) FOR(j, c[i], 3010) dp[j] += dp[j-c[i]];
ll t;
cin >> t;
while(t--) {
ll M;
cin >> M;
if(M < 3010) {
cout << dp[M] << endl;
continue;
}
mint m = M/500;
ll q = M % 500;
vector<mint> x(6), y(6);
REP(i, 6) {
x[i] = i;
y[i] = dp[i*500+q];
}
cout << lagrange_interpolation(x, y, m) << endl;
}
}
}
signed main(void)
{
cin.tie(0);
ios::sync_with_stdio(false);
yukicoder42::solve();
return 0;
}