1/4 PKU

4018 High security

N個のパスワードが与えられる。パスワードは5文字で、各文字はA-Za-z0-9のどれかである。0<=i<=5について、「与えられたパスワードのうち2つの組で、同じ位置の文字で異なるものの数がiであるもの」の数を決定せよ。

例えば1,3,5文字目が同じであるような組の数は、1,3,5文字目だけを取り出してソートすることでO(N log N)で求められる。同様にして、すべての位置の組み合わせについてその位置の文字が同じであるような組の数を求める。その後、適切に計算をするとちょうどi文字が異なるような組の数が得られる。