首页 > 其他分享 >QOJ #9317. Rivals

QOJ #9317. Rivals

时间:2024-10-30 19:47:12浏览次数:1  
标签:系数 frac limits sum underline Rivals 9317 展开 QOJ

题面传送门

直接做显然不太好做,考虑转化成每次都从 \(n\) 个怪中随机挑一个出来打,但是只有挑到还有血量的怪才算入“打了一次”。

使用生成函数来刻画这个东西:当打了一次,乘上一个 \(y\),打了有效的一次,乘上一个 \(x\)。枚举最后一次有效攻击打到了哪个身上,则每个怪的 EGF 就是

\[x^{a}e^{\frac{y}{n}}+\sum\limits_{0\leq j<a}{\frac{(x^i-x^a)y^i}{n^ii!}} \]

直接把所有生成函数用个 DP 卷出来,这部分复杂度是 \(O(n^3a^3)\) 的。

现在我们需要计算某个 \(x^ay^be^{k\frac{y}{n}}\) 的系数,将其贡献到攻击了 \(a+1\) 次的答案中。将 \(e\) 展开,我们要求的东西实际上长这样:

\[\sum\limits_{i\geq 0} (\frac{k}{n})^i (i+b)^{\underline{b}} \]

发现只和 \(k,b\) 有关,不妨确定 \(k\),记 \(f(b)\) 表示 \(b\) 的系数,则将 \(i=0\) 的情况提取出来,有

\[f(b)=b!+\frac{k}{n}\sum\limits_{i\geq 0} (\frac{k}{n})^i (i+b+1)^{\underline{b}} \]

注意到 \((i+b+1)^{\underline{b}}\) 实际上是可以展开的,其可以展开成 \(\sum\limits_{j=0}^{b}(i+j)^{\underline{b-j}}\),展开以后将 \(f(b)\) 移项到左边,整理为

\[\frac{n-k}{n} f(x)=b!+\frac{k}{n}\sum\limits_{0\leq j<x} f(j)b^{\underline{b-j}} \]

就可以 \(O(n^2a^2)\) 对于某个固定的 \(k\) 递推出系数。瓶颈还是在于前面的背包。

submission

标签:系数,frac,limits,sum,underline,Rivals,9317,展开,QOJ
From: https://www.cnblogs.com/275307894a/p/18516491

相关文章

  • springboot微信点餐小程序-计算机毕业设计源码93176
     目 录摘要1绪论1.1研究背景1.2 研究意义1.3微信开发者工具介绍2 系统分析2.1可行性分析2.2系统流程分析2.2.1数据新增流程2.2.2 数据删除流程2.3 系统功能分析2.4 系统用例分析3系统总体设计3.1 系统功能模块设计3.2 数据库设计......
  • qoj6562 First Last 题解
    妙妙题。首先不同字母数最多为\(3\)。我们把每一个字母看成一个点。对于每一个字符串,首个字母朝末尾字母连一条有向边。那么问题变为了给定一张有向图,从某个点出发,每次走一条边,且边不能重复,不能走的人输。问哪方有必胜策略。先不考虑时间复杂度,那么这个可以直接爆搜。但是肯定......
  • qoj8528 Chords 题解
    数据随机有什么用?用你惊人的注意力可以观察到答案的值域在\(800\)附近。考虑暴力dp,设\(dp_{l,r}\)表示值域在\([l,r]\)中最多能选几个区间。假设\(r\)对应区间的左端点为\(lst\),那么有转移方程\(dp_{l,r}=dp_{l,lst-1}+dp_{lst+1,r-1}+1\)。时间复杂度\(O(n^2)\)。......
  • 题解 QOJ5048【[ECFinal19K] All Pair Maximum Flow】
    题目描述给你一个\(n\)个点\(m\)条边的图,它是平面上的正\(n\)边形和一些对角线,节点按逆时针方向编号为\(1\)到\(n\)。对角线只可能在节点处相交。每条边有一个容量,求每个点对之间的最大流的和。\(n\leq200000,m\leq400000\)。solution做法每次找出边权最小的边\(......
  • QOJ #9448. Product Matrix
    题面传送门这居然是能快速插值的?首先令\(A_{i,x,y}=a_{x,y}2^i+b_{x,y}\),则\(\prod\limits_{i=k}^{k+m-1}A_i\)的\((1,1)\)位置相当于将\(x=2^k\)代入答案多项式得到的点值。可以用矩阵乘法在\(O(mn^3)\)时间复杂度内求出这\(m+1\)个点值。然后我们需要插值出原来......
  • 题解 QOJ1869【Power Station of Art】/ SS241006B【结论题】
    题解QOJ1869【PowerStationofArt】/SS241006B【结论题】PetrozavodskSummer2021.Day6.XJTUContest,GPofXJTUXXIIOpenCupnamedafterE.V.Pankratiev,GrandPrixofXi'an题目描述给出一个无向图,每个点有点权\(a\)和颜色\(c\),其中颜色只会有红蓝两种。......
  • 题解 QOJ2559【Endless Road】/ SS241006D【套路题】
    PetrozavodskWinter2022.Day2.KAISTContest+KOITST2021XXIIOpenCupnamedafterE.V.Pankratiev,GrandPrixofDaejeon题目描述现在有\(10^9\)个花盆,依次编号为\(1,2,\dots,10^{9}\)。给定\(n\)个二元组\(L_i,R_i(L_i<R_i)\),我们将进行\(n\)次以下操......
  • QOJ #9438. Two Box
    题面传送门首先考虑给定一个状态怎么计算答案。考虑建立一棵\(m\)层的树,在第\(d\)层的时候,考虑每个极长连续段\([l,r]\)满足\(\max\limits_{i=l}^{r}a_i\geqd\),则将\([l,r+1]\)看作这棵树上的一个点,向\(d+1\)层中所有被这个区间包含的点连边。对于第\(i\)层的第......
  • gym103687D / QOJ3998 The Profiteer
    题意有\(n\)个物品,和一个背包容量上限\(m\)。每个物品有价值\(v_i\)和体积\(a_i\)。你需要选择一段区间\([l,r]\),将这个区间内的体积变为\(b_i\),剩下的不变。然后你对这\(n\)个物品做背包,设背包容量结果为\(f(i)\),需要求出有多少段区间使得\(\dfrac{\sum_{i=1}^mf(......
  • qoj9230 Routing K-Codes 题解
    首先这个图肯定不能有环,也不能有度数大于\(3\)的点。也就是说这是一颗二叉树。我们假设父亲都比儿子小,根节点的值最小。那么假设\(u\)点的值为\(x\),它的儿子的值一定是\(\{2x,2x+1\}\)的子集。会发现\(u\)的子树内的权值和是一个关于\(x\)的一次函数。而且无论两个儿......