2019-03-18から1日間の記事一覧
高校数学を思い出させてくれる感じの数え上げ問題 問題へのリンク 問題概要 長さ の文字列 が与えられる。 の部分列であって、すべて異なる文字からなるものの数を 1000000007 で割った余りを答えてください。文字列として同一でも、異なる位置から取り出さ…
yukicoder
XOR
連立一次方程式
Gauss-Jordanの掃き出し法
行列
数え上げ問題
各桁ごとに見る
Greedy:各要素について独立に考えてよい
0と1の問題
区間
N個の区間の問題
F2 線形代数大好き! 問題へのリンク 問題概要 個の整数 の部分集合を選んで XOR 和を にする方法のうち、 個の区間 [ ] () について 区間の中から選ぶ個数は偶数個か奇数個かが指定される という制約を満たすものが何通りあるか求めよ。 制約 考えたこと 実…
累積和による DP 高速化のすごく面白い問題! 問題へのリンク 問題概要 階建てのビルに 個のエレベーターがあり、 番目のエレベーターは区間 [ ] の間を動いており、区間内の任意のフロアから任意のフロアへと移動することができる (同じフロアへの移動もエ…
yukicoder
数え上げ問題
包除原理
FPSテク:漸化式の母関数を求める
数列
包除原理:対称性
条件の言い換え
変数変換して扱いやすい同型な問題を見出す
二項係数
重複組合せ
制約条件:総和=K
制約条件:総和<=K
面白い!!!!!!!!! 問題へのリンク 問題概要 長さ の整数列 であって、 を満たすものの個数を 1000000007 で割ったあまりを求めよ。 制約 まずは変数変換 まずは数列 の差分に注目してみることにする。 とする ( とする)。そうすると、条件は () とい…