第1届ICPC青少年程序设计竞赛C G 两题题解。
C.Chocolate Counting
给定质数 (p)（(pge 3)）与整数 (k)，求在 (1sim kp) 中选择 (p) 个互不相同的数，满足和为 (p) 的倍数的方案数。(p,kle 10^7)。
Solution
对于某些模质数 (p) 的余数相关的计数题，可以考虑将选择方案分组，满足每组中 (p) 个方案的结果模 (p)
将 (1sim kp) 放在一个 (p imes k) 的矩阵上，第 (i) 行依次放置 (i,i+p,i+2p,dots i+(k-1)p)。
考虑在矩阵上随机选择 高校acm基础java进阶试题 (p) 个数，如果这 (p) 个数恰好是同一列的 (p) 个数，那么它们直接合法。否则，考虑找到从左到右任意一个被选了数的列，将其上被选择的数循环移位，得到 (p) 个选择方案，那么显然有这 (p) 个选择方案 (mod p) 的余数恰好为 (0sim p-1)。
由此，可以将剩下的所有 (dbinom{pk}{p}-k) 中方案，(p) 个为一组分成若干组，每组中恰好有一个方案合法，因此这部分对答案的贡献就是 (dfrac{1}{p}(dbinom{pk}{p}-k))。
G.Dynamic Graph
给定一个 (n) 个点的无向图以及一个常数 (F)，一开始没有边。
你需要执行 (m)
操作有 (3)
: 在 (u) 和 (v) 之间加了一条权值为 (w)
: 删除第 (id)
: 询问是否存在一条权值和模 (F) 余 (w) 的从 (u) 到 (v)
(n,mle 10^5,Fle 10^9)。
Solution
经典套路：对于询问某个两个点之间是否存在路径权值 (mod F=w) 的问题。可以先取出两点之间任意一条路径，设长度为 (x)，求出两点所在连通块所有环长的 (gcd) 设为(G)，那么能取到 (w) 当且仅当 (wequiv kG+xpmod F(kin Z))。
对这个结论的证明也很简单，就是先取出任意一条路径，然后可以通过从某个点出发向环上任意一点来回走 (F)
那么对于原问题，我们首先通过线段树分治去掉删除操作。对于添加边 ((u,v,w)) 的操作，如果 (u,v) 在同一连通块中，设 (d_u,d_v) 分别为 (u,v) 到根的路径长，则更新该连通块最大公约数 (G=gcd(G,2w,w+d_u+d_v))。如果 (u,v) 不在同一连通块中，合并这两个连通块，新块的最大公约数 (G=gcd(G_1,G_2,2w))。
于是使用按秩合并并查集维护，复杂度为 (mathcal O(nlog ^2 n))（假设 (n,m)
讯享网
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/10114.html