也许更好的阅读体验  文章目录  前置知识 定义 多项式的表示法  系数表示法 点值表示法  多项式的基本运算  加法 乘法  多项式的其它运算  基本套路 多项式求逆 多项式求ln 多项式exp 多项式开方    前置知识 FFT 牛顿迭代 求导  定义 简单来说，形如      a   0     x   0    +    a   1     x   1    +    a   2     x   2    +   ⋯   +    a   n     x   n     a_0x^0+a_1x^1+a_2x^2+\cdots+a_nx^n   a0​x0+a1​x1+a2​x2+⋯+a...

也许更好的阅读体验 这里不会详细讲导数，只贴最基本导数和有关多项式的导数 表示法       x   ′     x'   x′表示对     x    x   x进行     1    1   1阶求导       x    ′   ′      x''   x′′表示对     x    x   x进行     2    2   2阶求导      x    x   x上面有几个      ′     '   ′表示对     x    x   x进行几阶求导       x    (   i   )      x^{...

也许更好的阅读体验  文章目录  一般生成函数(OGF)  引入 定义 运算 个人理解  指数生成函数(EGF)  引入  带标号对象的拼接  定义 运算 个人理解  生成序列(seq) 生成集合(set)   一般生成函数(OGF) 引入 考虑一类组合对象组成的集合     A    A   A，其中：  每个元素     a   ∈   A    a\in A   a∈A都被定义了“大小”     ∣   a   ∣    |a|   ∣a∣，它是一个非负整数。 对于给定的     n    n   n，大小为     n    n   n的元素的数量是有限的，记作      A   n ...

也许更好的阅读体验  文章目录  泰勒(Taylor)公式  $e^x$的泰勒展开  牛顿迭代   泰勒(Taylor)公式       <mstyle displaystyle="true" scriptlevel="0">   f    (   x   )    =  <munderover>  ∑    i   =   0    ∞  </munderover>     f    (   i   )      (    x   0    )      i   !       (   x   −    x   0 ...

也许更好的阅读体验  文章目录  写在前面 后缀自动机的图的理解 构建自动机  约定  $right$集合  求$right$集合的大小 $right$集合的理解  后缀自动机的应用  判断是否是子串 不同子串个数 第K小子串 最小循环移位(最小表示法)     写在前面 本篇博客主要讲一些自己的理解，不喜勿喷 发现网上的博客关于     r   i   g   h   t    right   right集合只讲了如何做，没有讲清原因，于是和同学讨论了很久之后记录一下 如有没有看懂的地方或者错误的地方，欢迎提问或者指出 如有其它疑问也可提出，博主也会进行解答 本博客内容为对各种方法的理解与深...

也许更好的阅读体验  文章目录  前言 通项公式 负项数 有趣的东西   前言 考试的时候考了到斐波那契的题，于是咱自己推了一些好玩的东西，后来又听dalao讲了些感觉挺有用的东西 通项公式       f   0    =   0  <mtext>     </mtext>   f   1    =   1  <mtext>      </mtext>   f   2    =   1  <mtext>   </mtext>   f   n    =    f    n   −   1     +    f    n  ...

也许更好的阅读体验       D   e   s   c   r   i   p   t   i   o   n    \mathcal{Description}   Description 如标题 给一堆数，问其全排列有多少种 例 1 1 2 这三个数只有3种全排列 分别为      1  <mtext>   </mtext>  1  <mtext>   </mtext>  2   1  <mtext>   </mtext>  2  <mtext>   </mtext>  1   2  <...

也许更好的阅读体验      D   e   s   c   r   i   p   t   i   o   n    \mathcal{Description}   Description 给出一段环状序列，即认为      a   1     a_1   a1​和      a   n     a_n   an​​是相邻的，选出其中连续不重叠且非空的两段使得这两段和最大。       S   o   l   u   t   i   o   n    \mathcal{Solution}   Solution  思路 要求两个最大子段，考虑其与最大子段的关系  我们先把序列复制一遍，求出长度...

也许更好的阅读体验       D   e   s   c   r   i   p   t   i   o   n    \mathcal{Description}   Description 每天抛一个硬币，硬币正面朝上的几率是p，直到抛出k次正面为止结束，第     i    i   i天抛硬币的花费为     2   i   −   1    2i-1   2i−1，求出抛硬币的天数的期望和花费的期望。      S   o   l   u   t   i   o   n    \mathcal{Solution}   Solution 该题为双倍经验题，具体做法请看 收集邮票 (原谅我...

也许更好的阅读体验  文章目录  数学期望  符号 含义  转移方程 经典例题  SP1026FavoriteDice 涂格子/小孩和礼物 简单题 亚瑟王 抽卡 收集邮票 [POJ3682]King_Arthur's_Birthday_Celebration     数学期望 符号      E   =   p   ∗   v    E=p*v   E=p∗v 其中     E    E   E为期望，     v    v   v为权值，     p    p   p为概率 含义 期望表示多个可能事件的合理分配情况 (本人自己的理解，不喜勿喷) 汉语期望意思是指人们对某样东西的提前勾画出的一...

也许更好的阅读体验      D   e   s   c   r   i   p   t   i   o   n    \mathcal{Description}   Description 有     n    n   n种邮票，每天等概率的买一张邮票，第     i    i   i天购买要花费     i    i   i元，求收集     n    n   n种邮票的期望花费      S   o   l   u   t   i   o   n    \mathcal{Solution}   Solution 先设     f   [   i   ]    f[i]   f[i]表示买...

也许更好的阅读体验      D   e   s   c   r   i   p   t   i   o   n    \mathcal{Description}   Description 桌面上有R张红牌和B张黑牌，随机打乱顺序后放在桌面上，开始一张一张地翻牌，翻到红牌得到1美元，黑牌则付出1美元。可以随时停止翻牌，在最优策略下平均能得到多少钱。      S   o   l   u   t   i   o   n    \mathcal{Solution}   Solution 设     f   [   i   ]   [   j   ]    f[i][j]   f[i][j]表示有...

也许更好的阅读体验      D   e   s   c   r   i   p   t   i   o   n    \mathcal{Description}   Description 给出     n    n   n个技能，每个技能按输入顺序有     p   [   i   ]    p[i]   p[i]的概率释放并造成     d   [   i   ]    d[i]   d[i]的伤害。每轮游戏从前往后顺序查看每个技能，若技能发动过则跳过，没发动过则以     p   [   i   ]    p[i]   p[i]的技能发动，即每个技能只能发动一次，若将一个技能发动，则进...

也许更好的阅读体验      D   e   s   c   r   i   p   t   i   o   n    \mathcal{Description}   Description 有     n    n   n个格子，每次等概率随机给一个格子染色，问涂     m    m   m次后期望有多少格子被染色了      S   o   l   u   t   i   o   n    \mathcal{Solution}   Solution 设     f   [   i   ]    f[i]   f[i]表示涂     i    i   i次后期望有多少格子被染色了 现在进行...