けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Bostan-Mori法

AtCoder ARC 160 D - Mahjong (橙色, 700 点)

FPS による考察はやっぱり強力ですね! 問題へのリンク 問題概要 長さ かつ総和 である非負整数列 のうち、以下の条件を満たすものの個数を 998244353 で割ったあまりを求めよ。 「以下の操作のうちどちらかを選んで行うことを繰り返して、 の全ての要素を 0…

AtCoder ABC 009 D - 漸化式 (試験管黄色)

AND と XOR は、それぞれ「掛け算」と「足し算」に対応するので、行列累乗が使える! 問題へのリンク 問題概要 個の整数の組 と が与えられる。 数列 は次の漸化式で定義される。 () AND XOR AND XOR ... XOR AND () の値を求めよ。 制約 考えたこと AND は…

AtCoder ABC 300 Ex - Fibonacci: Revisited (銅色, 600 点)

「TDPC T - フィボナッチ」の亜種とも言える問題ですね。 問題へのリンク 問題概要 () によって定義される数列を考える。 整数 が与えられので、 AND を満たすすべての非負整数 に対する の総和を 998244353 で割った余りを求めよ。 制約 考えたこと この問…

TDPC (Typical DP Contest) T - フィボナッチ

Boston--Mori 法を履修した! 問題へのリンク 問題概要 () によって定義される数列において、 を 1000000007 で割ったあまりを求めよ。 制約 解法 0-indexed にして考えることにする。つまり、 () によって定義される数列において、 を求めることにする。 こ…