首页 > 其他分享 >P6667 [清华集训2016] 如何优雅地求和

P6667 [清华集训2016] 如何优雅地求和

时间:2024-01-16 20:12:37浏览次数:38  
标签:begin 2016 end limits mathscr sum aligned P6667 集训

P6667 [清华集训2016] 如何优雅地求和

Problem

给定最高次幂为 \(x^{m}\) 的多项式函数 \(g(x)\) 和整数 \(n, q\),其中 \(g\) 以点值形式给出,即给定 \(g(0), g(1), \dots, g(m)\)。求:

\[\begin{aligned} Q(g, n, q) = \sum\limits_{k = 0}^{n}g(k)\binom{n}{k}q^{k}(1 - q)^{n - k} \\ \end{aligned} \]

对 \(998244353\) 取模的结果。

\(1 \le n \le 10^{9}\),\(1 \le m \le 2 \times 10^{4}\),\(0 \le g(i), q < 998244353\)。

Solution

前提紧要:如何优雅地排序。你应该能猜到发生了什么。干脆一鼓作气把这道题扬了。

还是先来确定 \(a\)、\(F(x)\) 和 \(G(x)\)。

\[\begin{aligned} Ans = \sum\limits_{i = 0}^{m}a_{i}[x^{i}]F(G(x)) = \sum\limits_{k = 0}^{n}f_{k}\sum\limits_{i = 0}^{m}a_{i}[x^{i}]G(x)^{k} = \sum\limits_{k = 0}^{n}g(k)\binom{n}{k}q^{k}(1 - q)^{n - k} \end{aligned} \]

我们已知 \(g(0), g(1), \dots, g(m)\),又根据上面的等式,考虑将 \(g\) 的 \(m + 1\) 个点值与 Binomial Sum 标准形式中作为条件的 \(m + 1\) 和式进行关联,即:

\[\begin{aligned} g(k) = \sum\limits_{i = 0}^{m}a_{i}[x^{i}]G(x)^{k} \\ \end{aligned} \]

这样可以同时得到 \(f_{k} = \binom{n}{k}q^{k}(1 - q)^{n - k}\)。于是得到 \(F(x)\):

\[\begin{aligned} F(x) = \sum\limits_{k = 0}^{n}\binom{n}{k}q^{k}(1 - q)^{n - k}x^{k} = (qx + 1 - q)^{n} \\ \end{aligned} \]

接下来是 \(a\) 和 \(G(x)\),可以发现它们是绑定在一起的。

通过展开 \(g(x) = \sum\limits_{i = 0}^{m}g_{i}x^{i}\),我们可以看到这一点:

\[\begin{aligned} g(k) = \sum\limits_{i = 0}^{m}a_{i}[x^{i}]G(x)^{k} = \sum\limits_{i = 0}^{m}g_{i}k^{i} \\ \end{aligned} \]

这里 \(k^{i}\) 又出现了,于是 \(G(x)\) 还是我们的老伙计 \(e^{x}\),不过这一次它扔掉了它的拐杖 \(q\)。让我们来看看 \(G(x)\) 的表现吧:

\[\begin{aligned} g(k) = \sum\limits_{i = 0}^{m}a_{i}[x^{i}]e^{kx} = \sum\limits_{i = 0}^{m}a_{i}\frac{k^{i}}{i!} = \sum\limits_{i = 0}^{m}g_{i}k^{i} \\ \end{aligned} \]

于是 \(a_{i} = i!\)。这样的结果并不令人意外。

实际上,我们可以发现 \(G(x)\) 和 \(a\) 更像是趋于形式的事物。

更富有人情味地讲——如果你是 \(F(x)\),能有 \(G(x), a\) 这样的好伙计的话,想必是非常幸福的。


(以下画风与上文有所差异)

参考文献

\(F(x)\) 要开始它的表演了。

