保存されている過去のバージョンの一覧

2017年05月05日06時11分25秒
2017年05月05日06時08分44秒

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)$ 程度．

cLay（version 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: 2024年04月17日01時57分08秒
Last modified: 2017年05月05日06時11分25秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン：