AtCoder Beginner Contest 295 D問題 Three Days Ago
問題
提出解答
問題の概要
以下を満たす文字列 を嬉しい列という.
*
のある並び替え
が存在して,
は同じ列を
回繰り返した文字列である.
数字からなる文字列 が与えられる. 以下を満たす整数の組
の数を求めよ.
の
文字目から
文字目を抜き出した文字列が嬉しい文字列である.
制約
は数字からなる長さ
以上
以下の文字列
解法
とする.
数字全体の集合を とする. つまり,
である.
ここで, 文字列 が嬉しい文字列であることと, 任意の文字
に対して,
に
が出てくる回数が偶数回であることは同値である.
これを利用する. に対して,
を
の
文字目から
文字目を抜き出した文字列において, 奇数回出てくる文字の集合とする. ここで,
は以下のようにして求めることができる.
ここで, 集合における対称差は群をなすことから, 累積和の考え方により, 次が同値になることがわかる.
の
文字目から
文字目を抜き出した文字列は嬉しい列である.
である.
よって, 次の整数の組 を求めれば良いことが分かる *1.
これにより, 正解を導くことができる. 各 に対して, [tex; E_0, \dots, E_N] に現れる
の数を
と書くことにすると, 求めるべき答えは
である.
計算量は 時間である.
*1: に対応している