結果

問題 No.41 貯金箱の溜息（EASY）
コンテスト
ユーザー yuppe19 😺
提出日時 2015-10-22 11:15:54
言語 C++11(old_compat)
(gcc 12.4.0 + boost 1.89.0)
コンパイル:
g++-12 -O2 -lm -std=gnu++11 -Wuninitialized -DONLINE_JUDGE -include bits/stdc++.h -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 2,191 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,154 ms
コンパイル使用メモリ 169,992 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2026-03-08 16:03:54
合計ジャッジ時間 1,539 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:45:15: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   45 |   int t; scanf("%d", &t);
      |          ~~~~~^~~~~~~~~~
main.cpp:47:17: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   47 |     i64 m; scanf("%lld", &m);
      |            ~~~~~^~~~~~~~~~~~

ソースコード

diff #
raw source code 

#include <iostream>
#include <algorithm>
using namespace std;
using i64 = long long;

class range {private: struct I{int x;int operator*(){return x;}bool operator!=(I& lhs){return x<lhs.x;}void operator++(){++x;}};I i,n;
public:range(int n):i({0}),n({n}){}range(int i,int n):i({i}),n({n}){}I& begin(){return i;}I& end(){return n;}};

template <int mod>
struct Modint {
  long long x;
  Modint(void) : Modint(0) {};
  Modint(long long x) : x((x%mod+mod)%mod) {};
  Modint operator + (const Modint a)    { return Modint(*this) += a; }
  Modint operator - (const Modint a)    { return Modint(*this) -= a; }
  Modint operator * (const Modint a)    { return Modint(*this) *= a; }
  Modint operator * (const long long a) { return Modint(*this) *= Modint(a); }
  Modint operator +=(const Modint& a)   { if((x+=a.x)>=mod) { x-=mod; } return *this; }
  Modint operator -=(const Modint& a)   { if((x-=a.x)<0) { x+=mod; } return *this; }
  Modint operator *=(const Modint& a)   { (x*=a.x)%=mod; return *this; }
  Modint operator *=(const long long a) { (x*=a)%=mod; return *this; }
  /* a++ */ Modint operator ++(int)     { Modint old; old.x = x; if((x+=1)>=mod) { x-=mod; }; return old; }
  /* ++a */ Modint operator ++(void)    { *this += 1; return *this; }
  /* a-- */ Modint operator --(int)     { Modint old; old.x = x; if((x-=1)<0) { x+=mod; }; return old; }
  /* --a */ Modint operator --(void)    { *this -= 1; return *this; }
  bool operator ==(const Modint& a) const   { return x == a.x; }
  bool operator ==(const long long a) const { return x == Modint(a); }
  bool operator !=(const Modint& a) const   { return !(x == a.x); }
  bool operator !=(const long long a) const { return !(x == Modint(a)); }
  int intvalue(void) const { return (int)x; }
};
const int mod = 1000000009;
using modint = Modint<mod>;

const int MAX = pow(10, 10) / 111111;
vector<modint> dp;

int main(void) {
  dp.assign(MAX, 1);
  for(int v : range(1, 10)) {
    for(int cost : range(v, MAX)) {
      dp[cost] += dp[cost-v];
    }
  }
  int t; scanf("%d", &t);
  for(int cases : range(t)) {
    i64 m; scanf("%lld", &m);
    m /= 111111;
    modint res = dp[m];
    printf("%d\n", res.intvalue());
  }
  return 0;
}
0