ARC 071 F - Infinite Sequence ( DP )

F: Infinite Sequence - AtCoder Regular Contest 071 | AtCoder

題意：
問有多少無窮長度數列 A[] 滿足：
1. i 的下一個元素開始連續 A[ i ] 個皆相同
2. 對所有的 N ≤ i, j，A[ i ] = A[ j ]
輸出答案對 1e9 + 7 取模。

制約：
1≤n≤1e6
n は整数

解法：
首先可以發現，如果首項是大於 1 的數，那麼，下個數如果也大於 1，就只會有一個方案，因為形如 [ 2, 2 ] 的東西一旦產生就會必須永遠都長這個樣子。因此其實狀態是很少而且很顯然的，考慮枚舉第一項的值，並令 dp[ i ] 為剩餘長度為 i 時的答案：
A.front() = 1 : dp[ i - 1 ]
A.front() = 2 : dp[ i - 3 ] + N - 1
A.front() = 3 : dp[ i - 4 ] + N - 1
.
.
如果下一個數字決定要用 1，就會轉移到子問題的 dp，否則就是 [ 2, N ] 挑個數字數列就唯一確定了。
再考慮一下也可以知道 dp[ x ]，對於所有 x ≤ 0，都可以視作 1。
賽中只有想到這裡，然後連範測都無法過。
原因是，dp[ 1 ] 特例是 N，如果不當作邊界條件直接給這個值而是用上面的式子遞推會錯，因為 N ≤ i, j，所以後面的數字是唯一確定的。

時間 / 空間複雜度：
O( N )

#include <bits/stdc++.h>
using namespace std;
 
const int MOD = ( int ) 1e9 + 7;
const int MAXN = ( int ) 1e6;
 
int N;
int dp[ MAXN + 1 ];
int pdp[ MAXN + 1 ];
 
signed main(){
  ios::sync_with_stdio( 0 );
  cin >> N;
  pdp[ 0 ] = dp[ 0 ] = 1;
  pdp[ 1 ] = dp[ 1 ] = N;
  ++pdp[ 1 ];
  for( int i = 2; i <= N; ++i ){
    dp[ i ] = ( 1LL * pdp[ i - 1 ] - ( i - 2 >= 0 ? dp[ i - 2 ] : 0 ) + ( N - ( i - 1 ) ) ) % MOD;
    ( dp[ i ] += 1LL * ( N - 1 ) * ( N - 1 ) % MOD ) %= MOD;
    pdp[ i ] = ( pdp[ i - 1 ] + dp[ i ] ) % MOD;
  }
  if( dp[ N ] < 0 ) dp[ N ] += MOD;
  cout << dp[ N ] << endl;
  return 0;
}