漸化式
ペル方程式の練習 問題へのリンク 問題概要 数列 は次の漸化式で定義される。 この数列の母関数 を定義する。正の整数 が golden であるとは、 を満たす が有理数であることをいう。具体的には ... となっている。小さい方から 30 番目までの golden 整数の…
Codeforces
分割統治法
2^K
構築
入力が定数個
数列
操作
操作:上書き
数学的帰納法
再帰的構造に着目する
漸化式
見積り大事
過半数に関する考察
CodeforcesOthers
CodeforcesR2300
ならば になるネタ、結構見る! 問題へのリンク 問題概要 数列 があって、初期状態では となっている。ここで 2 つの正の整数の組 に対して正の整数 を返す関数 を考える。 次の条件を満たす操作列を構築せよ。1 つの操作は整数 で与えられ、 , をともに で…
AtCoder
AtCoder500点
ABC-E
ダブリング
周期性に着目する
シミュレーション問題
サイクル
整数問題
数列
漸化式
鳩の巣原理
累積和
総和を求める
K回操作後の結果を求める
操作:整数をreplaceしていく
緑色diff
この手の 周期性を利用する ダブリングする のどちらでも解けるタイプの問題、最近めっちゃ多いね。 問題へのリンク 問題概要 を で割ったあまりを で表す。 整数 が与えられる。以下で定まる漸化式の最初の 項の総和を求めよ。 制約 考えたこと 最初誤読し…
いわゆる本当に最初の入門という感じの DP だね。 問題へのリンク 問題概要 段の階段があって、現在は 0 段目にいる。 高橋君は一歩で 1 段か 2 段上がることができる。ただし 段目は壊れていて、そこに足を踏み入れることはできない。 高橋君が 0 段目から …