2017 ACM-ICPC 亚洲区(西安赛区)网络赛

B Coin
\(\frac{(\frac{q}{p}+\frac{p-q}{p})^k+(-\frac{q}{p}+\frac{p-q}{p})^k}{2}\).求快速幂和逆元。

C Sum
其实输出233个1000000就可以了、或者233个9?

E Maximum Flow
找规律得到。在\(2^k\)的时候会突变。
大概是\(\sum_{i=1}^{2^i\leq n-1}(4^{i-1}+1)*\left \lfloor \frac{n+2^{i-1}+1}{2^i} \right \rfloor\).

F Trig Function
\(cos nx = \sum_{k=0}^{n} g(n,k)\frac{n(n+k-2)!!}{k!(n-k)!!}cos^k x\)。
其中,
$$g(n,k)=\left\{\begin{matrix}
(-1)^{\frac{n-k}{2}}|n\% 2=k\% 2\\
0|others
\end{matrix}\right.$$.

G Xor
大致思路是,一开始可以预处理出到根间隔为k=1,2..,300以内的小数据。小数据查询的时候,从a开始,看a到根余几,把这些的异或和弄出来,再在根到b上弄出余(k-moda)的。
大数据直接暴力lca跑。
贴一份cww的代码。

I Barty’s Computer
I好像就是个暴力啊。。。

Leave a Reply

Your email address will not be published. Required fields are marked *