結果
問題 | 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 long using 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; }