AT274の技術だったりなかったり

あっとのTECH LOG

競プロのこととか技術のこととか。たまに日常を書きます。

2020-04-13から1日間の記事一覧

ABC162 E - Sum of gcd of Tuples (Hard)

問題原文 atcoder.jp 問題要旨 1以上 以下の整数からなる長さ の数列 を考える。 考えうる数列 通り全てについて、 を計算し、その総和を求めよ。 解法 まともには到底計算できないので、 「gcdが になるようなものは何通りあるか?」 を考える。 まずgcdが…

ABC162 D - RGB Triplets

問題原文 atcoder.jp 問題要旨 R, G, B のみからなる長さ の文字列 が与えられる。 であって、 , , が全て異なり、 であるようなものの通り数を求めよ。 解法 全体からカウントしてはいけないものを取り除く 方針を取る。 まず答え全体は明らかに、 (Rの数) …