题解：AT_arc071_d [ARC071F] Infinite Sequence

lkjzyd20 · 2024-08-22 09:49:57 · 题解

题意

让你构造一个每个数为 1 \sim n 的正整数无限长的序列，满足：

第 n 项及之后的所有项都相等
对于每一个 a_i，满足 a_{i+1} \sim a_{i+a_i} 个数都相同。

问你有多少种方案 \bmod\ 10^9+7。

思路

看到问方案，首先想到 dp。

那么设 f_i 表示对于每一位 a\in[1,n] 有多少种方案，则可以得到

f_i=f_{i-1}+(n-1+f_{i-3})+(n-1+f{i-4}) \cdots +(n-1+f_{i-n-1})

加上前缀和优化一下之后的式子就变成了

f_i=f_i-1+sum_{i-3}+n^2-n-i+2

其中 f_1=n,f_2=n^2，sum 数组用来求 f 数组的前缀和，需要预处理一下，注意 \bmod 10^9+7。

综上所述，时间负责度为 O(n)。

代码如下

#include <bits/stdc++.h>
#define int long long
using namespace std;
#define rep(i, l, r) for(int i = l; i <= r; ++ i)
#define per(i, r, l) for(int i = r; i >= l; -- i)
const int N = 1e6 + 10, mod = 1e9 + 7;
int f[N], sum[N], n;
main() 
{
    scanf("%lld", &n);
    f[0] = 1; f[1] = n; f[2] = (n * n) % mod;
    sum[0] = 1;
    sum[1] = (f[0] + f[1]) % mod;
    sum[2] = ((f[0] + f[1]) % mod + f[2]) %mod;
    rep(i, 3, n) 
    {
        f[i] = ((f[i - 1] + sum[i - 3]) % mod + n * (n - 1) - i + 2) % mod;
        sum[i] = (sum[i - 1] + f[i]) % mod;
    }
    printf("%lld", f[n] % mod);
    return 0;
}