Codeforces Round #383 (Div.2)

はい。
http://codeforces.com/contest/742

A. Arpa’s hard exam and Mehrdad’s naive cheat

ざっくりと大意

・1378のn乗の数の下一桁は何か。

Python2

n=int(raw_input())
print [6,8,4,2][n%4] if n!=0 else 1

0だけ例外で後は4増えるごとに周期性があるのでそれを利用する。TLではpowを利用する派が多かった。なぜだ。。

B. Arpa’s obvious problem and Mehrdad’s terrible solution

ざっくりと大意

・要素数n個の数列aの中からxorして結果がxになるようなペアを数える。

Python2

n,x=map(int,raw_input().split())
l=map(int,raw_input().split())
ans=chk=0
d={}
for i in l:
    if i in d:
        d[i]+=1
    else:
        d[i]=1
if x==0:
    for i in d:
        ans +=d[i]*(d[i]-1)/2
    print ans
else:
    for i in d:
        if i^x in d:
            ans+=d[i]*d[i^x]
    print ans/2

結果がxになるようなペアはi ^ j = xになるようなペアはi ^ x = jでもある特徴を利用する。そうすれば総当りでペアが成立するかを調べずにペア成立を数えられる。 xが0の場合は同じ数とのペアとなるのでnC2を計算する。 0以外ならばそれぞれの同じ数の個数の積がペアの成立数になる。但し、2重で数えていることになるので最後に2で割る。