2019-team11/0002

从 Trac 迁移的文章

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

原文章内容如下：

=== 2019.05.25 2016 Multi-University Training Contest 1 总结 By 1em0n Team ===

=== Part 1 流水账 ===

=== Part 2 队员总结 ===

=== 孔畅 ===

=== 夏天鑫 ===

=== 黄彦玮 ===



=== 补题 ===
|| Contest Name                                                                                            || A || B || C || D || E || F || G || H || I || J || K || L || M ||
|| 2016 Multi-University Training Contest 1                            || O || O || . || O || O || Ø || Ø || . || . || . || O || X || X ||
O:当场通过 .:尚未通过 Ø:赛后通过 #:口胡通过 X:不存在的

=== 题解 ===
E:  阴阳两种珠子的项链，给定若干个限制条件表示一个阴珠和哪几个阳珠相邻会变色，求最少有几个阴珠变色。————二分图匹配，枚举阳珠顺序，转化成最多能匹配几个阴珠，注意到环的不同排列数是(n-1)!，复杂度为O((n-1)!*n^2^)

F：（数论->欧拉函数），比较详细的推导见 https://blog.csdn.net/wust_zzwh/article/details/51966450
   这题是两个问题的融合，一个是求/sum i=1~m phi(i*n)，其中n的所有质因子的幂都是1，另一个是求k的k的k的......次幂 %p的值，需要用到欧拉降幂公式，见BZOJ3884.

G：原题题意比较模糊，dp方程是dp[i]=/sum j=i~i dp[j]*a[i-j]，CDQ分治+FFT模板题，复杂度O(nloglogn)

2019.05.25 2016 Multi-University Training Contest 1 总结 By 1em0n Team

Part 1 流水账

Part 2 队员总结

孔畅

夏天鑫

黄彦玮

补题

Contest Name

A

B

C

D

E

F

G

H

I

J

K

L

M

2016 Multi-University Training Contest 1

O

.

O

Ø

.

O

X

O:当场通过 .:尚未通过 Ø:赛后通过 #:口胡通过 X:不存在的

题解

E: 阴阳两种珠子的项链，给定若干个限制条件表示一个阴珠和哪几个阳珠相邻会变色，求最少有几个阴珠变色。————二分图匹配，枚举阳珠顺序，转化成最多能匹配几个阴珠，注意到环的不同排列数是(n-1)!，复杂度为O((n-1)!*n²)

F：（数论->欧拉函数），比较详细的推导见 https://blog.csdn.net/wust_zzwh/article/details/51966450

这题是两个问题的融合，一个是求/sum i=1~m phi(i*n)，其中n的所有质因子的幂都是1，另一个是求k的k的k的......次幂 %p的值，需要用到欧拉降幂公式，见BZOJ3884.

G：原题题意比较模糊，dp方程是dp[i]=/sum j=i~i dp[j]*a[i-j]，CDQ分治+FFT模板题，复杂度O(nloglogn)