結果
問題 | No.42 貯金箱の溜息 |
ユーザー |
|
提出日時 | 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); | ~~~~~^~~~~~~~~~~~
ソースコード
#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)^6binom{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;}