2018-Sp29-lyk

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[[Image(1.jpg,500px)]]

[http://10.71.10.90/pia/trac/wiki/2017-Sp128-team2 Legilimens]

[/wiki/2018-team3 返回Helianthus]

[https://vjudge.net/contest/253709#overview]

== 流水账 ==

== 总结 ==
=== LYK ===
ntt负数会炸，记下来。rmq求lca，jhguai记下来。新姿势学习。

=== Jhguai  ===

=== Heltion ===
怎么连LCA都不会

== 题解 ==
 * A: 容斥 高精度 之后怎么做不知道
 * ~~B~~: 化简式子后fwt或者N维前缀和
 * ~~C~~: 从大到小加入，维护set和链表，前后80个的位置在链表上走
 * ~~D~~: trie树，从左到右枚举J，维护左右a[i]的两颗trie树，同时维护f[i][0/1]表示第i高位相同，后一位左0右1的情况数。
 * ~~E~~: sigma(v[i]*min(sz[vet[i]],k))  i是边的编号 ，v是边权，vet是出点
 * ~~F~~: ntt加速
 * ~~G~~: trie树模拟:建一个始终为1的bit，记为one。建m*2个变量s[0/1][i]表示第i位是不是0/1。s[1][i]初值为0，添加门gate(i,one,s[1][i])。s[0][i]初值为1，添加门gate(s[1][i],one,s[0][i])。然后建trie树，每个节点建一个检验能否从根节点到达的bit，记为act[p]，初值为0。添加门gate(act[fa],s[0/1][i],act[p])，s中的0，1取决于p是其父亲的哪个儿子。显然在叶子结点中只有一个act是1。我们令输出的初值为0，对于每个叶子结点，假如对应的结果为1，则添加门(act[p],one,m+1)。其中m+1为输出的编号。这样输出就只可能在act为1的那一个叶子变化，假如那个叶子对应的答案为0，那么初值不需要变，否则会变成1。需要2m+3*2 ^m^ 个extra bits和gates。
 * ~~H~~: ans=n^k
 * ~~I~~: BEST's THEOREM + matrix tree 要先判有没有欧拉回路
 * ~~J~~: 结论题 RMP求LCA GTMjhguai
 * K: 沙比题 GTMjhguai
 * [http://bestcoder.hdu.edu.cn/blog/2017-multi-university-training-contest-3-solutions-by-%E6%B4%AA%E5%8D%8E%E6%95%A6/ official]
== 补题 ==

Legilimens

[/wiki/2018-team3 返回Helianthus]

https://vjudge.net/contest/253709#overview

流水账

总结

LYK

ntt负数会炸，记下来。rmq求lca，jhguai记下来。新姿势学习。

Jhguai

Heltion

怎么连LCA都不会

题解

  • A: 容斥 高精度 之后怎么做不知道
  • B: 化简式子后fwt或者N维前缀和
  • C: 从大到小加入，维护set和链表，前后80个的位置在链表上走
  • D: trie树，从左到右枚举J，维护左右a[i]的两颗trie树，同时维护f[i][0/1]表示第i高位相同，后一位左0右1的情况数。
  • E: sigma(v[i]*min(sz[vet[i]],k)) i是边的编号 ，v是边权，vet是出点
  • F: ntt加速
  • G: trie树模拟:建一个始终为1的bit，记为one。建m*2个变量s[0/1][i]表示第i位是不是0/1。s[1][i]初值为0，添加门gate(i,one,s[1][i])。s[0][i]初值为1，添加门gate(s[1][i],one,s[0][i])。然后建trie树，每个节点建一个检验能否从根节点到达的bit，记为act[p]，初值为0。添加门gate(act[fa],s[0/1][i],act[p])，s中的0，1取决于p是其父亲的哪个儿子。显然在叶子结点中只有一个act是1。我们令输出的初值为0，对于每个叶子结点，假如对应的结果为1，则添加门(act[p],one,m+1)。其中m+1为输出的编号。这样输出就只可能在act为1的那一个叶子变化，假如那个叶子对应的答案为0，那么初值不需要变，否则会变成1。需要2m+3*2 m 个extra bits和gates。
  • H: ans=n^k
  • I: BEST's THEOREM + matrix tree 要先判有没有欧拉回路
  • J: 结论题 RMP求LCA GTMjhguai
  • K: 沙比题 GTMjhguai
  • official

补题

附加文件