yukicoder No.503 - 配列コレクション

Source

ニコニコミュニティ
問題文

問題概要

全ての要素が $1$ で長さ $N$ の配列がある.
配列の長さが $K$ 以上である限り以下の操作を行う.
・配列から連続する長さ $K$ の部分列を取り除き,取り除いた場所に「取り除いた要素の積の $D$ 倍」を挿入する.
その結果としてあり得る配列全てからなる集合を $s$ とする.
\[ \sum_{a \in s} \sum_{i=1}^{|a|} a[i] \bmod 1000000007\ (10^9+7)\]の値(あり得る配列の全要素の和の和)を求める問題.

解法

操作を行うたびに配列の長さは $K-1$ だけ短くなるから,
操作の回数は $t = \left\lfloor (N-1)/(K-1) \right\rfloor$ となり,最終的な数列の長さは $r = N - t(K-1)$ となる.
まず,$D=1$ の場合は,最終的にできる配列は $\{1,1,\ldots,1\}$ しかないので,答えは $r$ である.
$D \neq 1$ の場合は,最終的にできる配列は $\{D^{p_1}, D^{p_2}, \ldots, D^{p_r}\}$ という形をしており,更に,$p_1+p_2+\cdots+p_r = t$ であれば,$p_i$ は任意の非負整数を自由に取りうる.
よって,最初の要素の和を求めて $r$ 倍すれば良く,最初の要素が $D^k$ になる場合の数は,残りの $r-1$ 要素に $D$ を $t - k$ 個振り分ける場合の数だから,$H(r-1,t-k) = C(r+t-k-2,t-k)$ と二項係数で計算される.
まとめると,$D \neq 1$ の場合の答えは,
\[ r \left( \sum_{k=0}^t D^k H(r-1, t-k) \right) \]となる.
時間計算量は $O(N)$ 程度.

cLayversion 20170505-2)のコード

C++に変換後のコードはこちら

{
  int N, K;
  mint D, res, m;
  combination_mint comb;
  int i, t, r;

  comb.init(1000100);

  rd(N,K,D);
  t = (N-1) / (K-1);
  r = N - t * (K-1);

  if(D==1){
    wt(r);
  } else {
    res = 0;
    m = 1;
    rep(i,t+1){
      res += m * comb.H(r-1, t-i);
      m *= D;
    }
    res *= r;
    wt(res);
  }
}

Current time: 2017年07月22日09時43分35秒
Last modified: 2017年05月05日06時11分25秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン: