[ARC071F] Infinite Sequence

に言及
各数1~nの無限長のシーケンスを構築し、以下を満たすようにします.

のn番目の数は、その後の数と同じ

です.

は、各数xについて、後のxの数と同じである.

何種類の案があるか聞いてください.
問題解
dpを考慮して、f[i]f[i]f[i]f[i]がi~n番目のビットを表すシナリオ数とし、dpを逆さにする.
転送は3つのケースに分けられます.
i位が1の場合、f[i]+=f[i+1]f[i]+=f[i+1]f[i]+=f[i+1]となる.
このシーケンスは、i番目が1である、i+1番目が1でない場合には、x y y y y y y y y y y y y y y y y y y y y yにしか成長する.xyyyyyyyyyyyy... xyyyyyyyyyyyy...のように、x x xとy y yは任意の非1数を埋めることができるので、f[i]+=(n-1)∗(n-1)f[i]+=(n-1)*(n-1)f[i]+=(n-1)∗(n-1)である.
i番目のビットが1ではないがi+1番目のビットが1である場合、このシーケンスはx 11111 S x 1111 S x 1111 Sのように成長するので、x x x毎にf[i]+=f[i+x+1]f[i]+=f[i+x+1]f[i]+=f[i+x+1]f[i]+=f[i+x+1]f[i+x+1>n i+x+1>nである場合、f[i+x+1]=1 f[i+x+1]=1 f[i+x+1]=1f fの接尾辞の和を1つ維持すればO(1)O(1)O(1)遷移が可能になる.
時間複雑度:O(n)O(n)O(n)O(n).
コード:

#include 
using namespace std;

#define MAXN 1000010
#define mod 1000000007

int n,f[MAXN],add;

int main()
{
    scanf("%d",&n);
    f[n]=n;
    f[n-1]=(long long)n*n%mod;
    for(int i=n-2;i>=1;--i)
    {
        add=(add+f[i+3])%mod;
        f[i]=f[i+1];
        f[i]=(f[i]+(long long)(n-1)*(n-1)%mod)%mod;
        f[i]=(f[i]+add)%mod;
        f[i]=(f[i]+i+1)%mod;
    }
    printf("%d
",f[1]);
}