NOIP集训-10.16总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
表示一直在做第三题，然后花五分钟写了第一题的70分，第二题看都没看，然而第三题还是没调出来...简直跪爽！
-------------------------------------------------------------------
1807:SuperOj931
SB DP..
-------------------------------------------------------------------
Minimum:SuperOj932
首先从每个白点开始，跑一次最短路，看哪些黑点是需要到达的，以及哪些边需要保留
这样就得到了一个森林，显然需要在其中选一些边，使得原来连通的依然连通
发现是MST，但是是个森林，不好搞
可以加一个超级节点，连向所有边，这样就搞成一个MST问题了...
-------------------------------------------------------------------
Gcd:SuperOj933
有意思的题，先说一下我考试时候的做法（后来调出来了，因常数太大而TLE..TAT）：
假设Si表示gcd为i的倍数的子集个数
这个可以通过枚举i的倍数求得
求出Si的时间复杂度是O(M/1 + M/2 + M/3 + ... + M/M) = O(M*ln(M)) (M为数组中最大数)
然后可以通过素数容斥求出gcd刚好为1的子集个数p:
p = Σ(i=1,M) miu(i)*Si
然后可以再用一次素数容斥求出答案，伪代码如下（已略去求模）:
（已预先排除集合中所有的1，并得到了1的个数num）
ans <- ((2^n - 1) - p) * num
for i ∈ a （这里及之后用∈符号表示i是数组a中的元素）
for j | i
ans <- ans + miu(j) * Sj
end
end
然后这个的时间复杂度是O(n*(M^0.5))的，在M=10^7,n=10^5这个数量级下和O(M*ln(M))差不多大
然后就T掉了...
标算：
发现答案就是:
总的方法数-Σ(gcd为1子集)（n-子集大小）-Σ(gcd不为1的子集)子集大小
设p = Σ(gcd不为1的子集)子集个数
q = Σ(gcd不为1的子集)子集大小
化简原式然后可以得到答案的表达式为:
2*q - n*p + n
接下来只需要求出p、q就可以了
可以用素数容斥：(假设Li表示i的倍数出现的个数)
p = Σ(i∈a) miu(i) * (2^(Li)-1)
q = Σ(i∈a) miu(i) * (Li* (2^(Li-1)))
然后这个算法的时间复杂度是O(n*ln(M))的，和上面那个复杂度一样，但是常数小一倍...
-------------------------------------------------------------------
评论 (0)
