原题大意

给定n，有多少个长度为无穷的数列{a}满足：

对于n < k，ak = an
对于i < j < k <= i + ai，aj = ak
1 <= ai <= n，n <= 10^6，对10^9 + 7取摸

算法分析

http://blog.csdn.net/crzbulabula/article/details/70145999

其中第二种情况的第三点k较大时，就是说如果(1+k)长度超过n时，后位只能补一，相当于给第二种情况的第一点里，k>i-3时的补充。

程序代码

#include <cstdio>
#include <cstring>
using namespace std;
const int mod = 1e9+7;
const int maxn = 1e6+5;
typedef long long ll;
int f[maxn];

int up(int a,int b){
    a+=b;
    if(a>=mod) a-=mod;
    return a;
}

int mul(ll  a, ll  b){
    return ((a%mod) *(b%mod)) % mod;
}

int main(){
    int n;
    int sum = 0;
    scanf("%d", &n);
    f[1] = n;f[2] = mul(n,n);

    for(int i = 3; i <= n; i++){
        f[i] = up(f[i-1],sum);
        f[i] = up(f[i],mul(n-1,n-1));
        f[i] = up(f[i],n-i+2);
        sum = up(sum,f[i-2]);
    }
    printf("%d\n", f[n]);
    return 0;
}