湖北网站建站系统哪家好,大连企业建站,西安手机网站建设,安徽网站建设价格时间安排
7:30–7:50 看题#xff0c;T1,T2 感觉是同类型的题#xff0c;直接搜索状态然后 dp 一下#xff0c;T3 估计是个独角晒。 7:50–8:20 T3#xff0c;有 n^2 的式子#xff0c;然后可以优化到 n ,写暴力验证一下发现不对。很迷#xff0c;反复推了几遍都拍不上暴…时间安排
7:30–7:50 看题T1,T2 感觉是同类型的题直接搜索状态然后 dp 一下T3 估计是个独角晒。 7:50–8:20 T3有 n^2 的式子然后可以优化到 n ,写暴力验证一下发现不对。很迷反复推了几遍都拍不上暴力。扭头看 T1,T2 了。 8:20–10:20 T1,显然只需要知道相对大小就可以了搜索一下状态比较少那么 dp 一下就行了。有一个贡献不是很好求推了一阵子。 10:20–11:10 T2,和前几天 ZR 非常像。打 zr 的时候有一个想法 zr 那个版本做不了但是这道题明显比 zr 的那道若可以直接用之前的想法做。先写部分分状压一下状态数大概有 250 左右于是对于 m 小的时候暴力 dp 就行了。 11:10–11:40 T2意识到这玩意可以矩乘。于是就有 状态数^3log 的做法。不过我还没有去减状态有点卡。
回顾反思
T1: 这道题基本思想比较简单但是花费时间有点长了。 主要是因为推导一个式子 ∑aC(a,c)C(K−a,d)C(K1,cd1)\sum\limits_{a}C(a,c)C(K-a,d)C(K1,cd1)a∑C(a,c)C(K−a,d)C(K1,cd1) 拍了几组是没问题的。 于是就和 K 具体大小无关直接做了也没用到题解所说的拉格朗日插值。不过硬要上差值也是没问题的贡献是形如 C(K,n)C(K,n)C(K,n) 的形式是 n 次或者 n1 次多项式n比较小算几遍差值就行了。 T2: 基本思路没差。 但是我赛时没有尽可能地去减状态于是状态数比较大就 T 了。 具体地注意到答案只跟状态中若干段的长度有关那么只要存长度就行了进一步地这玩意和若干长度的顺序也无关对状态里的长度排一下序状态数会更少。 T3 赛时推导到某个地方卡住了。 主要是因为设 DDD 替换形如 ababab 的式子的时候忽略了 aaa 被 DDD 整除的条件也就是少了个整除号然后就错了。 赛时一直没发现于是耽误了时间也推不下去。 一定要注意。 然后就是独角晒求 id×ϕid \times \phiid×ϕ 的前缀和。 比较关键的点是 拿 III 卷一下于是 id×ϕ×Iid×id∑d∣ndndn⋅σ(n)id\times \phi \times I id\times id \sum\limits_{d|n} d\frac{n}{d}n\cdot \sigma(n)id×ϕ×Iid×idd∣n∑ddnn⋅σ(n) 其中 σ(n)\sigma(n)σ(n) 为 n 的约数个数。
