多項式・FPS(形式的冪級数)
この問題のテスターをやってた！ 今流行の NTT 系問題！！しかも分割統治 + FFT というカッコいいやつ！！ 問題へのリンク editorial 問題概要 'U', 'M', 'G' のみからなる長さ の文字列 の UMG 数を、以下の条件を満たす添字 の組の個数として定義する。 T[…
時々やってくる積分ゲー。同時に多項式ゲーでもあった。 問題へのリンク 問題概要 個の区間 が与えられる。これらの区間から一様分布にしたがって点をとってくる (連続値)。 各点の座標の最大値の期待値を をかけた値 (整数値になる) を 1000000007 で割った…
形式的冪級数の練習！ 問題へのリンク 問題概要 各 に対して、次の問に答えよ。 二分木 (完全二分木でなくてもよいし、頂点数も未定) であって、 各頂点の重みが のいずれか 各頂点の重みの総和が であるようなものの個数を 998244353 で割ったあまりを求め…
FPS の inv 関数が使える問題 問題へのリンク 問題概要 階段で一度に登れる段差が であるとする。ちょうど 段を登る方法が何通りあるか、1000000007 で割ったあまりを求めよ。 制約 考えたこと として、 の 次の係数を求める問題となる。 の計算量でできる。…
形式的冪級数 (FPS) を用いた「多項式としての除算」の練習に 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 がある。 は初期状態ではすべて 0 である。 に以下の一連の 回の操作を行った。 各操作は区間 で表される ( を満たす) 数列 の該当する区…
すごく NTT したくなる 問題へのリンク 問題概要 正の整数 が与えられる。 をそれぞれ 個以上 個以下とってくる方法のうち、平均が となるものの個数を素数 で割ったあまりを、各 に対して求めよ。 制約 考えたこと まず、平均制約を次のように言い換える。…
DP 高速化系問題。こういうのが緑 diff になるようになったんかーー (水色 diff にアップグレードした！) 問題へのリンク 問題概要 マスからなるマス目が与えられる。また、 個の互いに disjoint な区間 が与えられる。この区間に属する整数からなる集合を …
実は、元の文字列の形はどうでもよくて、文字列の長さだけが重要という！！！ 問題へのリンク 問題概要 長さ の英子文字からなる文字列 が与えられる。これに以下の操作をちょうど 回行ってできる文字列が何通り考えられるか、1000000007 で割ったあまりを求…
どこかでめっちゃ似たのを解いたことあると思ったらコレだった！ drken1215.hatenablog.com 問題へのリンク 問題概要 長さ の正の整数列 と、正の整数 が与えられる。 個の整数 の空でない部分集合 は 通りあるが、そのそれぞれについて、 = の部分集合のう…
すっごく色んな方法がありそう！！！ 問題へのリンク 問題概要 正の整数 が与えられる。, を満たすすべての整数 についての の総和を 1000000007 で割ったあまりを求めよ。 制約 考えたこと とりあえず二項係数の計算自体は、適切に前処理をしておけば、 で…
すごい面白かった！！！ 問題へのリンク 問題概要 整数 が与えらえたときに、漸化式 を満たす数列 が与えられる。これに対して以下の 個のクエリに答えよ: 1 つのクエリは 2 以上の整数 が指定され、 を満たすような正の整数 に対して、 の総和を求め、10000…
バチャでは手が回らなかったけど、復習した。ちょっとこの多項式解法は今はよくわからないけど、覚えておこう... 問題へのリンク 問題概要 要素の数列 が与えられる。 の順列 に対して、それを巡回群の直積として表したときの、各巡回群に含まれる要素に対応…
重たい。。。 でも例えば行列 に対して の計算を行列累乗に帰着させるテクニックは、蟻本中級編の行列累乗のところに載っていたりする。それを膨らませると みたいな計算も、行列累乗でできそうという気持ちには確かになるよね。。。(なったけど昨日間に合わ…
今日の以下の類題 drken1215.hatenablog.com 解説はここに書いた。 qiita.com コード 形式的冪級数を用いてみた。 // // Formal Power Series (on runtime mod) // // verified: // Yosupo Judge // https://judge.yosupo.jp/problem/inv_of_formal_power_se…
最大公約数を求めるときに abs つけてれば通ってた。。。 なにこれ悔しすぎる。。。 問題へのリンク 問題概要 次の整数係数多項式 が与えられる。任意の整数 に対して が で割り切れるような素数 をすべて求めよ。 制約 考えたこと めっちゃ好き！！！！！！…
連立方程式の練習。多項式補間でも解ける。誤差がきつい。 問題へのリンク 問題概要 次多項式 がある (係数はわからない)。 個の点 の値がわかっている...はずだったが、そのうちの 1 個については間違った値が出力された状態で入力が与えられる。どれが間違…
このシンプル設定でこの深み...すごい！！！ や は順列や組合せを表すものとする。 問題へのリンク 問題概要 長方形の紙があって、水平方向の切れ線が 箇所、垂直方向の切れ線が 箇所ある。 箇所の切れ線から 箇所選んで順に切って行く 通りの方法それぞれに…
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…
最初迷走したけど、順位表見ると上位陣が 5 分とかで解いていて、「いくらなんでもこの方針で 5 分はない、きっとなにか簡潔な視点があるはず」と思えて思い付けたのがよかった。 問題へのリンク 問題概要 N 個のマスを赤、緑、青、無の 4 色に塗り分ける。 …
