浅谈基于转置原理的多项式多点求值算法

考虑一个经典的问题。给定 $n$ 次多项式

和 $n+1$ 个点值 $a_0,a_1,\dots,a_n$。您需要对于每个 $k$,求出 $b_k=F(a_k)$,对 $998244353$ 取模。

据说以前这种问题都是采用多项式取模的方法。但是现在我们有新科技了。

本篇文章将会以我个人认为十分通俗易懂的方式来详细地讲解这种新科技。

参考文献略。

阅读更多

ICPC 2022 Regional 合肥站游记

今天本来会有一场大物的考试。还好我因为打 ICPC 申请了免考不然就要在大物考场上丢人了。

前 3h 写出来 6 题。最后 2h 我在写一道数学题,SHX 在写一道数据结构题,结果都没有写出来。

本来以为写出来 7-8 题可以混一块金牌的。结果赛后一查排行榜,8 题 42 队,7 题 67 队,结果金牌只有 35 块。

也就是说无论如何都没有大金牌了 /kk

最后 rank 72 拿了一块银牌。

这么说来上周的 CCPC 其实是最有希望拿金牌的。如果我能够少浪费一时间的话。

害群之马竟是我自己 /kk

阅读更多

随笔题解 Pb. 5

2022 年 10 月 17 日 22:35 ~ 次日 00:35,AHU 2021 届不知名 ACM 选手関原みや(化名)报名参加 Educational Codeforces Round 137 (Rated for Div. 2)。期间因急了,C 题 WA 1 发,(某数据随机复杂度虚伪的)D 题 WA 4 发;但最后关头潜力爆发,做出 F 题并成功上分,跻身 Candidate Master 之列。距今已过……不知道多久,佳话永流传。

来源:CF1743 F Intersection and Union

阅读更多

随笔题解 Pb. 4

2022 年 10 月 1 日 20:00 ~ 21:40,AHU 2021 届不知名 ACM 选手関原みや(化名)报名参加 AtCoder Beginner Contest 271。期间因大脑短路,A/D/E 题各 WA 1 发,C 题 WA 4 发,G 题本应做出却未能做出(F 题就算了,真不会),最终以 1075th 的坏成绩遗憾离世离场,Rating 倒扣 17 分。距今已过 34 分 24 秒,警钟长鸣。

来源:ABC271 G Access Counter

阅读更多

随笔题解 Ct. 4

第一次试图在实验室过夜并打 Codeforces Global Round。

d*m「听上去很容易下分的样子。」

85 min 写出来四题我觉得已经可以开香槟了。这波上大分。

于是从考场偷偷溜出来写一写题解(

用户名 CLT,如果想要 AC 代码请去 CF 翻提交记录。(考场代码,不保证可读性)

阅读更多

随笔题解 Ct. 3

今天 ACM 实验室的一场原题大赛。

把其中一些觉得稍微有点意思的题跳了出来写一写题解。

今日题源 :

  • A: 1426A (*800)
  • B1: 1560F1 (*1900)
  • B2: 1560F2 (*2100)
  • C: 1509B (*1100)
  • D: 1295E (*2200)
  • E: 1608B (*1200)
  • F: 1612D (*1600)
  • G: 1624D (*1400)
  • H: 1495C (*2300)
  • I: 771A (*1500)
  • J: 583A (*1000)

差点就 AK 了。以及被三队暴打。

阅读更多

你解锁了『牺牲者污化以撒』

英文原文是 “Sacrifice”,为了匹配堕化角色解锁成就的命名格式(比如堕化以撒解锁成就 “Broken” 被译为「神伤者」)而译为「牺牲者」。

解锁方式:使用堕化以撒击败精神错乱。

初始基础属性和以撒完全相同;自带一个炸弹;自带次要主动道具 Blighted Dice

阅读更多