【HNOI2017】抛硬币

Source and Judge

HNOI2017
loj2023

Analysis

请先思考后再展开

先观察数据范围,注意到a和b的差很特殊
还有就是要尽量减少表达式的项数,比较巧妙的做法是考虑二进制的翻转、对称性

先考虑a=b
注意到二进制翻转能完全把正负调换,那么考虑用(总情况-平局)/2
$ans=\frac{2^{a+b}-C_{2n}^n}{2}$

不同的时候, $[a1 \leq b1,a>b]->[a-a1>b-b1]$ ,所以依然能把A负或平局翻转为胜利
但部分A胜的情况翻转后依然胜利,这种情况是没有配对的,要补上
$[a1>b1,a-a1>b-b1]->[0<a1-b1<a-b]$

$$
\begin{aligned}
=&\sum_{b1=0}^b C_b^{b1} \sum_{t=0}^{a-b-1} C_a^{b1+t}\\
=&\sum_{t=1}^{a-b-1} \sum_{b1=0}^b C_b^{b-b1} C_a^{b1+t}\\
=&\sum_{k=b+1}^{a-1} C_{a+b}^{b}\\
ans=&\frac{ 2^{a+b}+\sum_{k=b+1}^{a-1} C_{a+b}^{b} }{2}
\end{aligned}
$$

求组合数要用拓展lucas,教程
不过这次稍有不同,已知质因子是2和5
$fac(n)=fac(\frac{n}{p^k}) \times p^t \times fac(p^k-1)^{\frac{n}{p^k}} \times fac(n\%p^k)$
$p^k$ 以内的阶乘可以预处理出来

最后提一提这个除以2,如果a-b+1是偶数,直接算一半(对称性)
如果是奇数,那么就是要加上 $\frac{1}{2} C_{a+b}^{(a+b)/2}$
因为只有一次,可以分解质因数暴力做

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/a109.html
转载请注明出处,谢谢!