Rikka with Rock-paper-scissors

题目链接

题意

有两个人进行$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).$$