Educational Codeforces Round 121

發表於 更新於 分類於 ， Disqus： 文章字數： 693 所需閱讀時間 ≈ 2 分鐘
F(LCM)

CF tracker

Edu List

https://codeforces.com/contest/1626

F. A Random Code Problem

给长度n的数组a

执行k次i=1..k

每次随机取下标idx,

ans+=a[idx]

a[idx] -= (a[idx] % i)

求 ans的期望, mod998244353

范围

n 1e7

1 <= a[0],x,y < M <= 998244353

1 <= k <= 17

a[i] = (a[i-1] * x + y)%M

3s

512mb

我的思路

这个操作就是 a[idx]变成贡献, 然后a[idx]变成不大于它的最大的i的倍数

这好几个神奇的地方, 首先n很大, 数组都是通过 递推式子给的, 这个递推式如果M小还有周期, 如果M大,不太知道怎么用

然后这个k <= 17 真的很小, 小到 甚至在想 bitmask

f[index][bitmask] = 贡献, 虽然这个状态大小都接受不了

但注意到第一次 的期望就是所有的平均数,

第二次也是, 当第二次选的偶数时, 那么第三次也是, 当第二次选的奇数时, 第三次 = 所有平均数 - 1/n

所以 经过第 i 轮 损失的量的 期望如果能算的话, 也是一个角度

算了下lcm(1…17) = 12252240, 也不小

而且 分支变化 状态也多

要快速计算 a[j] 可以用矩阵乘法, 但是 又要mod 又要加法, 算和也不知道怎么搞, 所以应该直接暴力掉?

12252240 似乎也可以, 每次相当于 n种操作, 那么就是所有 产生n 分, 第i份 处理i

只是在统计上,把它们加在一起, 这样每次 每个产生 1份处理的 和 n-1份没被处理的

r[i][w] += r[i-1][w]*(n-1)

r[i][next(w)] += r[i-1][w]

处理后的一定不大于当前的, 所以可以从大到小滚动掉,

所以可以滚动掉, 大概 O(k lcm(1…k)) ? 能过吗?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import math

def f(l,r):
    s = 1
    for i in range(l,r+1):
        s=math.lcm(i,s)
    return s

for i in range(1,17+1):
    print(i, f(i,17))

1 12252240
2 12252240
3 12252240
4 12252240
5 12252240
6 12252240
7 12252240
8 12252240
9 12252240
10 4084080
11 4084080
12 371280
13 371280
14 28560
15 4080
16 272
17 17

题解

还真是这样, 问题在于我想多了, 17并不需要, 因为17虽然改变, 但是贡献是由16决定的

所以 lcm(1..16) = 720720 就相当的小了

就随便做了

总结

试了一下, 看来补atcoder和补cf还是开vp补 比较好, 这场VP了

E 没有在时间内写出来, 翻来覆去才写出, 花了接近1.5h, 还是应该想清楚所有情况才写,不要想一半写一半

F 细节想得有问题, 但总体的思路没问题

然后1e7 果然 for还是随便for的, 不直接给, 估计是因为read慢

参考

官方