結果
問題 | No.1581 Multiple Sequence |
ユーザー |
![]() |
提出日時 | 2024-08-07 22:35:01 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,155 ms / 2,000 ms |
コード長 | 914 bytes |
コンパイル時間 | 1,432 ms |
コンパイル使用メモリ | 127,600 KB |
実行使用メモリ | 77,676 KB |
最終ジャッジ日時 | 2024-08-07 22:35:20 |
合計ジャッジ時間 | 15,380 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#include<iostream>#include<vector>#include<algorithm>using namespace std;using ll = long long;#include<atcoder/modint>using mint = atcoder::modint1000000007;#include<unordered_map>#include<map>const int M = 1<<17;vector<map<int,mint>> memo(M+1);vector<vector<int>> facs(M+1);mint calc(int res,int can){if(res%can!=0) return 0;if(res==0) return 1;if(memo[res].find(can)!=memo[res].end()) return memo[res][can];mint tmp = 0;tmp += calc(res-can,can);for(auto&j:facs[res]) {if(j%can!=0) continue;if(j==can) continue;tmp += calc(res-j,j);}return memo[res][can] = tmp;};int main(){cin.tie(nullptr);ios::sync_with_stdio(false);int m;cin>>m;for(int i = 2;i<=m;i++){for(int j = i;j<=m;j+=i){facs[j].push_back(i);}}mint ans = calc(m,1);cout<<ans.val()<<endl;}