結果
問題 | No.1331 Moving Penguin |
ユーザー |
|
提出日時 | 2021-01-08 22:29:02 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 463 ms / 1,500 ms |
コード長 | 508 bytes |
コンパイル時間 | 1,772 ms |
コンパイル使用メモリ | 172,636 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-07 14:50:50 |
合計ジャッジ時間 | 19,599 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 49 |
ソースコード
#include<bits/stdc++.h>#define int long longusing namespace std;const int mod=1000000007;signed main(){int N;cin>>N;int S=sqrt(N);vector<int>dp(N);dp[0]=1;vector<vector<int>>A(S,vector<int>(S));for(int i=0;i<N-1;i++){int a;cin>>a;if(a<S){A[a][i%a]=(dp[i]+A[a][i%a])%mod;}else{for(int j=i+a;j<N;j+=a)dp[j]=(dp[j]+dp[i])%mod;}if(a!=1)dp[i+1]=(dp[i+1]+dp[i])%mod;for(int j=1;j<S;j++)dp[i+1]=(dp[i+1]+A[j][(i+1)%j])%mod;}cout<<dp[N-1]<<endl;}