首先是犯下傲慢之罪的微分方程,以为自己是高达 \(n + 1\) 项的多项式,于是毫不珍惜地抛出了一坨 \((qx + 1 - q)F^{'}(x)\)。等式右侧的 \(0\) 是神的旨意,是完美的造化,它凝视着 \(F(x)\) 幼稚的挑衅。为什么说是挑衅,注意到等式中的减号就像一截锋利的匕首,其实 \(F(x)\) 有刺杀神灵之意,世人称其为 “丢匕”。

\[\begin{aligned} S(x) = nqF(x) - (qx + 1 - q)F^{'}(x) = 0 \end{aligned} \]

说时迟那时快,\(F(x)\) 变成了 \(F(x + 1)\)。这招叫做多项式平移。

为什么每个 \(x\) 都变成了 \(x + 1\)?其实我们还没有提到等式左侧 \(S(x)\),好巧不巧,这个玩意儿的名字叫做 “丢笔”。传说在 \(S(x)\) 降生之时,世间万物都听到了它振聋发聩的怒吼声,使得万物为之一颤:“我和你们每个人,都有 \(1\) 笔账要算。”所以每一项都加了个 \(1\)。

\[\begin{aligned} S(x + 1) = nqF(x + 1) - (qx + 1)F^{'}(x + 1) = 0 \\ \end{aligned} \]

接着是犯下懒惰之罪的多项式截取:\(\mathscr{F}(x + 1) = F(x + 1) \bmod{x^{m + 1}}\)。\(F\) 家族攒下来的 \(n + 1\) 项财产,由于 \(\mathscr{F}\) 的畏难情绪,只剩下了 \(m + 1\) 项。

注意到 \(S\) 变成了 \(\mathscr{S}\),与 \(\mathscr{F}\) 的畏难情绪相反,\(\mathscr{S}\) 不仅不因为自己的智商感到自卑,还努力依靠自己记忆力的优势不断精通世间万物的真理,成为了 “所有人的物理老师”(出处:欧拉被称为 “全人类的数学老师”)。

再注意到右侧的神灵 \(0\) 变成了 \(\mathscr{D}(x)\),其实 \(\mathscr{D}(x)\) 是 dewbee 的简称,这说明丢笔的造化很深,神灵已经为它留下了一席之位。

著名的化学家 GY 也是一位即将一步登天的人,他离成为祖宗只有一步之遥(迫真)。GY 曾经说过:“我的时间是不多了,但比你的时间多”。这能够表明他对丢笔崇高的敬意与可望不可及的畏难情绪。

\[\begin{aligned} \mathscr{S}(x + 1) = nq\mathscr{F}(x + 1) - (qx + 1)\mathscr{F}^{'}(x + 1) = \mathscr{D}(x) \\ \end{aligned} \]

设 \(F(x + 1) = \sum\limits_{i = 0}^{n}f_{i}x^{i}\),则 \(\mathscr{F}(x + 1) = \sum\limits_{i = 0}^{m}f_{i}x^{i}\),\(\mathscr{F}^{'}(x + 1) = \sum\limits_{i = 0}^{m}if_{i}x^{i - 1} = \sum\limits_{i = 0}^{m - 1}(i + 1)f_{i + 1}x^{i}\)。

考察前 \(m + 1\) 项。发现只有第 \(m + 1\) 项不完整(即不为 \(0\)),所以可以设 \(\mathscr{D}(x) = ax^{m}\),并通过一通计算得到:

\[\begin{aligned} a = nqf_{m} - qmf_{m} \\ \end{aligned} \]

求 \(f_{m}\) 是容易的。\(F(x + 1) = (qx + 1)^{n}\),所以 \(f_{m} = \binom{n}{m}q^{m}\)。

然后是犯下贪婪之罪的整式递推。我们现在想要求出 \(\mathscr{F}(x)\) 第 \(0 \sim m\) 项的系数 \(\mathscr{f}_{0}, \dots, \mathscr{f}_{m}\),众所周知这是可以用 NTT 碾过去的,但是整式递推否决了这个想法。

尽管如此,丢笔认为整式递推仍然具有畏难情绪。对于这种简单的问题,“放第二小问都太简单了,更不要谈第三小问”,整式递推这种低效的算法在丢笔面前显然是不堪入目。“做事情要讲究效率。”丢笔如是说。

化学家 GY 曾就【贪婪】这一概念与丢笔谈笑风生。“你【数据删除】是为了【数据删除】吗?”丢笔对此评价是:”你不用管这些。“表现出了丢笔优雅的自尊心理与摈弃世俗的超凡眼光。

整式递推显然还不够贪婪,所以它触犯了贪婪之罪。

\[\begin{aligned} nq\mathscr{F}(x) - (qx + 1 - q)\mathscr{F}^{'}(x) = \mathscr{D}(x - 1) = a(x - 1)^{m} \\ \end{aligned} \]

书写递推式:

\[\begin{aligned} nq\mathscr{f}_{i} - qi\mathscr{f}_{i} - (1 - q)(i + 1)\mathscr{f}_{i + 1} = a(-1)^{m - i}\binom{m}{i} \\ \mathscr{f}_{i} = \frac{a(-1)^{m - i}\binom{m}{i} + (1 - q)(i + 1)\mathscr{f}_{i + 1}}{q(n - i)} \end{aligned} \]

递推边界为 \(\mathscr{f}_{m + 1} = 0\)。当 \(n < i\) 时,特判 \(\mathscr{f}_{i} = 0\)。当 \(n = i\) 时,特判 \(\mathscr{f}_{n} = q^{n}\)。\(q = 0\) 不想管了,因为代回去 \(0^{0}\) 无意义。

代回答案式:

\[\begin{aligned} Ans &= \sum\limits_{i = 0}^{m}a_{i}[x^{i}]F(G(x)) \\ &= \sum\limits_{i = 0}^{m}a_{i}[x^{i}]\mathscr{F}(G(x)) \\ &= \sum\limits_{k = 0}^{m}\mathscr{f}_{k}\sum\limits_{i = 0}^{m}a_{i}[x^{i}]G(x)^{k} \\ &= \sum\limits_{k = 0}^{m}\mathscr{f}_{k}g(k) \\ \end{aligned} \]

所以说,丢笔才是神,前面忘了中间忘了后面忘了。

你说得对,但是我推式子时把一个正负号写错了。

标签:begin,2016,end,limits,mathscr,sum,aligned,P6667,集训
From: https://www.cnblogs.com/Schucking-Sattin/p/17968450

相关文章

  • Windows 2016 2019 显示桌面图标
    运行cmd窗口输入命令rundll32.exeshell32.dll,Control_RunDLLdesk.cpl,,0弹出桌面图标设置窗口作者:VipSoft......
  • 寒假集训Day1
    寒假集训Day1主要了解到了两个比较有意义的东西,记录如下质数筛法埃氏筛从二开始,二是一个质数,那么二的倍数就是合数,三同理,利用这样的思想可以把所有质数的倍数做上标记欧拉筛埃氏筛有一个问题,就是同一个合数可能被反复筛选,比如6既是2的倍数又是3的倍数,这样它就会被筛选两遍。......
  • 南外集训 2024.1.15 T3
    纯粹技术性的题目。给定一个字符串的后缀数组以及对应的height数组的一部分(即一些height数组的位置是未知的,用\(-1\)表示),要求还原出一种可能的字符串。保证存在一种由\(26\)个小写英文字母构成的解。\(1\len\le10^6\)首先考虑没有\(-1\)的情况。注意到此时我们给......
  • 南外集训 2024.1.12 T3/AGC022F Checkers 加强版
    第一步转化比较套路,DP设计需要很强的洞察力,最后的优化也很考验基本功。有\(n\)个\(n\)维空间中的点,第\(i\)个点\(x_i\)满足\(x_{i,i}=1,x_{i,j}=0(\foralli\neqj)\)。接下来进行\(n-1\)次操作,每次任选两个点,将第一个点关于第二个点对称,然后删掉第二个点。......
  • 冯梓轩集训总结3
    冯梓轩集训总结3——最短路模版算法Dijkstra可以说是最常用的最短路算法了。主要思想是找到当前更新过的距离源点最近的点,然后用它的最短路去更新与它相连的点的最短路。对于距离源点最近,可以开一个小根堆维护,这样的时间复杂度为\(O(m\logm)\)。但是算法有一个弊端:所有边的......
  • 期末集训总结
    这个学期我们主要学了四个内容:序列DP,背包DP,区间DP,最短路。序列DP最长公共子序列朴素模版for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){dp[i][j]=max(dp[i-1][j],dp[i][j-1]);if(a[i]==b[j])dp[i][j]=max(dp[i][j],dp[i-1][j-1]); }}最长上升/......
  • 期末集训总结
    这个学期我们主要学了四个内容:序列DP,背包DP,区间DP,最短路。序列DP最长公共子序列朴素模版for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){dp[i][j]=max(dp[i-1][j],dp[i][j-1]);if(a[i]==b[j])dp[i][j]=max(dp[i][j],dp[i-1][j-1]); }}最长上升/......
  • Windows Server 2016 & 2019 工作站速配脚本
    之前有一篇关于把WindowsServer打造成工作站系统的随笔,其中的步骤完全基于手工操作,一部分对系统不熟悉的朋友恐怕会找不到设置的入口。与其弄一堆截图写所谓的教程,还不如写一个程序来自动化处理。init.ps1Write-Host"`n正在启用声音服务"Set-Service-Name"Audiosrv"-Stat......
  • CTSC 2016 香山的树
    题意给定\(n,k\)和Lyndon串\(s_1\),求长度小于等于\(n\)的Lyndon串中,按照字典序排在\(s_1\)后面\(k-1\)名的串\(s_k\),或报告无解。\(1\len\le50,1\lek\le10^{15}\)。Lyndon串:字典序严格小于所有自己真后缀的串题解只需要计数拥有某个给定前缀\(p\)的......
  • P4093 [HEOI2016/TJOI2016] 序列 题解
    题目链接:序列对于LIS问题,很显而易见的有dp方程为:\[dp_i=\max{dp_j}+1\(j<i,a_j\lea_i)\text{dp表示以某个位置结尾的最长LIS}\]本题考虑到对于转移的两位置,如果能从\(j\rightarrowi\),那么在以上条件成立的基础情况下,我们由于可以更改二者中的任意一个值(因为同一......