[ARC071F] Infinite Sequence

题目描述：

定义 \(n-\)可爱序列 指无限长的由 \(\{1,2...,n\}\) 组成的序列。同时 \(a_1,a_2...\)满足以下条件:

1.第 \(n\) 个及以后的元素是相同的，即若 \(\forall i,j\geq n,a_i=a_j\) 。

2.对于每个位置 \(i\)，紧随第 \(i\) 个元素后的 \(a_i\) 个元素是相同的，即若 \(\forall i<j<k≤i+a_i,a_j=a_k\)。

输入 \(n\)，请输出 \(n-\)可爱序列的数量 \(\bmod 10^9+7\) 。

\(n\leq{10^6}\)。

思路：

首先我们先对这个题目进行一些转换：
1. n后的每个数都应与n相同
2. 若第i位为x，则[i+1,i+x]均=x

对于一个计数类型的题目，要么选择组合，要么就是用 Dp。显然这里 Dp可能更加方便一点

我们观察一下题目中的条件，发现所有的范围都是往后延申的，所以这启发我们从后往前Dp。
令 \(dp_i\) 表示当前填到了第 \(i\) 位，其中 \(i\sim n\) 位的方案数位多少
然后我们进行分类讨论：

1. 若 \(a_i=1\& a_{i+1}\neq 1\|a_{i+1}=1\) 则 \(dp_i+=dp_{i+1}\)
2. 若 \(a_i\neq 1\& a_{i+1}\neq 1\) 则序列形如abbbbbbb，则 \(dp_i=(n-1)\times (n-1)\)
3. 若 \(a_i\neq 1\& a_{i+1}=1\) 则序列形如 a11111X，则 \(dp_i=\sum\limits_{x=2}^{n}f_{i+x+1}\)

其实是一个不错的计数，但是不能算很难的那种。

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(isdigit(c)){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
const int maxn=1e6+5;
const int mod=1e9+7;
int n;
int dp[maxn];
signed main(){
    n=read();
    dp[n]=n;
    dp[n-1]=n*n%mod;
    int sum=0;
    for(int i=n-2;i>=1;i--){
        sum=(sum+dp[i+3])%mod;
        dp[i]=(dp[i]+dp[i+1])%mod;
        dp[i]=(dp[i]+(n-1)*(n-1)%mod)%mod;
        dp[i]=(dp[i]+sum+i+1)%mod;
    }
    cout<<dp[1]<<endl;
    return 0;
}