コンテスト終了から 8 秒後の AC で泣いた。でも、分割統治 FFT が自力で書けてよかった。想定解法は FPS だった。 問題へのリンク 問題概要 次の問題がある。 の順列 と が与えられる。 これらをもとに次のように、頂点数 、辺数 の有向グラフを作る。 頂点…

「TDPC T - フィボナッチ」の亜種とも言える問題ですね。 問題へのリンク 問題概要 () によって定義される数列を考える。 整数 が与えられので、 AND を満たすすべての非負整数 に対する の総和を 998244353 で割った余りを求めよ。 制約 考えたこと この問…

Boston--Mori 法を履修した！ 問題へのリンク 問題概要 () によって定義される数列において、 を 1000000007 で割ったあまりを求めよ。 制約 解法 0-indexed にして考えることにする。つまり、 () によって定義される数列において、 を求めることにする。 こ…

この平方分割のやり方はちゃんとマスターしたい 問題へのリンク 問題概要 種類のレベル 1 の宝石がある。各種類のレベル 1 の宝石は無限個ある。 個の宝石を合成することで、レベル の宝石を作ることができる。ただし、その 個の宝石は次の条件を満たす必要…

オンライン分割統治 FFT 面白いね！！ 公式解説がとても丁寧なので、備忘録程度に 問題へのリンク 問題概要 頂点数 のが与えられます。 組の頂点対に対して、次のように無向辺を張っていきます。 組めの頂点対に対しては 長さ 1 の辺が 本 長さ 2 の辺が 本 …

コンテスト中にアダマール変換を思い出せたのはよかった！ 問題へのリンク 問題概要 整数 と 個の整数 が与えられます。次の条件を満たすような Nim をすべて考えます。 山の個数は のいずれかである 各山の石の個数は のいずれかである このような Nim の盤…

(x - a)(x - b) ... (x - z) みたいなやつの計算 問題へのリンク 問題概要 個の箱がある。箱 には色 のボールが入っている。以下の 個のクエリに答えよ。 各クエリは 以下の整数 が与えられる 各箱から 個ずつボールを取り出す方法であって、取り出されたボ…

めちゃ好きだけど、実装重い 問題へのリンク 問題概要 頂点の重み付き無向完全グラフが与えられる。各 に対して、 頂点集合を 個の互いに disjoint な集合に分割する方法であって どの同族辺 (両端点が同一のグループに属する辺) の重みも、どの異族辺 (両端…

こういうのは包除原理しかない！ 問題へのリンク 問題概要 人の人がいる。 人 の身長は である。以下の条件を満たすように、 組のペアを作る方法は何通りあるか、998,244,353 で割ったあまりを求めよ。 どの人もちょうど一つのペアに含まれる。 どのペアも、…

確かに、えでゅふぉのラス問にありそう！ 問題へのリンク 問題概要 人の選手が距離 のレースを走る。 人目はデフォルトでは距離 1 走るのに 秒かかる。 スタートから距離が のところにアイテムがある。各アイテムは各選手に対して独立に、確率 で減速 (距離 …

NTT と聞いて 問題へのリンク 問題概要 偶数 が与えられる。 十進法表記で () しか登場しない 桁の整数のうち、 前半 桁の各位の和 後半 桁の各位の和 が等しいものが何通りあるか、998244353 で割ったあまりで答えよ。leading zero は OK。 制約 考えたこと…

きたまさ法によく似たタイプの DP ダブリング高速化！ ただかなり難しい問題だと思うので、004 まで順調に解いていた方が、この問題で挫折しないように注意！！！ 無理に解こうとせずに飛ばすのも一案だと思います...... 問題へのリンク editorial 問題概要 …