Q779的博客

洛谷P10143 [WC2024] 代码堵塞题解题目链接：P10143 [WC2024] 代码堵塞题意：小 $\beth$ 为了纪念停办的 codejam，准备了一场“代码堵塞纪念赛”。小 $\beth$ 的朋友小 $\mho$ 也

2024-02-06 OI

算法 DP

升幂引理发现自己居然没有写过升幂引理的东西。因为证明比较简单，所以本文就不写了，想知道就看参考文献[1]吧。以下设 $p$ 为质数，令 $x,y$ 为满足 $p \not\mid x$ 且 $p \not\mid y$ 的整数，且 $

2024-02-06 OI

数学

洛谷P4725 【模板】多项式对数函数（多项式 ln）题解题目链接：P4725 【模板】多项式对数函数（多项式 ln）题意：给出 $n-1$ 次多项式 $A(x)$，求一个 $\bmod{\:x^n}$ 下的多项式 $B(x)$，满

2024-02-06 OI

算法数学多项式

洛谷P4512 【模板】多项式除法题解题目链接：P4512 【模板】多项式除法题意：给定一个 $n$ 次多项式 $F(x)$ 和一个 $m$ 次多项式 $G(x)$ ，请求出多项式 $Q(x)$, $R(x)$，满足以下条件：

2024-02-05 OI

算法数学多项式

洛谷P5205 【模板】多项式开根题解题目链接：P5205 【模板】多项式开根题意：给定一个 $n-1$ 次多项式 $A(x)$，求一个在 ${} \bmod x^n$ 意义下的多项式 $B(x)$，使得 $B^2(x) \equi

2024-02-04 OI

算法数学多项式

洛谷P4238 【模板】多项式乘法逆题解题目链接：P4238 【模板】多项式乘法逆题意：给定一个多项式 $F(x)$ ，请求出一个多项式 $G(x)$，满足 $F(x) \cdot G(x) \equiv 1 \pmod{x^n}

2024-02-04 OI

算法数学多项式

多项式初等函数本文主要介绍多项式的初等函数的定义以及在 OI 中如何求解。注意，多项式的初等函数一般定义在模 $x^n$ 意义下，但是在 OI 中，多项式系数通常还需要另外模一下 $p$ 。友情提醒：多项式模板题里的 $n$

2024-02-04 OI

算法数学总结多项式咕咕

洛谷P4921 [MtOI2018] 情侣？给我烧了！题解题目链接：P4921 [MtOI2018] 情侣？给我烧了！题意：有 $n$ 对情侣来到电影院观看电影。在电影院，恰好留有 $n$ 排座位，每排包含 $2$ 个座位，共 $2

2024-02-03 OI

算法数学 DP

小蓝书 16.3 题解传送门：小蓝书16.3 例题例1求解下列递推式的通项 a_0=-1,~a_1=1 \\[6pt]a_n=2 a_{n-1}+3 a_{n-2}+3^n,~n>1解：记 $F(x)=\sum_{n=0}^{\inf

2024-02-02 OI

数学生成函数咕咕

洛谷P2012 拯救世界2 题解题目链接：P2012 拯救世界2 题意：经过 12 年的韬光养晦，世界末日再次来临（众人：什么鬼逻辑……）。这次，小a 和 uim 已经做好了一切准备，顺利召唤出了 kkksc03 大神和 lzn 大神

2024-02-02 OI

算法数学卡常生成函数

洛谷P2001 硬币的面值题解题目链接：P2001 硬币的面值题意：小 A 有 $n$ 种硬币，现在要买一样不超过 $m$ 元的商品，他不想得到找钱（多脏啊），同时又不想带太多的硬币，且硬币可以重复，现在已知这 $n$ 种硬币的价值

2024-02-01 OI

算法数学

拉格朗日反演注意，本文不是 _拉格朗日定理_ 。复合与复合逆定义：形式幂级数 $F(w) = \sum_{n \ge 0}f_nw^n$ 和 $G(x) = \sum_{n \ge 1} g_nx^n$ 的复合为 F(G(x)) =

2024-02-01 OI

数学生成函数