ダブルカウントに気をつければ難しくない。現代なら 700 点かもしれない...
問題概要
正の整数 が与えられる。
以上 以下の整数からなる無限数列 のうち
- 任意の について であるとき、 から連続する 個は同じ値である
を満たすものの個数を 1000000007 で割ったあまりを求めよ。
制約
考えたこと
1 箇所でも 以外の数値が連続したら、そこを とするとそこから先はずっと が続くことになる。
なので数列は
- (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; }