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

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

2019-03-18から1日間の記事一覧

AtCoder AGC 031 A - Colorful Subsequence (200 点)

高校数学を思い出させてくれる感じの数え上げ問題 問題へのリンク 問題概要 長さ の文字列 が与えられる。 の部分列であって、すべて異なる文字からなるものの数を 1000000007 で割った余りを答えてください。文字列として同一でも、異なる位置から取り出さ…

yukicoder No.803 Very Limited Xor Subset

F2 線形代数大好き! 問題へのリンク 問題概要 個の整数 の部分集合を選んで XOR 和を にする方法のうち、 個の区間 [ ] () について 区間の中から選ぶ個数は偶数個か奇数個かが指定される という制約を満たすものが何通りあるか求めよ。 制約 考えたこと 実…

yukicoder No.801 エレベーター

累積和による DP 高速化のすごく面白い問題! 問題へのリンク 問題概要 階建てのビルに 個のエレベーターがあり、 番目のエレベーターは区間 [ ] の間を動いており、区間内の任意のフロアから任意のフロアへと移動することができる (同じフロアへの移動もエ…

yukicoder No.802 だいたい等差数列

面白い!!!!!!!!! 問題へのリンク 問題概要 長さ の整数列 であって、 を満たすものの個数を 1000000007 で割ったあまりを求めよ。 制約 まずは変数変換 まずは数列 の差分に注目してみることにする。 とする ( とする)。そうすると、条件は () とい…