高速畳み込み計算
Polynomial Taylor Shift が使えた！ 問題へのリンク 問題概要 頂点数 の木が与えられる。各 に対して、次の問いに答えよ。 頂点から 個の頂点を選ぶ 通りの方法それぞれについて その 個の頂点をすべて含む連結な部分グラフのサイズとして考えられる最小値…
面白かった！ 問題へのリンク 問題概要 整数係数の多項式 と、整数定数 が与えられる。 を展開したときの各係数を 998244353 で割った余りを求めよ。 制約 考えたこと Polynomial Taylor Shift については、次の記事に詳しく書いた。計算量は となる。 drken…
Polynomial Taylor Shift を履修したので、簡単にまとめてみます。例によって、Yosupo Library Checker の 問題 を通します。 なお、Polynomial Taylor Shift の解法は、単なるライブラリ整備の一環とみなすというよりは、その導出過程をぜひ押さえておきた…
本当に ACL の convolution をそのまま試してほしいという問題ですね。 問題へのリンク 問題概要 整数列 と、整数列 が与えられる。 によって定義される整数列 を求めよ。 制約 解法 とにかく、ACL のドキュメントにそのままの式が書いてある！ https://atco…
この平方分割のやり方はちゃんとマスターしたい 問題へのリンク 問題概要 種類のレベル 1 の宝石がある。各種類のレベル 1 の宝石は無限個ある。 個の宝石を合成することで、レベル の宝石を作ることができる。ただし、その 個の宝石は次の条件を満たす必要…
面白かった！！ より一般化した問題 (グラフの頂点集合の任意の部分集合に対して、それらを連結にする辺の選び方の数え上げ) を考えた方が考えやすいね。 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフ が与えられます。 の辺集合の部分集合 ( 通…
コンテスト中にアダマール変換を思い出せたのはよかった！ 問題へのリンク 問題概要 整数 と 個の整数 が与えられます。次の条件を満たすような Nim をすべて考えます。 山の個数は のいずれかである 各山の石の個数は のいずれかである このような Nim の盤…
添字 GCD 畳み込みの練習問題！ 問題へのリンク 問題概要 長さ の正整数列が 個ある。 各数列から高々 1 個ずつ整数を抜き取って得られる数列は 通り考えられる。そのうち抜き取られた数値が 2 個以上あるようなものすべてについての、「それらの数値の最大…
添字 GCD convolution が一躍話題になった問題だった気がする 問題へのリンク 問題概要 長さ の整数列 がある。 の値を 998244353 で割ったあまりを求めよ。 制約 考えたこと 個の値のうちのすべてのペアに対するなにかの総和を求める問題では を満たす につ…
原始根 + NTT 問題へのリンク 問題概要 素数 と、数列 、 が与えられる。 各整数 に対して、 の値を 998244353 で割ったあまりを求めよ。 制約 考えたこと 添字積 convolution はできるのかと一瞬戸惑う。しかし が素数であることに着目すると、原始根 を介…
AGC っぽくない気がするけど、好き 問題へのリンク 問題概要 とする (素数である)。 個の非負整数 が与えられる。 の値を求めよ。 制約 考えたこと 「和を で割ったあまり」ではなく、「 で割ったあまりの和」であることに注意。それでも、とりあえず以下の…
から落とせる気がまったくしなかった... 問題へのリンク 問題概要 個の広義単調増加数列 が与えられる。 それぞれの数列から、先頭から 個ずつとってきた値の総和の最大値を求めよ。ただし でなければならないものとする。 制約 考えたこと 個数に関する con…
(x - a)(x - b) ... (x - z) みたいなやつの計算 問題へのリンク 問題概要 個の箱がある。箱 には色 のボールが入っている。以下の 個のクエリに答えよ。 各クエリは 以下の整数 が与えられる 各箱から 個ずつボールを取り出す方法であって、取り出されたボ…
形式的冪級数すごい 問題へのリンク 問題概要 個の整数 が与えられる。各 に対して を 998244353 で割ったあまりを求めよ。 制約 考えたこと いっそ 次までではなく、無限級数にしてしまう。そして として、 の各次数の係数を求めたい。ここで、 と計算でき…
「要素を 1 個ずつ追加していくときに値がどう変化していくか」を観察する方向でずっと考えていて迷走してしまった... 問題へのリンク 問題概要 正の整数 と、 個の整数 が与えられる。 に対して、 の値を 998244353 で割ったあまりを求めよ。 制約 解法 個…
この問題のテスターをやってた！ 今流行の NTT 系問題！！しかも分割統治 + FFT というカッコいいやつ！！ 問題へのリンク editorial 問題概要 'U', 'M', 'G' のみからなる長さ の文字列 の UMG 数を、以下の条件を満たす添字 の組の個数として定義する。 T[…
こういうのは包除原理しかない！ 問題へのリンク 問題概要 人の人がいる。 人 の身長は である。以下の条件を満たすように、 組のペアを作る方法は何通りあるか、998,244,353 で割ったあまりを求めよ。 どの人もちょうど一つのペアに含まれる。 どのペアも、…
すごい面白かった！！！ 問題へのリンク 問題概要 整数 が与えらえたときに、漸化式 を満たす数列 が与えられる。これに対して以下の 個のクエリに答えよ: 1 つのクエリは 2 以上の整数 が指定され、 を満たすような正の整数 に対して、 の総和を求め、10000…
これ 81 人も通してるのか... 問題へのリンク 問題概要 人の子供がいる。 日間にわたって、 人の中から 人を一様ランダムに選んでクッキーを与える。 日分のあらゆるクッキーの配り方を考えたときの「各子供の最終的にもらったクッキーの個数の積」の総和を…
添字 GCD 畳み込みの練習に 問題へのリンク 問題概要 の格子点上の二点対であって、その二点を結ぶ線分上に格子点をもたないものが何個あるかを数え上げよ。(1000000007 で割ったあまりで) 制約 解法 1：添字 GCD 畳み込み この問題は、線分として 軸や 軸に…
NTT と聞いて 問題へのリンク 問題概要 偶数 が与えられる。 十進法表記で () しか登場しない 桁の整数のうち、 前半 桁の各位の和 後半 桁の各位の和 が等しいものが何通りあるか、998244353 で割ったあまりで答えよ。leading zero は OK。 制約 考えたこと…
FFT 勉強シリーズその 2。 うーん、、、これ思いつけるもんなんかいな...... Codeforces 488 DIV1 E - Nikita and Order Statistics 問題概要 要素の整数数列 と整数 が与えられる。数列 の連続する部分列のうち、「 未満の値となっているものが 個ある」と…
FFT の勉強シリーズその 1 なん yukicoder 0206 数の積集合を求めるクエリ 問題概要 どの 2 つも互いに相異なるサイズ L の数列 A[0], A[1], ..., A[L-1] と どの 2 つも互いに相異なるサイズ M の数列 B[0], B[1], ..., B[M-1] とが与えられる。 各 A[i], B…
