多項式・FPS(形式的冪級数)
「戻す DP」または「FPS」で！ 問題へのリンク 問題概要 最初、箱は空である。以下の操作を 回行う。各操作後において、以下の値を答えよ。 箱に入っているボールをいくつか選ぶ方法であって、ボールに書かれた数値の総和が となる方法の個数を 998244353 で…
Polynomial Taylor Shift が使えた！ 問題へのリンク 問題概要 頂点数 の木が与えられる。各 に対して、次の問いに答えよ。 頂点から 個の頂点を選ぶ 通りの方法それぞれについて その 個の頂点をすべて含む連結な部分グラフのサイズとして考えられる最小値…
面白かった！ 問題へのリンク 問題概要 整数係数の多項式 と、整数定数 が与えられる。 を展開したときの各係数を 998244353 で割った余りを求めよ。 制約 考えたこと Polynomial Taylor Shift については、次の記事に詳しく書いた。計算量は となる。 drken…
Polynomial Taylor Shift を履修したので、簡単にまとめてみます。例によって、Yosupo Library Checker の 問題 を通します。 なお、Polynomial Taylor Shift の解法は、単なるライブラリ整備の一環とみなすというよりは、その導出過程をぜひ押さえておきた…
最初 DP で迷走して、期待値の線形性を使って まで来れた。でも、Polynomial Taylor Shift なる解法もあるらしい！ 問題へのリンク 問題概要 個のキャンディがあって、各キャンディの色は正の整数 で表されている。 各 に対して、 個のキャンディから 個のキ…
コンテスト終了から 8 秒後の AC で泣いた。でも、分割統治 FFT が自力で書けてよかった。想定解法は FPS だった。 問題へのリンク 問題概要 次の問題がある。 の順列 と が与えられる。 これらをもとに次のように、頂点数 、辺数 の有向グラフを作る。 頂点…
ここでは の計算量の解法を実装した。本当は FPS を使えば の計算量でできる。 問題へのリンク 問題概要 非負整数値 が与えられる。 の分割数を 998244353 で割った余りを求めよ。 制約 考えたこと ここでは、この記事に書いた の計算量の解法を実装した。 q…
将来、「積の和」タグを開いたときに、最も典型的な問題が目に入るように。なお、二項係数 を と表記することにする。 問題概要 長さが で総和が であるような、正の整数のみからなる数列 は 通り考えられる。これらすべての数列についての の総和を 9982443…
FPS + 負の二項係数 問題へのリンク 問題概要 長さが で総和が であるような、正の整数のみからなる数列 すべてについての の総和を 998244353 で割ったあまりを求めよ ( ケース)。 制約 解法 (1)：FPS 求めたいものは である。これはちゃんと計算すると、 …
プリューファーコード！ それを知っていれば FPS 解法は自然。 問題へのリンク 問題概要 以上 以下の整数集合の部分集合 {} が与えられる。 頂点に と番号のついた頂点数 の木であって、各頂点の次数が集合 に含まれているようなものの個数を 998244353 で割…
FPS による考察はやっぱり強力ですね！ 問題へのリンク 問題概要 長さ かつ総和 である非負整数列 のうち、以下の条件を満たすものの個数を 998244353 で割ったあまりを求めよ。 「以下の操作のうちどちらかを選んで行うことを繰り返して、 の全ての要素を 0…
AND と XOR は、それぞれ「掛け算」と「足し算」に対応するので、行列累乗が使える！ 問題へのリンク 問題概要 個の整数の組 と が与えられる。 数列 は次の漸化式で定義される。 () AND XOR AND XOR ... XOR AND () の値を求めよ。 制約 考えたこと AND は…
opt さんとのスペースで解いた！ いくつか典型を見落としていたのでメモ！！ 問題へのリンク 問題概要 のグリッドがあって、マス には値 が記されている。 いずれかのマスから始めて右または下に隣接するマスへの移動を 0 回以上繰り返すことで得られる経路…
「TDPC T - フィボナッチ」の亜種とも言える問題ですね。 問題へのリンク 問題概要 () によって定義される数列を考える。 整数 が与えられので、 AND を満たすすべての非負整数 に対する の総和を 998244353 で割った余りを求めよ。 制約 考えたこと この問…
Boston--Mori 法を履修した！ 問題へのリンク 問題概要 () によって定義される数列において、 を 1000000007 で割ったあまりを求めよ。 制約 解法 0-indexed にして考えることにする。つまり、 () によって定義される数列において、 を求めることにする。 こ…
DP 高速化に累積和を使う問題！ 問題へのリンク 問題概要 人の子ども に、 個の飴を分けることにした。 ただし、子ども に分ける飴は、 個以上 個以下のする必要がある。 各子どもへの飴の分け方の総数を、1000000007 で割ったあまりを求めよ。 制約 解法：…
この平方分割のやり方はちゃんとマスターしたい 問題へのリンク 問題概要 種類のレベル 1 の宝石がある。各種類のレベル 1 の宝石は無限個ある。 個の宝石を合成することで、レベル の宝石を作ることができる。ただし、その 個の宝石は次の条件を満たす必要…
残り 1 分でなんとか通せた。 問題へのリンク 問題概要 頂点数 の連結な単純無向グラフ (頂点番号は であって、次の条件を満たすものの個数を で割ったあまりを求めよ。 なお、ここで、頂点 から各頂点 までの最短距離を としている。 制約 考えたこと グラ…
前回の ABC に続いて、D 問題が数学っぽい。でも実際には今回は探索問題ですね。 問題へのリンク 問題概要 非負整数 を用いて と表せる整数 を「特別数」と呼ぶことにします。 非負整数 が与えられますので、 以上である最小の「特別数」を求めてください。 …
問題を見て「めっちゃ数学やん！！なにこれ！？？」となった人は多いと思う！！！ でも落ち着いて整理して取り組めば解けるので、落ち着くことが大事そう。 もしくは、ライブラリで殴る！！！！！！ 問題へのリンク 問題概要 つの多項式 次の多項式 次の多項…
コンテスト中にアダマール変換を思い出せたのはよかった！ 問題へのリンク 問題概要 整数 と 個の整数 が与えられます。次の条件を満たすような Nim をすべて考えます。 山の個数は のいずれかである 各山の石の個数は のいずれかである このような Nim の盤…
ぷよぷよみたいに 2 つ揃うと消えるような対象物の数え上げ問題。これを思い出した drken1215.hatenablog.com 問題へのリンク 問題概要 (意訳) "B", "W", "?" のみからなる長さ の文字列が与えられる ( は偶数)。"?" に "B", "W" を割り当てる方法のうち、"B…
色んな解法がありそう。 問題へのリンク 問題概要 個の正の整数 が与えられる。 を満たすすべての非負整数列 に対する の総和を 1000000007 で割ったあまりを求めよ。 制約 解法 (1)：経路数への帰着 (僕の解法) 二項係数を扱う方法論として、経路数へと帰着…
ペル方程式の練習 問題へのリンク 問題概要 数列 は次の漸化式で定義される。 この数列の母関数 を定義する。正の整数 が golden であるとは、 を満たす が有理数であることをいう。具体的には ... となっている。小さい方から 30 番目までの golden 整数の…
形式的冪級数の pow で通せた！ 問題へのリンク editorial 問題概要 個の箱それぞれに正しい括弧列を入れる。ただし、次の2つの条件をともに満たすように入れる必要がある。 個の箱に含まれる '(' の個数の合計が 長さが である括弧列はどの箱にも入れてはな…
コンテスト本番、こっちをやればよかった...ところで解説が天才すぎる！ 問題へのリンク editorial 問題概要 個の部品と、 個の接続用部品とがある。これらを用いてフィギュアを作ろうとしている。 番目の部品には 個の穴がついている。接続用部品は、2 個の…
(x - a)(x - b) ... (x - z) みたいなやつの計算 問題へのリンク 問題概要 個の箱がある。箱 には色 のボールが入っている。以下の 個のクエリに答えよ。 各クエリは 以下の整数 が与えられる 各箱から 個ずつボールを取り出す方法であって、取り出されたボ…
形式的冪級数すごい 問題へのリンク 問題概要 個の整数 が与えられる。各 に対して を 998244353 で割ったあまりを求めよ。 制約 考えたこと いっそ 次までではなく、無限級数にしてしまう。そして として、 の各次数の係数を求めたい。ここで、 と計算でき…
結構いろんな考え方のできる問題！ 問題へのリンク 問題概要 頂点数 、辺数 の無向グラフであって、次の条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。 自己ループを持たない すべての頂点の次数が 2 以下である 各連結成分のサイズを並べた…
この問題のテスターをやってた！ 今流行の NTT 系問題！！しかも分割統治 + FFT というカッコいいやつ！！ 問題へのリンク editorial 問題概要 'U', 'M', 'G' のみからなる長さ の文字列 の UMG 数を、以下の条件を満たす添字 の組の個数として定義する。 T[…
