結果
問題 | No.1581 Multiple Sequence |
ユーザー |
![]() |
提出日時 | 2024-08-07 22:33:59 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 951 bytes |
コンパイル時間 | 1,518 ms |
コンパイル使用メモリ | 126,824 KB |
実行使用メモリ | 82,664 KB |
最終ジャッジ日時 | 2024-08-07 22:34:13 |
合計ジャッジ時間 | 11,942 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 2 |
other | WA * 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);}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 = 0;for(int i = 1;i<=m;i++) ans += calc(m,i);cout<<ans.val()<<endl;}