主要思路
佛了。
让 \(p\) 跟 \(10\) 取个 \(\gcd\)。如果互质的话就是数数列 \(a_i = \text{从 i 到 n 表示的数字} \bmod p\) 区间里的同色对数,用莫队搞即可;如果是 \(2\) 那就把 \(0, 2, 4, 6, 8\) 这些尾数染颜色然后数同色对数,这个可以 \(\Theta(n)\),如果是 \(5\) 那就把 \(0, 5\) 染色即可。
Continue reading →佛了。
让 \(p\) 跟 \(10\) 取个 \(\gcd\)。如果互质的话就是数数列 \(a_i = \text{从 i 到 n 表示的数字} \bmod p\) 区间里的同色对数,用莫队搞即可;如果是 \(2\) 那就把 \(0, 2, 4, 6, 8\) 这些尾数染颜色然后数同色对数,这个可以 \(\Theta(n)\),如果是 \(5\) 那就把 \(0, 5\) 染色即可。
Continue reading →一眼可以看出一个 \(\Theta(n^3)\) 的 DP。其实用双带权二分就可以用 \(\Theta(n \log^2 n)\) 的时间搞了,但是我没写这个写法。
考虑一下被选择时的贡献。\(p_a, p_b\) 是单元贡献,考虑同时被选的贡献 \(1 – (1 – p_a)(1 – p_b) = p_a + p_b – p_a p_b\)。所以我们可以考虑最大费用最大流,来算这个式子。
需要注意的是,我们需要保证每一次代价都是正的,因为我们其实并不需要最大流,而只是相对的最大费用。
Continue reading →