読者です 読者をやめる 読者になる 読者になる

n-knuu's logs

憧れ駆動。だいたい競プロ

Codeforces Round #355 div2 C. Vanya and Label

codeforces

問題

文字列S(0..9, A..Z, a..z, -, _)を64進数とみなす。このとき、論理和をとってSと等しくなる文字列の個数を求めよ(ただしmod 10^9+7を取れ)

制約

1 <= |S| <= 10^5

解法

64進数なので、ちょうど6桁ごとに論理和を取って一致すればよい。
よってまず、64×64の組み合わせについて予め論理和を取った後に、文字列を前から順番に見ていって、論理和を取ってS_iになる文字の組の個数を掛けあわせていけば良い。

計算量

O(|S|)

コード


感想

2^iが底じゃないときはどうするんだろう...