包除原理

Codeforces #225(383 Div1) E. Vowels

問題 英小文字のうちa-xの24文字のどれか、3文字からなる単語がn個与えられる。 24文字のうち好きな文字を母音にしてよい。 母音が一文字以上含まれている単語はよい単語である。 2^24の母音の選び方に対して、(良い単語の数)^2を求め、それらを全てxorした…

TopCoder SRM 583 Div1 Hard RandomPaintingOnABoard

問題 h行w列の行列があって、(i, j)にはp[i][j]の数字が書かれている。 この行列の一つのセルを、p[i][j]に比例する確率で選ぶことを繰り返す。 全ての行と列について、その行、列に属するセルが一度以上選ばれる状態になったら、 操作を終了する。 操作が終…

TopCoder SRM 603 Div1 Medium PairsOfStrings

問題 n文字でアルファベットの最初のk種類からなる文字列A, Bのうち、 次の条件を満たす(A, B)のペアの総数をmod 10^9 + 7で求めよ。 ある文字列Cが存在し、A + C = C + Bとなる。 (ただし + は文字列の結合を表す) AまたはBが一文字でも違うとき、二つの…

AOJ 2446 Enumeration + 高速メビウス変換まとめ

問題 日本語(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2446) 制約条件 n≦20 m≦10^18

TopCoder SRM 545 Div1 Hard SetAndSet

問題 Aを非負の整数列とする。 Aの各要素を赤または青に色づけする。 色づけ後で、それぞれの色に色づけされた要素のAND(ビット毎のand)を 取ったとき、両者が等しくなっているような色づけの仕方は何通りあるか、求めよ。 制約条件 A[i]≦1048575 Aの要素≦…