AtCoder

Luogu

分析

发现,如果两个不为 $1$ 的数连在一起,那么后面的所有数必须相等。

设 $f[i]$ 表示 $i\sim n$ 有多少种填法。

容易得到 $f[n]=1,f[n-1]=n^2$ 。

考虑一下怎么转移。

  • 填一个大于 $1$ 的数

此时后面会有连续的若干个 $1$ ,于是得到这一部分的方案数是 $\sum\limits_{j=i+3}^nf[j]$ 。显然可以后缀和优化一波。

然后,还有 $i+a_i>n$ 的情况,于是还要多加上 $i+1$ 。

  • 填上连续两个大于 $1$ 的数

由上面的性质可知,这一部分的方案数是 $(n-1)^2$ 。

  • 填上一个 $1$

显然方案数为 $f[i+1]$ 。

最终答案为 $f[1]$ 。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000000+10;
const int mod=1e9+7;

int f[N];

int main() {
    int n=read();
    f[n]=n,f[n-1]=1ll*n*n%mod;
    for (re int i=n-2,s=0;i>=1;--i) {
        s=(s+f[i+3])%mod;
        f[i]=(s+i+1+1ll*(n-1)*(n-1)%mod+f[i+1])%mod;
    }
    printf("%d\n",f[1]);
    return 0;
}
最后修改:2019 年 09 月 25 日 01 : 22 PM