ダブルカウントに気をつければ難しくない。現代なら 700 点かもしれない...

問題概要

正の整数 $N$ が与えられる。
$1$ 以上 $N$ 以下の整数からなる無限数列 $a$ のうち

任意の $i$ について $k = a_i$ であるとき、 $a_{i+1}$ から連続する $k$ 個は同じ値である
$a_{n} = a_{n+1} = a_{n+2} = \dots$

を満たすものの個数を 1000000007 で割ったあまりを求めよ。

制約

$1 \le n \le 10^{6}$

考えたこと

1 箇所でも $1$ 以外の数値が連続したら、そこを $b, c$ とするとそこから先はずっと $c$ が続くことになる。

なので数列は

(1)
(211)
(3111)
(41111)
...

から構成されたものの最後に (bcccccccc...) をくっ付けたようなものになる。

dp[ i ] := 最初の i 個で (1)(211)(3111)... で構成する場合の数

とする。注意点として、最初の n-1 個のうち最後の部分に

(a11111...1)

を持って行ったときに n-1 個を超えてしまうものをダブルカウントしないようにする。これは超えてしまう前の、最後の 1 の位置で場合分けすることにした。

#include <iostream>
using namespace std;

const int MOD = 1000000007;
long long dp[1100000], sum[1100000];

int main () {
    long long n; cin >> n;
    dp[0] = 1; sum[1] = 1;
    dp[1] = 1; sum[2] = 2;
    for (long long i = 2; i < n; ++i) {
        dp[i] = (dp[i-1] + sum[i-2]) % MOD;
        sum[i+1] = sum[i] + dp[i];
    }
    long long res = 0;
    for (long long i = 0; i < n; ++i) {
        if (i <= n-3) res += dp[i] * (n * (n-2) % MOD+i+3) % MOD;
        else if (i == n-2) res += dp[i] * n % MOD * (n-1) % MOD;
        else if (i == n-1) res += dp[i] * n % MOD;
        res %= MOD;
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ARC 071 F - Infinite Sequence (黄色, 1000 点)

問題概要

制約

考えたこと