Processing math: 0%
\def\bra#1{\mathinner{\left\langle{#1}\right|}} \def\ket#1{\mathinner{\left|{#1}\right\rangle}} \def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}}

◇◇ref010:CODE FESTIVAL 2018 qual A - C : 半分◇◇


☆問題URL

https://beta.atcoder.jp/contests/code-festival-2018-quala/tasks/code_festival_2018_quala_c

☆問題の概要

長さNの整数列が与えられる。「整数のうち1つを選んで2で割る(小数点以下切捨て)」という操作をK回行って得られる可能性がある数列の数を10^9+7で割ったあまりを求めよ。

☆解法

まず、i番目の数について何回2で割ると0になるかを表した数列を作る。これらの和は最大でも3000程度なので、K\geq 4000であれば4000くらいにしておいていい(答えが変わらないため)。

DPテーブルを DP[i][j][flag]=i{\rm 番目の数までで}j{\rm 回操作をしたときに作れる数列の数} とする。ただし、flag=0は操作後の数列に1つも0が含まれていないことを、flag=1は操作後の数列に0が含まれていることを表す。ここで、0に対してはそれ以上操作しないものとする(実際には可能であるが)。

数列に0が含まれていない場合はK回ちょうどの操作で作れる数列の数を見なくてはいけないが、数列に0が1つでもあればその0に対して操作をし続けることでいくらでも本質的な操作回数を減らすことができる。よって、求める答えは DP[N][K][0]+\sum_{k=0}^K DP[N][k][1] となる。

☆反省

まさかDPとは。

戻る