結果

問題 No.42 貯金箱の溜息
ユーザー Ryuhei Mori
提出日時 2020-04-10 01:21:53
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 13 ms / 5,000 ms
コード長 2,418 bytes
コンパイル時間 886 ms
コンパイル使用メモリ 50,816 KB
最終ジャッジ日時 2025-01-09 15:36:01
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 3
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:60:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   60 |   scanf("%d", &t);
      |   ~~~~~^~~~~~~~~~
main.cpp:64:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   64 |     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
*/
constexpr int mod = 1000000009;
void mul5(std::vector<int> &P){
P.push_back(0); P.push_back(0);
P.push_back(0); P.push_back(0);
for(int i = P.size()-1; i >= 5; i--) P[i] -= P[i-5];
for(std::size_t i = 1; i < P.size(); i++) P[i] += P[i-1];
// for(int i = P.size()-1; i >= 4; i--) P[i] += P[i-1]+P[i-2]+P[i-3]+P[i-4];
}
void mul(std::vector<int> &P){
P.push_back(0);
for(int i = P.size()-1; i > 0; i--) P[i] += P[i-1];
}
int binom5(long long int k){
return k * (k - 1) % mod * (k - 2) % mod * (k - 3) % mod * (k - 4) % mod;
}
void print(std::vector<int> &P){
for(int x: P) printf("%d ", x);
puts("");
}
int main(){
int t;
scanf("%d", &t);
while(t--){
long long int m;
std::vector<int> P;
scanf("%lld", &m);
m /= 5;
if(m&1) P.push_back(2);
else P.push_back(1), P.push_back(1);
// print(P);
m /= 2;
mul5(P);
mul5(P);
mul5(P);
std::size_t i;
for(i = 0; 5*i+(m%5) < P.size(); i++) P[i] = P[5*i + (m%5)];
P.resize(i);
// print(P);
m /= 5;
mul(P);
mul(P);
mul(P);
mul(P);
for(i = 0; 2*i+(m%2) < P.size(); i++) P[i] = P[2*i + (m%2)];
P.resize(i);
// print(P);
m /= 2;
mul5(P);
mul5(P);
mul5(P);
mul5(P);
mul5(P);
for(i = 0; 5*i+(m%5) < P.size(); i++) P[i] = P[5*i + (m%5)];
P.resize(i);
// print(P);
m /= 5;
long long int r = 0;
for(i = 0; i < P.size(); i++) r += (long long) binom5((m+5-i)%mod) * P[i];
printf("%d\n", (int) (r % mod * 591666672 % mod));
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0