けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

包除原理:2^K個の足し引き

数学アルゴ本 068 - Number of Multiples 2 (1Q)

包除原理の基本! 問題へのリンク 問題概要 1 以上 以下の整数のうち、 のいずれかで割り切れるものの個数を求めよ。 制約 考えたこと 包除原理の超典型問題。たとえば のときは、次のように考えればよい。 (V[0] で割り切れる個数) + (V[1] で割り切れる個…

AtCoder ABC 246 F - typewriter (1D, 青色, 500 点)

包除原理を学べる問題! 問題へのリンク 問題概要 個の文字列 が与えられます。次の手順によって作れる長さ の文字列の個数を 998244353 で割ったあまりを求めてください。 のいずれかを選ぶ 文字列 に含まれる文字のみを使って、長さ の文字列を作る 制約 …