2023-05-15から1日間の記事一覧
Binary Trie + 平方分割 問題へのリンク editorials 問題概要 数列 に対して、以下の 個のクエリを処理せよ。 クエリタイプ 1 (k x): を xor に置き換える クエリタイプ 2 (l r x): xor の値を出力する 制約 考えたこと これは TL で解法を見た上で解いた…
AtCoder
AtCoder500点
水色diff
ARC-B
数え上げ問題
解空間:O(N^2)通りの選択肢
3つのものの真ん中に着目する
O(√N)まで考えれば十分
平方分割
多重for文
全探索
マルチテストケース問題
ダブルカウントを防ぐ場合分け
数学(整数問題)
【問題集】整数変数の式で表された条件を扱う探索
これ系は好き! これに近いのを ABC-D で最近よく見かける気がする。 問題へのリンク 問題概要 整数 が与えられる。 3 つの整数の組 であって、 がすべて 以下であるようなものの個数を 998244353 で割ったあまりを求めよ。 ケース与えられる。 制約 考えた…
AtCoder
AtCoder700点
ARC-D
多項式・FPS(形式的冪級数)
Bostan-Mori法
制約条件:総和=K
二項係数
負の二項係数
入力が定数個
対象を一意に定める操作列を数え上げる
数え上げ問題
グラフ・盤面・数列の個数の数え上げ
操作後の結果の数え上げ
操作
橙色diff
FPS(形式的冪級数)の高等演算
FPSテク:漸化式の母関数を求める
重複組合せ
数列
Greedy:端から順に決まっていく
包除原理
制約条件:xi<=ai
FPS による考察はやっぱり強力ですね! 問題へのリンク 問題概要 長さ かつ総和 である非負整数列 のうち、以下の条件を満たすものの個数を 998244353 で割ったあまりを求めよ。 「以下の操作のうちどちらかを選んで行うことを繰り返して、 の全ての要素を 0…