結果
問題 | No.1581 Multiple Sequence |
ユーザー | shiomusubi496 |
提出日時 | 2021-07-02 22:26:09 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 705 ms / 2,000 ms |
コード長 | 876 bytes |
コンパイル時間 | 2,252 ms |
コンパイル使用メモリ | 212,832 KB |
実行使用メモリ | 116,772 KB |
最終ジャッジ日時 | 2023-09-11 22:39:51 |
合計ジャッジ時間 | 11,629 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 546 ms
95,816 KB |
testcase_03 | AC | 602 ms
103,748 KB |
testcase_04 | AC | 161 ms
35,204 KB |
testcase_05 | AC | 638 ms
107,660 KB |
testcase_06 | AC | 270 ms
54,468 KB |
testcase_07 | AC | 144 ms
33,676 KB |
testcase_08 | AC | 203 ms
43,716 KB |
testcase_09 | AC | 560 ms
99,080 KB |
testcase_10 | AC | 356 ms
69,116 KB |
testcase_11 | AC | 72 ms
19,588 KB |
testcase_12 | AC | 226 ms
47,144 KB |
testcase_13 | AC | 8 ms
5,260 KB |
testcase_14 | AC | 630 ms
104,560 KB |
testcase_15 | AC | 423 ms
79,016 KB |
testcase_16 | AC | 91 ms
23,368 KB |
testcase_17 | AC | 673 ms
113,724 KB |
testcase_18 | AC | 57 ms
16,848 KB |
testcase_19 | AC | 523 ms
93,276 KB |
testcase_20 | AC | 540 ms
96,676 KB |
testcase_21 | AC | 602 ms
103,568 KB |
testcase_22 | AC | 324 ms
63,636 KB |
testcase_23 | AC | 705 ms
116,772 KB |
ソースコード
#include<bits/stdc++.h> #define int long long using namespace std; constexpr int mod=1000000007; signed main(){ int M; cin>>M; vector<vector<int>> Y(M+1); for(int i=1;i<=M;i++){ for(int j=i;j<=M;j+=i)Y[j].push_back(i); } Y[0]=vector<int>(M); for(int i=0;i<M;i++)Y[0][i]=i+1; reverse(Y.begin(),Y.end()); vector<map<int,int>>Z(M+1); for(int i=0;i<=M;i++){ for(int j=0;j<Y[i].size();j++)Z[i][Y[i][j]]=j; } vector<vector<int>> dp(M+1); for(int i=0;i<=M;i++)dp[i].resize(Y[i].size()); dp[0][0]=1; for(int i=0;i<M;i++){ int K=Y[i].size(); for(int j=K-1;j>=0;j--){ for(int k:Y[M-Y[i][j]]){ if(Y[i][j]!=k)(dp[i][j]+=dp[i][Z[i][k]])%=mod; } } for(int j=0;j<K;j++){ (dp[i+Y[i][j]][Z[i+Y[i][j]][Y[i][j]]]+=dp[i][j])%=mod; } } int ans=0; for(int i=0;i<M;i++)(ans+=dp[M][i])%=mod; cout<<ans<<endl; }