【AtCoder Regular Contest 071 F】Infinite Sequence | Mrsrz's blog

动态规划。

题目大意：

给定 $n$，问有多少个不同的无限长的数列 $a$ 满足：

1. $a_n=a_{n+1}=a_{n+2}=a_{n+3}=\cdots$
2. 对于位置 $i$，任意 $i\lt j\lt k\leq i+a_i$，有 $a_j=a_k$。

题解：

如果一个位置 $i$ 填了大于 $1$ 的数，且它后面不是 $1$，则这个数列后面的数就唯一确定了。

我们令 $f_i$ 表示填完前 $i$ 个位置，后面还没确定的方案数。

这个的转移比较显然，$f_i=f_{i-1}+f_{i-3}+f_{i-4}+\cdots+f_0$（上一个非 $1$ 位置填 $k$ 就要占用 $k+1$ 的位置，上一个位置可以直接填一个 $1$）。可以用前缀和优化到 $O(n)$。

然后对每个位置，我们考虑一次性填满后面的所有格子的方案数。后面第一个位置必须填大于 $1$ 的数，之后的位置填 $2\sim n$ 是可以的，填 $1$ 则要看后面第一个位置放的数是否够大。用乘法原理计算方案数并累加即可。

如果当前是 $f_{n-1}$，则只用考虑后面一个位置。$f_n$ 没有贡献。

时间复杂度 $O(n)$。

Code：

#include<cstdio>
const int md=1e9+7;
int n,ans,f[1000005],g[1000005];
int main(){
    scanf("%d",&n);
    ans=(n-1LL)*(n-1LL)%md;
    ans+=(n>2)+1;
    f[0]=g[0]=1;
    for(int i=1;i<n;++i){
        f[i]=(f[i-1]+((i>=3)?g[i-3]:0))%md,g[i]=(g[i-1]+f[i])%md;
        if(i<n-1)ans=(ans+((n-1LL)*(n-1)+i+1+(i!=n-2))%md*f[i])%md;else
        ans=(ans+1ll*n*f[i])%md;
    }
    printf("%d",ans);
    return 0;
}