漸化式
きたまさ法によく似たタイプの DP ダブリング高速化！ ただかなり難しい問題だと思うので、004 まで順調に解いていた方が、この問題で挫折しないように注意！！！ 無理に解こうとせずに飛ばすのも一案だと思います...... 問題へのリンク editorial 問題概要 …
ペル方程式の練習 問題へのリンク 問題概要 数列 は次の漸化式で定義される。 この数列の母関数 を定義する。正の整数 が golden であるとは、 を満たす が有理数であることをいう。具体的には ... となっている。小さい方から 30 番目までの golden 整数の…
ならば になるネタ、結構見る！ 問題へのリンク 問題概要 数列 があって、初期状態では となっている。ここで 2 つの正の整数の組 に対して正の整数 を返す関数 を考える。 次の条件を満たす操作列を構築せよ。1 つの操作は整数 で与えられ、 , をともに で…
この手の 周期性を利用する ダブリングする のどちらでも解けるタイプの問題、最近めっちゃ多いね。 問題へのリンク 問題概要 を で割ったあまりを で表す。 整数 が与えられる。以下で定まる漸化式の最初の 項の総和を求めよ。 制約 考えたこと 最初誤読し…
いわゆる本当に最初の入門という感じの DP だね。 問題へのリンク 問題概要 段の階段があって、現在は 0 段目にいる。 高橋君は一歩で 1 段か 2 段上がることができる。ただし 段目は壊れていて、そこに足を踏み入れることはできない。 高橋君が 0 段目から …
この問題の既存の解説記事は中国剰余定理によるものが多かったので、それ以外の方法を示すのはいいかもなん。 AOJ 2353 Four Arithmetic Operations 問題概要 有理数列 がある。各項は以下のように定義される: ただし は ＋、－、×、÷ のいずれかである。 を…
