2017 Multi-University Training Contest - Team 5
1001 - Rikka with Candies
题意
给定长为n的序列A和长为m的序列B，(n <= 50000，m<=50000)，和q(q<=50000)个询问，每次给定k，询问有多少对(i, j)满足A_i % B_j = k，(1<=i<=n,1<=j<=m,B_j>k)，输出数量%2的值。
题解
- 问题等价于求(A_i - k) % B_j = 0的对数，那么我们可以从大到小枚举B_j，每次更新其倍数x，令f[x]表示有多少个B_j是其因子，那么我们只需要对每个A_i，令ans += f[A_i-k]，在更新前对k进行求解，这样保证了每个x得来的贡献都是满足要求的。
- 考虑到只需要判断奇偶性，使用bitset来优化，对每一个i，枚举其倍数，复杂度是O(nlogn)，对k求解是$O(\frac{n^2}{32})$。
代码
|
|
1002 - Rikka with String
题意
有多少个长为2L的串S，包含给定的n个子串，且满足S[i]≠S[|S|−i+1]
- 1≤n≤6,1≤L≤100,1≤|si|≤20
题解
- 把n个串和n个串反转后加入AC自动机。
- 考虑dp[i][j][s]表示前i个字符中，当前在AC自动机的状态为j，且包含给定n个串的状态为s的方案数。
- 但是在L和L+1突然连起来的地方会形成新的串，那么暴力枚举哪些状态在L和L+1的地方连起来后会形成给定的串，也把这些子串加入AC自动机，所以ac自动机要设置两个val值，且其中一个val值在i==L的时候才有效。
代码
|
|
1004 - Rikka with Candies
题意
Alice和Bob玩石头剪刀布，每个人都是随机出石头或者剪刀或者步，三者概率相同，总共玩n局游戏，如果最后Alice赢a场，Bob赢b场，那么这局游戏的分数s是gcd(a, b)，求$s * 3^{2n}$的期望值。
题解
- Alice赢a场，Bob赢b场的期望值是${n \choose a} * {n-a \choose b} * 3^n$，那么$$ans = 3^n * \sum_{i=0}^{n} \sum_{j=0}^{n-i} {n \choose a} * {n-a \choose b} * gcd(i, j) $$
- $$= 3^n * \sum_{i=0}^{n} \sum_{j=0}^{n-i} {n \choose a} * {n-a \choose b} * \sum_{d|gcd(i,j)} {φ(d)}$$
- 交换求和顺序我们得到$$ans = 3^n * \sum_{d=0}^{n} φ(d)\sum_{i=0}^{\frac{n}{d}} \sum_{j=0}^{\frac{n}{d}-i} {n \choose id} * {n-id \choose jd}$$
- $$ = \frac{3^n}{n!} * \sum_{d=1}^{n} φ(d)\sum_{i=0}^{\frac{n}{d}} \frac{1}{(n-id)!} \sum_{j=0}^{i} \frac{1}{(jd)!} * \frac{1}{((i-j)d)!}$$
- 注意到后面的求和是一个卷积，使用FFT进行优化，那么总复杂度就是$\sum_{i=1}^{n}O(\frac{n}{i}logn) = O(n{logn}^2)$,上面的分析过程多考虑了i和j同时为0的情况，最后需要减去多余的φ(d)，对于任意质数为模数的FFT需要考虑到实现时的效率，而且在次数界很小时直接暴力求卷积是更优的。
代码
|
|
1007 - Rikka with Match
题意
给一颗树，去掉树上的一些边后求最大匹配，问有多少种去边方法使得最大匹配数是m的倍数（包括0）。
题解
- 树形dp。
- 设两个数组f[i][j]和g[i][j],f[i][j]表示i节点与其某一个子节点存在一条在最大匹配中的边，j表示该最大匹配模以m后为j。
g[i][j]表示i节点与其任意一个子节点不存在一条在最大匹配中的边，j表示该最大匹配模以m后为j。- 那么假设f[i][j]和g[i]j都已经求得，有一颗子树k，f[k][j]和g[k][j]也已经求得。现在将子树K加到i节点下方成为i节点的子节点。那么变换后的f'[i][j]和g'[i][j]可以通过地推式得到:
f'[i][(j+l+1)%m] += f[i][j] * (f[k][l] + g[k][l]) * 2 + g[i][j] * g[k][l]
g'[i][(j+l)%m] += g[i][j] * (f[k][l] + g[k][l]) + g[i][j] * f[k][l]- 可以这样理解，先算f'[i][j]。如果i和k之间的边是去掉的边，那么增加的个数就是f[i][j]*(g[k][l] + f[k][l])。
- 如果不是去掉的边，分两种情况考虑。Ik是最大匹配中的边，那么原来i节点没有最大匹配中的边，原来k节点也要没有最大匹配中的边，所以增加的个数是g[i][j]*g[k][l]。
- 最后ik不是最大匹配中的边所以增加了f[i][j]*(g[k][l]+f[k][l])。再算g'[i][j]。如果ik之间的边是去掉的，那么增加的个数是g[i][j]*(f[k][l]+g[k][l])。如果ik之间的边没有去掉，为了使这条边不是最大匹配中的边k节点就要已经是最大匹配中的点，所以增加的个数是g[i][j]*f[k][l]。
代码
|
|