Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom6月前

04/23
21:18
乱搞 期望动规 构造 离线 莫队算法

[czyz 2017.04.23 noip-省选 模拟赛]

http://czyzuoj.com/problem/92

http://czyzuoj.com/problem/93

http://czyzuoj.com/problem/94

A:

设f[i][j]为进行了前i轮,总和是j的期望人数,直接前缀和优化转移即可。

 

B:

可以把小于1000的质数和大于1000的质数分开来考虑

小于1000的质数只有168个,计算出前n个数每个质因数个数的前缀和,然后询问的时候直接枚举每个质因数快速幂计算答案即可。

对于大于1000的质数,每个数只可能有一个这样的质因数,直接莫队合并即可。

复杂度 O(n sqrt(n) + n sqrt(v) / logv * log(n log n)) (后面的鬼畜复杂度大概就是 n sqrt(v)吧)

做题的时候评测姬比较慢顺带卡了卡常

 

C:

对于每个奇置换,我们可以直接构造出 f[i] = i + ((tot + 1) >> 1) 来解决

对于2个长度相等的偶置换,我们可以在两个中间随便连

否则就是不可行

 

[czyz 2017.04.23 noip-省选 模拟赛]