結果
問題 |
No.978 Fibonacci Convolution Easy
|
ユーザー |
![]() |
提出日時 | 2020-01-31 21:38:50 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 37 ms / 2,000 ms |
コード長 | 725 bytes |
コンパイル時間 | 794 ms |
コンパイル使用メモリ | 83,528 KB |
実行使用メモリ | 34,304 KB |
最終ジャッジ日時 | 2024-09-18 20:52:00 |
合計ジャッジ時間 | 1,854 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
// I SELL YOU...! #include<iostream> #include<vector> #include<algorithm> #include<functional> #include<queue> #include<chrono> #include<iomanip> #include<map> #include<set> #define MOD 1000000007 using namespace std; using ll = long long; using P = pair<ll,ll>; void init_io(){ cin.tie(0); ios::sync_with_stdio(false); cout << setprecision(10); } signed main(){ init_io(); ll n,p,ans=0; cin >> n >> p; vector<ll> a(n+1),sum(n+2); a[0] = 0; a[1] = 1; sum[0] = 0; sum[1] = 1; for(int i=2;i<=n;i++){ a[i] = p*a[i-1] + a[i-2]; a[i] %= MOD; sum[i] = sum[i-1] + a[i]; sum[i] %= MOD; } for(int i=n-1;i>=0;i--){ ans += (sum[i]*a[i])%MOD; ans %= MOD; } cout << ans << endl; }