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

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

AtCoder ARC 071 F - Infinite Sequence (1000 点)

ダブルカウントに気をつければ難しくない。現代なら 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;
}