atcoder.jp 問題概要 文字列TのABC数をT[i]=A, T[j] = B, T[k] = Cとできるi,j,k(i < j < k)の個数と定め,?にはA,B,Cのいずれかの文字で置換出来、そのような文字列全てのABC数の和を求めよ。 制約 3 <= |S| <= 1e5 Sは'A','B','C','?'で構成される 方針・所…

atcoder.jp 問題概要 N個の箱が左右一列に並んでいて、左からi番目の箱にはAi個のお菓子が入っている。連続した箱[l,r]からM人の子供に平等に配れるようにMの倍数個取り出したい時、l,rの選び方の総数を求めよ。 制約 1 <= N <= 1e5 1 <= M , Ai<= 1e9 方針…

atcoder.jp 問題概要 N人の男性、N人の女性がいる。それぞれ1~Nの番号が振られ、男性iと女性jの相性がいい1(a_i,j = 1)か悪い(a_i,j = 0)かはわかっている。N組の相性が良いペアを作る方法は何通りか？1e9 + 7で割った余りを求めよ。 方針・所感 N <= 21なの…

atcoder.jp 問題概要 長さH+1の平行な縦棒がW本与えられる。この縦棒の1,2,...Hの高さに横線を引いてあみだくじを構成する。この時、横棒は 互いに端点を共有しない それぞれの横棒の２つの端点は同じ高さになければならない 横棒は隣り合う縦線を繋がなけれ…

atcoder.jp 問題概要 整数 N が与えられます。N! (=1×2×...×N) の約数のうち、七五数 は何個あるでしょうか？ ここで、七五数とは約数をちょうど 75 個持つ正の整数です。 方針・所感 約数の個数は「素因数分解して、それぞれの指数に1を足して、全部掛け合…