包除原理
操作によってできるものの個数を数え上げる系の問題の最も基本的な問題！ 問題へのリンク 問題概要 長さ の文字列 が与えられる。以下の操作を 1 回行ってできる文字列が何種類あるかを求めよ。 を満たす を好きなように選んで、 の 文字目と 文字目を swap …
包除原理した！ 問題へのリンク 問題概要 1 以上 以下の正整数 であって、ある正整数 と 2 以上の正整数 を用いて と表現できるものはいくつありますか？ 制約 考えたこと まず考えたのは、 は素数のみ考えれば良いということだった。たとえば、 というよう…
包除原理の基本！ 問題へのリンク 問題概要 1 以上 以下の整数のうち、 のいずれかで割り切れるものの個数を求めよ。 制約 考えたこと 包除原理の超典型問題。たとえば のときは、次のように考えればよい。 (V[0] で割り切れる個数) + (V[1] で割り切れる個…
共通テスト数学 IA にも似た問題が出ていた！ 問題へのリンク 問題概要 頂点数が のサイクルグラフが与えられる。このグラフの各頂点を色 のいずれかの色で塗る。 どの隣接する頂点対も異なる色で塗られるようにする方法の個数を 998244353 で割った余りを求…
コンテスト後に解いた。こっちの方が解きやすかった。 問題へのリンク 問題概要 制約 考えたこと 最初は の指数を気にするのかな......などと考えていたが、考えていくうちに の値など、ただの飾りであることがわかってきた。 まず、問題の条件を言い換える…
コンテスト終了から 8 秒後の AC で泣いた。でも、分割統治 FFT が自力で書けてよかった。想定解法は FPS だった。 問題へのリンク 問題概要 次の問題がある。 の順列 と が与えられる。 これらをもとに次のように、頂点数 、辺数 の有向グラフを作る。 頂点…
モノグサ社内で同僚と一緒に解いた！ 問題へのリンク 問題概要 要素からなる数列 が与えられる。各 に対して次の問に答えよ。 先手と後手が交互にプレイする。整数 を管理する。最初 である。 先手は初手は を選び、 と に更新し、数列からその整数は削除す…
メビウス関数を用いた約数系包除原理を使いこなそう！ 問題へのリンク 問題概要 (表現改) 文字 '.' と '#' のみからなる長さ の文字列 が与えられる。今、文字 '#' をいくつか '.' に書き換えることによって、文字列 が周期的文字列となるようにしたい。 な…
FPS による考察はやっぱり強力ですね！ 問題へのリンク 問題概要 長さ かつ総和 である非負整数列 のうち、以下の条件を満たすものの個数を 998244353 で割ったあまりを求めよ。 「以下の操作のうちどちらかを選んで行うことを繰り返して、 の全ての要素を 0…
包除原理を学べる問題！ 問題へのリンク 問題概要 個の文字列 が与えられます。次の手順によって作れる長さ の文字列の個数を 998244353 で割ったあまりを求めてください。 のいずれかを選ぶ 文字列 に含まれる文字のみを使って、長さ の文字列を作る 制約 …
面白かった！！ より一般化した問題 (グラフの頂点集合の任意の部分集合に対して、それらを連結にする辺の選び方の数え上げ) を考えた方が考えやすいね。 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフ が与えられます。 の辺集合の部分集合 ( 通…
これが ABC の C 問題だったとは...！！！ 典型90問の問 4 が結構近いと思った。 drken1215.hatenablog.com 問題へのリンク 問題概要 のグリッド (メモリにおさまらない規模) が与えられる。そのうちの 個のマスには飴が置いてある。 次の条件を満たすマスの…
約数系包除原理の教育的問題 問題へのリンク 問題概要 整数 が与えられるので、以下の条件を満たす整数 の組の個数を求めてください。 としたとき、, , 制約 解法 (1)：約数系包除 まさに約数系包除原理の教育的良問。この問題をきっかけとして、次の記事を…
間に合わなかった！！！悔しい！！！ 問題へのリンク 問題概要 長さ の数列 が与えられます。以下の条件を満たすような、長さ の数列 の個数を 998244353 で割ったあまりを答えよ。 制約 考えたこと という条件は扱いづらいので、包除原理でやると良さそう。…
「横移動 + 縦移動」で行けるところをすべて求めるのは簡単だし、「縦移動 + 横移動」で行けるところをすべて求めるのも簡単。しかし、両方の方法で行けるマスの扱いが難しい。 問題へのリンク 問題概要 のグリッドがあり、そのうちの 個のマスは壁になって…
面白かった。単純にやると なので、そこから計算量オーダーを 1 つ落とすことを考える。 ジャッジページへのリンク 問題文へのリンク 問題概要 のグリッドが与えられる。各マスには 0, 1, 2 のうちのいずれかの値が描かれている。 これらの 個のマスのうちの…
この回の前の回の LCMs といい、約数系包除がこの時期流行ってたのかな。 問題へのリンク 問題概要 整数 が与えられる。 以上 以下のすべての整数 に対し、 に以下の操作を繰り返すことによって次に に戻るまでの操作回数 (戻らない場合 0) を足し合わせた値…
こういう数え上げ、大好きすぎる！！！ 問題へのリンク 問題概要 長さ の数列 がある。初期状態ではすべての値が 0 となっている。この数列に以下の操作をちょうど 回行って得られる数列が何通りあるか、998244353 で割ったあまりを求めよ。 となる を選んで…
添字 GCD 畳み込みの練習問題！ 問題へのリンク 問題概要 長さ の正整数列が 個ある。 各数列から高々 1 個ずつ整数を抜き取って得られる数列は 通り考えられる。そのうち抜き取られた数値が 2 個以上あるようなものすべてについての、「それらの数値の最大…
りんごさんセット！！！ 問題へのリンク 問題概要 次元空間において () を満たす部分の体積を とすると は整数値となる。この整数値を 1000000007 で割ったあまりを求めよ。 制約 考えたこと 最初は色々迷走していた。三次元の場合を考えていて思っていたの…
形式的冪級数の pow で通せた！ 問題へのリンク editorial 問題概要 個の箱それぞれに正しい括弧列を入れる。ただし、次の2つの条件をともに満たすように入れる必要がある。 個の箱に含まれる '(' の個数の合計が 長さが である括弧列はどの箱にも入れてはな…
ずっと前にこれを作問して出題していたので記録を。 時は流れて AGC 026 D - Histogram Coloring でよく似た設定の問題が出たときはビックリした (実際はそんなに似てない)。 問題へのリンク 問題概要 のグリッドが与えられる。各マスは '0', '1', '?' のい…
このセットの writer をしていました 問題へのリンク 問題概要 を並び替えてできる数列 は 通りあるが、そのうち以下の条件を満たすものが何通りあるかを、1000000007 で割ったあまりを求めよ。 を満たすような がちょうど 個 を満たすような がちょうど 個 …
頭整理するのが大変だった 問題へのリンク editorial 問題概要 個の格子点 (、、) がある。 これらの格子点を以下のルールに則って 色 () で塗る。 点 の、 とのマンハッタン距離が であるとき 点 を、色 % で塗る 各 について、その色で塗られた格子点が何…
包除原理！！！C 問題としては難しめですね。 問題へのリンク 問題概要 0 以上 9 以下の整数値からなる長さ の数列 であって、 数列中に 0 が含まれる 数列中に 9 が含まれる という条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。 制約 考え…
落ち着いて頭を整理。。。 問題へのリンク 問題概要 'R', 'G', 'B' のみからなる長さ の文字列 が与えられる。 の index の組 であって、 と と はすべて互いに異なる である という条件を満たすものの個数を求めよ。 制約 考えたこと 頭がごっちゃになりそ…
面白かった 問題へのリンク 問題概要 の盤面の各マスを T, M, N, P の四色に塗る方法のうち、以下の条件を満たすものが何通りあるか、1000000007 で割ったあまりを求めよ。 どの T マスと M マスについても、M マスは T マスから見て strict に右にあるか、s…
座標圧縮をがんばる 問題へのリンク 問題概要 個の区間 が与えられる。それぞれの区間から一様ランダムに整数を選んでいく。 これが広義単調減少となる確率を求め、それを 998244353 で割ったあまりの形式で求めよ。 制約 考えたこと 区間の幅は大きいが、 …
すごく面白かった！！！！！！！ 問題へのリンク 問題概要 長さ のマス目があって、長さがそれぞれ の 個の区間を配置していきたい。 個の区間がすべてのマスを被覆するような配置方法は何通りあるか、1000000007 で割ったあまりを求めよ。 制約 考えたこと …
包除原理をとても素朴な状態で問いかける問題！！！ 問題へのリンク 問題概要 頂点のツリーが与えられる。ツリーの各辺を白色または黒色に塗る 通りの方法のうち、以下の 個の制約をすべて満たすものの個数を求めよ。 個目の制約は 2 頂点 が指定され、 と …
