結果

問題 No.42 貯金箱の溜息
ユーザー Ryuhei Mori
提出日時 2020-04-10 03:20:37
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 7 ms / 5,000 ms
コード長 2,165 bytes
コンパイル時間 527 ms
コンパイル使用メモリ 48,640 KB
最終ジャッジ日時 2025-01-09 15:36:06
ジャッジサーバーID
（参考情報） 		judge1 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:68:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   68 |   scanf("%d", &t);
      |   ~~~~~^~~~~~~~~~
main.cpp:72:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   72 |     scanf("%lld", &m);
      |     ~~~~~^~~~~~~~~~~~

ソースコード

diff # 

#include <cstdio>
#include <vector>

/*
[q^m] 1/(1-q)(1-q^5)(1-q^10)(1-q^50)(1-q^100)(1-q^500)
[q^m] (1+q+q^2+q^3+q^4)/(1-q^5)^2(1-q^10)(1-q^50)(1-q^100)(1-q^500)
[q^{m/5}] 1/(1-q)^2(1-q^2)(1-q^10)(1-q^20)(1-q^100)
[q^m] (1+q)^2/(1-q^2)^3(1-q^10)(1-q^20)(1-q^100)


If m is odd
[q^{m}] 2q /(1-q^2)^3(1-q^10)(1-q^20)(1-q^100)
[q^{m/2}] 2 /(1-q)^3(1-q^5)(1-q^10)(1-q^50)
If m is even
[q^{m}] (1+q^2) /(1-q^2)^3(1-q^10)(1-q^20)(1-q^100)
[q^{m/2}] (1+q) /(1-q)^3(1-q^5)(1-q^10)(1-q^50)

[q^{m}] P(q)/(1-q)^3(1-q^5)(1-q^10)(1-q^50)
[q^{m}] P(q)(1+q+q^2+q^3+q^4)^3/(1-q^5)^4(1-q^10)(1-q^50)

[q^{m}] P(q)/(1-q)^4(1-q^2)(1-q^10)
[q^{m}] P(q)(1+q)^4/(1-q^2)^5(1-q^10)

[q^{m}] P(q)/(1-q)^5(1-q^5)
[q^{m}] P(q)(1+q+2^2+q^3+q^4)^5/(1-q^5)^6

[q^{m}] P(q)/(1-q)^6

binom{i+5}{5}

[q^m] (1+q+...+q^499)(1+q^5+...+q^495)(1+q^10+...+q^490)(1+q^50+...+1+q^450)(1+q^100+...+q^400)/(1-q^500)^6

[q^{m}] P(q) /(1-q)^3(1-q^5)(1-q^10)(1-q^50)
[q^{m}] P(q)(1+q+q^2+...+q^49)^3(1+q^5+...+q^45)(1+q^10+...+q^40) /(1-q^50)^6
*/

constexpr int mod = 1000000009;


void mul(std::vector<long long int> &P, int a){
  for(std::size_t i = a; i < P.size(); i++) P[i] += P[i-a];
}

int binom5(long long int k){
  return k * (k - 1) % mod * (k - 2) % mod * (k - 3) % mod * (k - 4) % mod;
}

void print(std::vector<long long int> &P){
  for(long long int x: P) printf("%lld ", x);
  puts("");
}

int main(){
  std::vector<long long int> P(49*3 + 45 + 40 + 2);
  P[0] = 1;
  P[50] = mod-5;
  P[100] = 10;
  P[150] = mod-10;
  P[200] = 5;
//  P[250] = mod-1;
  mul(P, 1);
  mul(P, 1);
  mul(P, 1);
  mul(P, 5);
  mul(P, 10);
  for(long long int &x: P) x %= mod;
  int t;
  scanf("%d", &t);
// print(P);
  while(t--){
    long long int m;
    scanf("%lld", &m);
    m /= 5;
    long long int r = 0;
    if(m&1){
      m /= 2;
      for(std::size_t i = m % 50; i < P.size() && i <= m; i+=50) r += (long long) binom5(((m-i)/50+5)%mod) * P[i];
      r += r;
    }
    else {
      m /= 2;
      for(std::size_t i = m % 50; i < P.size() && i <= m; i+=50) r += (long long) binom5(((m-i)/50+5)%mod) * (P[i] + (i ? P[i-1] : 0));
    }
    printf("%d\n", (int) (r % mod * 591666672 % mod));
  }

  return 0;
}
0