HNOI

HNOI2018:1/?

HNOI2017:2/?

HNOI2016:2/?

HNOI2018

「HNOI2018」道路

请先思考后再展开

HNOI2017

「HNOI2017」抛硬币

请先思考后再展开

2019.2做过,当时膜飞,2020.5再来看,感觉也就那样

首先式子就是$\sum_{A1=0}^A \sum_{B1=0}^B [A1>B1]C_{A}^{A1}C_b^{B1}$

对于A=B,利用其对称性,考虑反转二进制来反转胜负,发现只有在平手时才会始终输,$ans=\frac{(\sum_{A1=0}^A C_A^{A1})^2-\sum_{A1=0}^A (C_A^{A1})^2}{2}=\frac{2^{2n}-C_{2n}^n}{2}$

对于A>B,同上考虑且要利用$A-B$很小,明显仅$A1>B1且A-A1>B-B1$会始终赢,即$A1-B1 \in (0,A-B)$

于是$ans=\frac{ 2^{A+B}+ \sum_{t=1}^{A-B-1} \sum_{i=0}^B C_B^i C_A^{i+t} }{2}$,将$C_{B}^i写成C_{B}^{B-i}$,满足范德蒙德卷积,变成$\sum_{t=1}^{A-B-1} C_{A+B}^{B+t}$

组合数需要一个拓展Lucas定理,复杂度为$O(2^k+5^k+(A-B)log)$

「HNOI2017」影魔

请先思考后再展开

HAOI2016

「HNOI2016」网络

请先思考后再展开

「HNOI2016」序列

请先思考后再展开

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