tkppc2016题解

Source

技術室奥プログラミングコンテスト#2

tkppc2016

tkppc2016 D エンブレム(Emblem)

题意:从前有个wxh的网格,$从左下角(0,0)射出一条向(K,h)$的光线不断反射,求最后形成的路径中光线重合的点的个数

请先思考后再展开

在某条边上反射等价于将这个网格沿那条边对称作图后继续按直线射,所以一定会到某个网格角结束反射

然后对于不互质的$(w,h)$,明显可以把$gcd*gcd$看做一个块,答案显然不变,故现在得到$(W,H),gcd(W,H)=1$

结论:若$W*H且gcd(W,H)=1$的网格左下角射出$(0,0)\to(1,1)$的光线,则$\forall x,y \in N,(x+y)\%2=0,(x,y)会被经过$,其中不在边框上的点会被经过多次,且上述结论是充要的,$ans(W*H)=\frac{(W+1)(H+1)}{2}-(W+1)-(H+1)+四个角被多算$

$在(W,H)中射(k,H),等价于(W*H/k,H)中射45度$,如果边长不是整数放缩一下即可,code

tkppc2016 H デバッグ(Debug)

题意:n点m边无向图,求每个点出发,长度为4的简单路径数,$n,m \le 1e5$

请先思考后再展开

woshiwang

三元环、四元环计数见这里,设$g(x,k)$表示经过x的k元环个数;接下来就是讨论,设$f(x,ln)$表示从x出发长度为ln的简单路径计数
$$
f(x,2)=\sum [f(y,1)-1] \\
f(x,3)=\sum [f(y,2)-(deg_x-1)]-g(x,3)*2 \\
f(x,4)=\sum [f(y,3)]-g(x,4)*2-g(x,3)*2*(deg_x-2)-(f(x,2)*(deg_x-1)-g(x,3)*2) \\
分别表示在四元环上、三元环上、二元环上,注意二元环可能计重,一开始没意识到
$$
code

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