2017-Sp128-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场各自看题，sub高速上机，'''K1y2'''。然后各自想题，cjb上机写I，花了很长时间。刷了一下榜发现H被板刷，sub不会做，感觉过的人太多了，猜了一发结论，cjb傻傻快速幂写错了，'''H2y53'''。yzc和sub讨论C，然后yzc上机写C，，cjb查自己的I去了，之后yzc '''C3y105'''，cjb此前交了一发wa，立马发现错的地方，修改后'''I2y105'''。cjb和yzc口胡了一下D，yzc上机wa了之后发现做法有问题，写了对拍，sub在刚E，大力猜了发结论wa了。之后sub发现没多组数据，'''E2y141'''，yzc想到做法，改了之后'''D2y152'''。cjb一直在想J，大力上了个结论，让yzc证明了一下，之后获得wa。感觉很难过，对拍了也没错，cjb把dp转移边界写得严谨了一些，又查了lca，再交就过了，'''J2y193'''。之后cjb上机抄NTT，sub上机写F，yzc一直想G，cjb想B，都不太行，之后sub '''F3y257'''。
== 总结 ==
=== chenjb ===
I会做法后写了太久了，主要是平时不怎么写数学题....Best Theorem和Matrix-tree Theorem在板子上要重新整理一次。
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * A：cjb

 * B：设a=x or y,b=x xor y,有c[k]=[y∈x][x xor y=k]b[x]*a[y]*1<<bit(y)=c[k]=[bit(x)-bit(y)=bit(k)][x xor y=k]b[x]*a[y]*1<<bit(y).以次数不超过m的多项式为元素跑FWT即可。注意时限。

 * C：求每个数的贡献，只需要枚举前面有k个比他大的和后面有k个比他大的，数字从小往大做，做完就把数字在链表里删掉，找k个数字直接在链表上跑就可以了。

 * D：枚举a[k]的某一位，考虑这一位和他不同的a[i]，显然满足条件的a[j]这一位和i相同，依次添加数字进入trie数时维护每一位是0或1的个数，并在每一个位置减去在他之前的这一位相同的个数。

 * E：对于每个边，他被经过的次数是k，和他的子树大小取min，可以证明一定能取到，统计输出即可。

 * F：展开，可以发现式子能NTT。

 * G：建一个始终为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。

 * H：n^k^

 * I：把Best Theorem改造一下，因为每个1都可以剪开，所以要乘du[1]，同时因为Best Theorem里每条边都是不同的，而本题中相同的边(x,y)视为同一种，所以还要除以每一种边的数量。

 * J：重要结论是对于树上任意p个点，随意排列，总存在相邻两个点的lca等于所有p个点的lca，f[i][j]表示前i个数中有j块的最小答案，有三种可能，第一种是i和i-1存在于第j块中，但是他们不对答案作贡献，第二种是i和i-1对答案作了贡献，特殊转移是i单独在一块里，就变成O(nk)的dp了。

 * K：统计有多少个数<=35。

 * [http://bestcoder.hdu.edu.cn/blog/2017-multi-university-training-contest-3-solutions-by-洪华敦/ Official]

流水账

开场各自看题，sub高速上机，K1y2。然后各自想题，cjb上机写I，花了很长时间。刷了一下榜发现H被板刷，sub不会做，感觉过的人太多了，猜了一发结论，cjb傻傻快速幂写错了，H2y53。yzc和sub讨论C，然后yzc上机写C，，cjb查自己的I去了，之后yzc C3y105，cjb此前交了一发wa，立马发现错的地方，修改后I2y105。cjb和yzc口胡了一下D，yzc上机wa了之后发现做法有问题，写了对拍，sub在刚E，大力猜了发结论wa了。之后sub发现没多组数据，E2y141，yzc想到做法，改了之后D2y152。cjb一直在想J，大力上了个结论，让yzc证明了一下，之后获得wa。感觉很难过，对拍了也没错，cjb把dp转移边界写得严谨了一些，又查了lca，再交就过了，J2y193。之后cjb上机抄NTT，sub上机写F，yzc一直想G，cjb想B，都不太行，之后sub F3y257。

总结

chenjb

I会做法后写了太久了，主要是平时不怎么写数学题....Best Theorem和Matrix-tree Theorem在板子上要重新整理一次。

oipotato

subconscious

题解

A：cjb
B：设a=x or y,b=x xor y,有c[k]=[y∈x][x xor y=k]b[x]*a[y]*1<
C：求每个数的贡献，只需要枚举前面有k个比他大的和后面有k个比他大的，数字从小往大做，做完就把数字在链表里删掉，找k个数字直接在链表上跑就可以了。
D：枚举a[k]的某一位，考虑这一位和他不同的a[i]，显然满足条件的a[j]这一位和i相同，依次添加数字进入trie数时维护每一位是0或1的个数，并在每一个位置减去在他之前的这一位相同的个数。
E：对于每个边，他被经过的次数是k，和他的子树大小取min，可以证明一定能取到，统计输出即可。
F：展开，可以发现式子能NTT。
G：建一个始终为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。
H：n^k
I：把Best Theorem改造一下，因为每个1都可以剪开，所以要乘du[1]，同时因为Best Theorem里每条边都是不同的，而本题中相同的边(x,y)视为同一种，所以还要除以每一种边的数量。
J：重要结论是对于树上任意p个点，随意排列，总存在相邻两个点的lca等于所有p个点的lca，f[i][j]表示前i个数中有j块的最小答案，有三种可能，第一种是i和i-1存在于第j块中，但是他们不对答案作贡献，第二种是i和i-1对答案作了贡献，特殊转移是i单独在一块里，就变成O(nk)的dp了。
K：统计有多少个数<=35。
Official

附加文件

1.png by chenjb