当前位置: 首页 > news >正文

计数(5):多项式相关

计数中我目前只见过两类与多项式相关的问题,一类是采用 gf 来刻画,一类是用拉插来优化掉 dp 的很大一个维度,还有一类就是神秘多项式问题,但是考虑 fft 已经被 cnoi 除名了所以我就不学了(

这部分写的非常浅显,我本身的多项式水平是负数,如果大家有题目推荐欢迎狠狠地踹主包的说。


拉格朗日插值法

想到一个很有意思的事情,我第一次见到拉格朗日插值法被名字吓跑了,后来有一天看到老高中数学课本,看到 CRT 居然有用拉格朗日插值法的理解,然后就去写板子了。

基本形式

给定 \(n\) 个点 \((x_1, y_1)\sim (x_n, y_n)\),求一个 $(n - 1) $ 次经过所有点的多项式中 \(x = k\) 的函数值。

无脑的做法是高斯消元求解系数。

但是注意到我们并不在乎系数只在乎求值。因此有:

\[f(k) = \sum\limits_{i = 1}^n y_i\prod_{j \not= i}\dfrac{k - x_j}{x_i - x_j} \]

感性认知一下:我们给每个 \(y\) 配上一个系数,对于 \(x_i\) 那么 \(y_i\) 系数为 \(1\),否则为 \(0\)。因此将 \(x_i\) 带入进来的时候我们希望首先 \(j\not= i\),其次总是有分子分母相等,同样的如果 \(x_i\) 与这一项不相等那么就等于 \(0\)。得到系数 \(\prod\limits_{j \not = i}\dfrac{k - x_j}{x_i - x_j}\)


拓展

值域连续时

\(x_i\) 的值域连续时,以 \(x_i\)\(1\sim n\) 为例,此时:

\[f(k) = \sum\limits_{i = 1}^n y_i\prod\limits_{j \not= i}\dfrac{(k - j)}{i - j} \\ = \sum\limits_{i = 1}^n y_i \dfrac{\frac{(k - 1)^{\underline{n}}}{k - i}}{(i-1)!(-1)^{\underline{n - i}}} \]

必须注意的是,\(k\le n\) 时,\((k - 1)^{\underline{n}}\) 可能等于 \(0\) 要特判!

预处理一些阶乘即可。

重心拉格朗日插值

有的时候我们要对单点 \(k\) 求取值,但是点会不断增加。

变换式子:

\[w = \prod\limits_{j = 1}^n (k - x_j)\\f(k) = w\sum\limits_{i = 1}^n \dfrac{1}{k - x_i}\prod\limits_{j \not =i}^n\dfrac{y_i}{x_j - x_i} \]

那么令 \(t_i = \prod\limits_{j \not= i}\dfrac{y_i}{x_j - x_i}\),新加入一个点只需要对所有 \(t_i\) 进行更新,计算新的 \(t_n\)\(w\),最后计算贡献。加入一个点的代价是 \(O(n)\) 的。


例题

AT_abc208_f

关键是要注意到组合数也可以看作是多项式,后面忘了

题解 https://www.luogu.com.cn/article/95bxguv3

P8290

我被卡常了。

首先考虑暴力,最大值与最小值的差很难做,考虑钦定范围在 \([L, R]\) 内其中 \(R - L = k\)。这样会算重,常见的套路是钦定端点被选择,比如这里我们再减去 \([L+1, R]\) 的情况即可。那么每个点能选择的就是 \([l_i, r_i]\cap [L, R]\) 这个区间。第一问直接 dp,第二问要做一个换根,对于一个区间可以 \(O(n)\) 求。最终时间复杂度是 \(O(nV)\) 的。现在考虑优化。首先如果我们将 \(l_i - 1, l_i, r_i, r_i+1\) 这些可能的端点离散化,那么两个端点之间的情况显然是相同的,要么然完全包含,要么然是与 \(l_i, r_i\) 形成一次函数,总共乘起来是 \((n+1)\) 次的函数,最后再做前缀和就是 \((n+2)\) 次函数,要枚举前 \((n+3)\) 项算前缀和。拉差即可,时间复杂度 \(O(n^3)\)

P3270

当时应该是省选之前和 yzy 一起看的这题,我俩当时怎么都不会啊,暴力都不会。

为了方便下问认为 \(n \gets n - 1, R_i = n - R_i + 1\)

注意到直接约束“恰好 \(K\) 个人全部科目小于等于 B 的”很难做,所以考虑容斥,钦定有 \(x\) 个人被吊打了就很容易了。这是一个明显的二项式反演的形式,\(g(x)\) 为钦定 \(x\) 个人被碾压了,那么就有:

\[g(x) = \binom{n}{x}\prod\limits_{i = 1}^m(\sum\limits_{t = 1}^{U_i}\binom{n - x}{R_i - x}t^{R_i}(U_i - t)^{n - R_i})\\ f(K) = \sum\limits_{i = K}^n (-1)^{i - K}\binom{i}{K}g(i) \]

瓶颈在于快速计算 \(\sum\limits_{t=1}^{U_i}t^{R_i}(U_i - t)^{n - R_i}\),拉插即可。


生成函数相关

形式幂级数也是幂级哈!

利用形式幂级数分析问题,而不是使用多项式科技

P5333

这也太难了

不会,我学。

首先考虑刻画哈密尔顿回路,通过手玩不难发现,本质上是将这些树分别剖成若干条不交链,哈密尔顿回路可以看作这些链的拼接,要求:

  1. 相邻的两条链来自不同树。
  2. 第一条链必须来自第一棵树,并且必须包含 \(1\) 点。
  3. 最后一条链必须不来自第一棵树。

假设已经钦定了链的剖分方式,如果一条链大小大于 \(1\) 那么产生 \(2\) 方案,否则只产生 \(1\) 方案。设 \(f[i, j]\) 代表第 \(i\) 棵树剖分成 \(j\) 条链的权和,若钦定了 \(j_1, j_2, \dots, j_m\),那么总权和就是 \(\prod_{i = 1}^n f[i, j_i]\)。那么只需要计算链的排列方式。

首先考虑第一条约束。

考虑容斥。独立考虑一棵树的影响,对于树 \(i\),剖分成 \(j\) 条链,钦定其中有 \(k\) 个位置最后相邻,容斥系数则为 \((-1)^k\),排列一共应当由 \(j!\binom{j - 1}{k}\) 中选择方法。于是我们得到了新的 \(x^{j - k}\) 条链。最后我们是按照这个 \((j - k)\) 之和相关计算答案的,不难想到构造出 egf:

\[G_{i} = \sum\limits_{j = 0}f[i, j]j!\sum\limits_{k = 0}^j\binom{j - 1}{k}(-1)^k\dfrac{x^{j - k}}{(j - k)!} \]

如果没有别的约束,将 \(G_i\) 全部相乘计算每一项系数即可。

对于第二条约束,强制第一条链,注意,链内部只要将 \(j!\) 改成 \((j - 1!)!\) 代表第一条链固定,即可,合并链的形式幂级数则要去掉这条链。即 \(G_1\) 变成:

\[G_1 = \sum\limits_{j = 1}f[1, j](j - 1)!\sum\limits_{k = 0}^j\binom{j - 1}{k}(-1)^k\dfrac{x^{j - k - 1}}{(j - k - 1)!} \]

即可。

对于第三条约束,我们正难则反,减去不合法,即对于第一棵树强制第一条链和最后一条链。注意,最后一条链是任选的,所以 \((j - 1)!\) 仍然不变,代表钦定了第一条,剩下任意选,最后还剩下一个不准动。唯一的修改也是在最后的形式幂级数中:

\[G_1 = \sum\limits_{j = 1}f[1, j](j - 1)!\sum\limits_{k = 0}^j\binom{j - 1}{k}(-1)^k\dfrac{x^{j - k - 2}}{(j - k - 2)!} \]

计算答案全部卷起来就行了。时间复杂度 \(O(\sum\limits k^2)\)


接下来三题都是形如:\(K\) 次操作取反之类的问题,前两个问题我们都采用生成函数刻画,但是最后一个问题并不采用这个方法而是直接考虑集合幂级数卷积。一方面是最后一道题用生成函数推导有点太困难了我还不会 QAQ,一方面也是提个醒不要被生成函数卷积给局限住啦。

zr3272

\(n\) 个点的树,每条边拥有权 \(p_i\) 与存在状况 \(c_i\)。无形的大手子进行了 \(K\) 次操作,每次有 \(\dfrac{p_i}{\sum_{j = 1}^{n-1}p_j}\) 取反 \(i\) 这条边的存在状况。求最终树上联通块大小乘积的期望。

猫生首次见到这种问题,猫很震撼!令 \(S = \sum\limits p\),接下来我们默认 \(S^{K}\) 最后除以。

首先考虑已知每条边存在情况计算概率。因为每个边有可能被取反多次,最后操作数量和为 \(K\),并不好直接刻画,所以我们采用 egf,这样卷积的过程天然为我们做好了这个背包。

对于第 \(i\) 条边,它取反情况记作 \(G_{i, 1}\),未被取反的情况记作 \(G_{i, 1}\),那么有:

\[G_1 = \dfrac{e^{px} - e^{-px}}{2}\\G_0 = \dfrac{e^{px} +e^{-px}}{2} \]

盘面的 egf 为所有 \(G\) 的乘积 \(F\),那么最终概率为 \(K![x^K]F\)。令 \(F = \sum\limits_{i\in [-S, S]} c_ie^{ix}\),那么有:

\[K![x^K]F = \sum\limits_{i\in [-S, S]} c_ii^K \]

维护 \(c_i\) 即可。

回到题目当中来,树形 dp 合并子树的时候考虑 \(u-v\) 选择哪一个 gf,重点在于我们无法轻易的维护“联通块乘积”这一个信息。使用组合意义,联通块乘积看作联通块内部选一个点方案数。这个可以增量计算,设 \(f[u, i, 0/1]\) 代表 \(u\) 所在联通块选/没选,当前维护的系数为 \(c_i\) 的系数只和。直接转移即可。

AT_abc231_g

离开事件发生独立性谈论期望的可乘性是无稽之谈。用生成函数刻画。

建立一个 gf,\([x^k]G_i(x)\) 代表 \(i\) 位置选中了 \(k\) 次的期望,也就是 \((a_i+k)\dfrac{1}{n^k}\)。外面套上 egf 计算可重集合,最后相乘卷积起来即可。

具体而言对于每个 \(i\) 的 ogf 为 \(G_i(x) = \sum\limits_{m = 0}{(a_i+{m})\dfrac{(\frac{x}{n})^m}{m!}}\)。最后计算 \(n![x^k]\prod_{i = 1}^nG_i(x)\) 即可。\(k\) 很大所以没有什么直接卷积的余地。考虑求出封闭形式后直接计算。

\[G_i(x)=a_i\sum\limits_{m = 0}\dfrac{(\frac{x}{n})^m}{m!} + \sum\limits_{m=1}\dfrac{(\frac{x}{n})^m}{(m-1)!}\\=a_ie^{\frac{x}{n}}+\dfrac{x}{n}e^{\frac{x}{n}} \]

注意到 \(\frac{x}{n}e^{\frac{x}{n}}\) 看上去很难维护,但是对于每个 \(i\) 都有这一项,所以可以直接枚举乘积中选了多少项这个。考虑计算答案的贡献形式,答案形式为 \(t(\frac{x}{n}e^{\frac{x}{n}})^me^{\frac{(n-m)}{n}x}\),展开计算一下:

\[t(\frac{x}{n}e^{\frac{x}{n}})^me^{(n-m)x} = t\dfrac{x^m}{n^m}e^{x}\\ = \dfrac{t}{n^m}\sum\limits_{i=0}\dfrac{x^{m+i}}{i!} \]

故第 \(k\)\(\dfrac{tk!}{n^m(k-m)!}\)。对于相同 \(m\) 记录 \(t\) 和即可。直接 dp 即可。

http://www.hskmm.com/?act=detail&tid=21568

相关文章:

  • 最新WTAPI开发微信机器人教程说明
  • 线性DP - 学习笔记
  • 2025 年最新制氮机厂家权威推荐排行榜:聚焦行业优质厂商综合实力,助力企业精准选购优质设备制氮机产生氮气/氮气纯化/设备改造/维修/保养/半导体用制氮机厂家推荐
  • 2025 年氨分解设备厂家最新推荐榜单:含半导体 / 冶金 / 稀土行业专用设备及品牌综合实力排名
  • 2025 阳台装修公司推荐榜:最新优质厂商资质 / 技术 / 服务测评,杭州浙江地区优选指南杭州阳台装修/浙江阳台装修公司推荐
  • bitset
  • 网易雷火胡志鹏:AI驱动未来,游戏科技重塑虚拟创造力与现实生产力
  • idea打包推送maven仓库及同时推送到不同的maven仓库,本地和云上的腾讯云
  • 2025 阳台柜厂家最新推荐榜:企业资质 / 材质 / 服务全景解析,选对品牌少走弯路杭州阳台柜/浙江阳台柜厂家推荐
  • 2025 年除湿机厂家最新权威推荐排行榜:实力厂家技术口碑评测及场景适配选购指南吊顶/泳池/车库/防爆/调温/新风除湿机厂家推荐
  • 2025 年液氨蒸发器厂家联系方式,众众电热:多领域加热设备供应与定制化解决方案提供商
  • 【Batch】批量修改文件后缀
  • 【solace】基于docker部署solace环境
  • 2025 年阿里巴巴开通实力商家店铺开通代运营 / 阿里巴巴新手开店全托管代运营公司推荐:南鑫粤网络 —— 全域运营解决方案与实战服务优势解析
  • Vue-element-admin开发指南 - 教程
  • 2025 年国内工作服厂家最新推荐排行榜:聚焦工艺设计与服务,精选权威榜单助企业采购冬季/春季/工人/车间/防静电/餐饮/劳保工作服厂家推荐
  • ClickHouse 窗口函数使用详解(一) - 若
  • ClickHouse 窗口函数详解:告别 GROUP BY 的局限性,实现灵活数据分析 - 若
  • 简单WEB网站
  • AtCoder AGC044 总结
  • UOJ#32【UR #2】跳蚤公路 题解
  • 2025 年窗帘杆源头厂家最新推荐榜单:包含支架 / 环 / 全自动 / 可伸缩等多类产品及配件,帮助选到品质与交期双优的优质厂家
  • 2025 年电动窗帘厂家推荐榜单:聚焦国内优质企业定制实力与口碑,为采购者提供最新选择参考电动窗帘系统/电机/轨道/配件/智能电动窗帘厂家推荐
  • Vue3 使用注意事项
  • ClickHouse ReplacingMergeTree 去重陷阱:为什么你的 FINAL 查询无效? - 若
  • js中?? 和 || 的区别详解
  • 微信机器人API接口| 个人开发者必备
  • 直击现场! “ 直通乌镇 ”开源赛复赛收官,OpenCSG担任评委,十强藏着哪些产业机会?
  • Python 列表生成式、字典生成式与生成器表达式
  • java 解析json字符串,获取特定的字段值,JsonObject