题目描述：
定义 \(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\) 位的方案数位多少
然后我们进行分类讨论：
- 若 \(a_i=1\& a_{i+1}\neq 1\|a_{i+1}=1\) 则 \(dp_i+=dp_{i+1}\)
- 若 \(a_i\neq 1\& a_{i+1}\neq 1\) 则序列形如
abbbbbbb，则 \(dp_i=(n-1)\times (n-1)\) - 若 \(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;
}