多項式
AtCoder
AtCoder600点
ABC-Ex
赤色diff
高速畳み込み計算
分割統治法
オンライン処理を実現する分割統治法
DP
多項式
多項式・形式的冪級数
分割統治FFT
FFT
DP高速化
DP高速化:FFT
平方分割
漸化式
数え上げ問題
フラクタル構造を解く
入力が定数個
この平方分割のやり方はちゃんとマスターしたい 問題へのリンク 問題概要 種類のレベル 1 の宝石がある。各種類のレベル 1 の宝石は無限個ある。 個の宝石を合成することで、レベル の宝石を作ることができる。ただし、その 個の宝石は次の条件を満たす必要…
AtCoder
AtCoder400点
ABC-D
緑色diff
式変形
ある量を固定して考える
二分探索
lower_bound
多項式
方程式
見積り大事
整数問題
しゃくとり法
単調性に着目する
前回の ABC に続いて、D 問題が数学っぽい。でも実際には今回は探索問題ですね。 問題へのリンク 問題概要 非負整数 を用いて と表せる整数 を「特別数」と呼ぶことにします。 非負整数 が与えられますので、 以上である最小の「特別数」を求めてください。 …
問題を見て「めっちゃ数学やん!!なにこれ!??」となった人は多いと思う!!! でも落ち着いて整理して取り組めば解けるので、落ち着くことが大事そう。 もしくは、ライブラリで殴る!!!!!! 問題へのリンク 問題概要 つの多項式 次の多項式 次の多項…
AtCoder
AtCoder600点
ABC-Ex
橙色diff
高速畳み込み計算
高速アダマール変換
XOR
DP
DP高速化
DP高速化:FFT
ダブリング
Nim
ゲーム
数え上げ問題
数列
バケット
級数和を求める
グラフ・盤面・数列の個数の数え上げ
補集合を考える
制約:数値が10^6以下
多項式
再帰的構造に着目する
コンテスト中にアダマール変換を思い出せたのはよかった! 問題へのリンク 問題概要 整数 と 個の整数 が与えられます。次の条件を満たすような Nim をすべて考えます。 山の個数は のいずれかである 各山の石の個数は のいずれかである このような Nim の盤…