結果

問題 No.41 貯金箱の溜息（EASY）
コンテスト
ユーザー yuppe19 😺
提出日時 2015-10-22 11:15:54
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,191 bytes
コンパイル時間 349 ms
コンパイル使用メモリ 51,216 KB
最終ジャッジ日時 2024-11-14 19:20:34
合計ジャッジ時間 864 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:35:17: error: ‘pow’ was not declared in this scope
   35 | const int MAX = pow(10, 10) / 111111;
      |                 ^~~
main.cpp:36:1: error: ‘vector’ does not name a type
   36 | vector<modint> dp;
      | ^~~~~~
main.cpp: In function ‘int main()’:
main.cpp:39:3: error: ‘dp’ was not declared in this scope
   39 |   dp.assign(MAX, 1);
      |   ^~
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