ARC071D Infinite Sequence

传送门

仔细观察可以发现,如果在一个\(> 1\)的数后面放一个\(> 1\)的数,那么后面的序列也就确定了,所以我们考虑dp出特定长度的序列,然后在后面加上能确定序列的数来贡献答案

为了凑出这样的序列,用来填充的东西是单个的\(1\),或者长度为\(x+1(x>1)\)的 \(x\)加\(x\)个\(1\),所以转移就是\(f_i=\sum_{j=0}^{i-1}[j\ne i-2]f_j\),注意不能加上\(f_{i-2}\),因为\(1\ 1\)会和\(1\)加\(1\)算重

然后考虑\(f_i\)的贡献,如果\(i<n-1\),首先可以加上\(xyyyy...(x>1,y>1)\),然后也可以加上\(x11111(x>1\)且\(i+x+1\ge n)\),因为凑到n时后面就全是\(1\)了;如果\(i=n-1\),那么n号位放什么,后面就是什么,所以可以放一个\([1,n]\)的数

渣渣灰代码警告

#include<bits/stdc++.h>

#define LL long long

#define db double

#define il inline

#define re register

#define mkpr make_pair

using namespace std;

const int N=1e6+10,mod=1e9+7;

il LL rd()

{

    LL x=0,w=1;char ch=0;

    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

    return x*w;

}

int n,m,f[N],ans;

int main()

{

    n=rd();

    m=(1ll*(n-1)*(n-1))%mod;

    ans=m+1+(n>2);  //整个序列可以是xyyyy,也可以是n11111或者(n-1)11111

    int sm=f[0]=1;

    for(int i=1;i<n;++i)

    {

        f[i]=sm;

        if(i-2>=0) f[i]=(f[i]-f[i-2]+mod)%mod;

        sm=(sm+f[i])%mod;

        if(i!=n-1) ans=(ans+1ll*f[i]*(m+min(i+2,n-1))%mod)%mod; //乘的东西代表的分别是xyyyy和x1111

        else ans=(ans+1ll*f[i]*n%mod)%mod;

    }

    printf("%d\n",ans);

    return 0;

}