CF 785 D - Anton and School - 2
問題
問題概要
(と)のみで構成される文字列について、次のような長さの文字列を
regular simple bracket sequences(RSBS)と呼ぶことにする：
- 空文字列ではない(
)
は偶数で、前半の
文字は全て
(、後半の)
例えば((()))はRSBSで、())や(()())はRSBSではない。
今、(と)のみで構成される文字列が与えられる。
からいくつかの文字を削除してRSBSを作成したいと思う時、その方法は何通りあるか、
で割った余りを答えよ。
アイデア
要するに、の部分文字列の中でRSBSの個数を求めたい。まず、自分で考えたこととしては
を先頭から走査していってその時点で左にある
(の合計(個とする)と右にある
)の合計(個とする)がわかっていれば、現在注目している箇所の
(を必ず採用すると仮定してで組み合わせの総数を列挙できるなーとは思った。けれど、それを全ての
(に対してやるのは間に合わない。
実は、1箇所の(に注目して、それより左にある(の個数が個でそれより右にある
)の個数が個の時のRSBSの構成方法の場合の数はもっと簡単に計算できる。
シンプルな場合として、前半文字が
(で後半文字が
)のような文字列からRSBSを構成することを考えると、この場合は通りになる。なぜこうなるかを、
個の1と
個0を並べる順列に対応付けて考える。
以下に例を示す：
s: ((()))) select: ( ( )) convert: 0100110
元の文字列がであるときに、このように部分文字列を構成すると、01はこのように対応させる。これは具体的に何をやっているかというと、部分文字列として採用された
(に0、されない(に1、採用された)に1、されない)に0を付与している。この方法によって、0は個、1は
個になる。
採用された(が個とすると、採用された
)も個。つまり採用されない
)は個。ということで、0は合計で
個になる。前から順番に括弧を対応させていくことで一対一にこの文字列が定まるというわけである。
実際に走査していく時は、一番右にある(は必ず採用する仮定があるので、01の対応で言うと0が1つ減ることになる。よって、通りになる。
あとは、はじめに)の数を数えておいて、操作しながら減らしていき、combinationを計算すれば良い。combinationは階乗を事前に計算して、繰り返し二乗法を利用すれば逆元も計算できる。
実装(C++)
続きを読むCF 740 D - Alyona and a tree
問題
問題概要
頂点数の木があり、各頂点には
から
までの番号が振られている。根の頂点番号は
である。各頂点はそれぞれ整数
を持っている。
また、辺には重みがあり、本の辺の情報について、
個目の情報は頂点
と
を結んでおり、その重みは
である。
いま、頂点が頂点
を
controlしているということを次のように定義する：
- 頂点
は
を根とする部分木に含まれる
各頂点に対して、その頂点が
controlしている頂点の個数を求めよ。
アイデア
controlの条件に関して、と
の距離で定義されているが、今回のグラフは木なので任意の頂点間の距離は根からの距離を利用することで計算できる。根からの各頂点への距離を
とすると、
controlの定義からは
よりも根から離れていることになるので2番目の条件は
となり、更に変数を揃えるために変形すると
ということになる。
さて、ここでを固定して考えてみる。
としてあり得るのは根からの
へのパス上にある頂点ということになる。根をスタート地点として
は単調増加するので、初めて条件を満たす位置
から
の手前までの区間がこの条件を満たすのでこの区間に+1すればいいということになる。
まず、初めて条件を満たす位置を探すためには、各頂点からの親をダブリングして保存しておけば二分探索によって探すことが可能になる。
そして、このような区間へのaddはimos法での親の頂点に+1,
の親の頂点に-1をしておいて最後に子から親へ足し上げれば答えを出すことが出来る。
