rikka with rock

有两个人进行$n$局石头剪刀布游戏，设其中一个人赢了$a$局，另一个人赢了$b$局，$n-a-b$局平局。则分数为$gcd(a,b)$。
问分数的期望。

$$ans={3}^{n} sum_{a=0}^{n} sum_{b=0}^{n-a} C_{n}^{a} C_{n-a}^{b} gcd(a, b).$$ $$={3}^{n} sum_{d=1}^{n} sum_{a=0}^{n} sum_{b=0}^{n-a} C_{n}^{a} C_{n-a}^{b} d[gcd(a,b)==d].$$ $$={3}^{n} sum_{d=1}^{n} d f(d).$$ $$f(d) = sum_{a=0}^{n} sum_{b=0}^{n-a} C_{n}^{a} C_{n-a}^{b} [gcd(a,b) == d].$$ $$F(d) = sum_{a=0}^{n} sum_{b=0}^{n-a} C_{n}^{a} C_{n-a}^{b} [d | gcd(a, b)].$$ $$F(d) = sum_{d | k} f(k).$$ $$f(d) = sum_{d | k} mu( frac{k}{d}) F(k).$$ $$F(d) = sum_{a=0}^{n} sum_{b=0}^{n-a} C_{n}^{a} C_{n-a}^{b} [d | gcd(a,b)] [gcd(a, b) != 0].$$ $$= sum_{a=0}^{ frac{n}{d} } sum_{b=0}^{ frac{n}{d} - a} C_{n}^{ad} C_{n-ad}^{bd} -1.$$ $$= sum_{a=0}^{ frac{n}{d} } sum_{b=0}^{ frac{n}{d} - a} frac{n!}{(ad)!(bd)!(n-ad-bd)!} -1.$$ $$= sum_{a=0}^{ frac{n}{d} } sum_{b=0}^{a} frac{n!}{(ad - bd)!(bd)!(n-ad)!} - 1.$$ $$= n! sum_{a=0}^{ frac{n}{d} } frac{1}{(n - ad)! } sum_{b=0}^{a} frac{1}{(bd)!(ad-bd)!} - 1.$$ $$= n! sum_{a=0}^{ frac{n}{d} } frac{1}{(n - ad)! } (fac * fac)_{a} - 1.$$

可以用FFT优化这个狄利克雷卷积。

$$ans = {3}^{n} sum_{d=1}^{n} d f(d).$$ $$= {3}^{n} sum_{d=1}^{n} d sum_{d | k} mu( frac{k}{d} ) F(k).$$ $$= {3}^{n} sum_{k=1}^{n} sum_{d | k} d mu( frac{k}{d} ) F(k).$$ $$= {3}^{n} sum_{k=1}^{n} F(k) phi(k).$$