ARC071F Infinite Sequence

Link
若存在两个不为(1)且相邻的数，那么后面的数都会相等。
那么设(f_i)表示填([i,n])位置的方案数，边界为(f_n=n,f_{n-1}=n^2)。
考虑如何进行转移。
( ext{1:})填一个(x(xin(1,n-i]))然后后面接(x)个(1)，即(f_ileftarrowsumlimits_{j=i+3}^n f_j)。
( ext{2:})填一个(x(xin(n-i,n]))然后后面接(n-i)个(1)，即(f_ileftarrow i+1)。
( ext{3:})只填一个(1)，即(f_ileftarrow f_{i+1})。
( ext{4:})在第(i)和(i+1)位填两个大于(1)的数，即(f_ileftarrow(n-1)^2)。
最后的答案就是(f_1)。

#include<cstdio>
int n,f[1000007],P=1000000007;
int main()
{
    scanf("%d",&n),f[n]=n,f[n-1]=1ll*n*n%P;
    for(int i=n-2,s=0;i>0;--i) (s+=f[i+3])%=P,f[i]=(f[i+1]+1ll*(n-1)*(n-1)+s+i+1)%P;
    printf("%d",f[1]);
}