前言
本文章将会持续更新，主要是一些个人觉得比较妙的题，主观性比较强（给自己记录用的），有讲错请补充。
带 ！号的题是基础例题，带 * 号的是推荐首先完成的题（有一定启发性的）。
组合数
P6620 [省选联考 2020 A 卷] 组合数问题
运用斯特林数好的例题，普通幂转下降幂。用到第二类斯特林数。
\[x^{\underline n}= \sum_{i=0}^{n} \lbrace ^n _i \rbrace x^i \]下降幂处理方式：先转为阶乘形式，后转为组合数形式。如
\[x^{\underline n}=\binom{x}{n}*n! \]这题按照题目推式子，主要卡点就是斯特林数的运用。
*高橋君
组合数与数据结构的结合。
离线询问+ (\(n=10^{5}\)) 的数据范围可以联想到莫队。
又通过归纳恒等式可以推出 \(n,k\) 分别左移或右移的式子。
\[\sum_{i=0}^{k+1}\binom{n}{i}=\sum_{i=0}^{k} \binom{n}{i}+\binom{n}{k+1} \]\[\sum_{i=0}^{k-1}\binom{n}{i}=\sum_{i=0}^{k} \binom{n}{i}-\binom{n}{k-1} \]\[\sum_{i=0}^{k}\binom{n+1}{i}=2*\sum_{i=0}^{k} \binom{n}{i}-\binom{n}{k} \]\[\sum_{i=0}^{k}\binom{n}{i}=\frac{1}{2}*(\sum_{i=0}^{k} \binom{n+1}{i}+\binom{n}{k}) \]注意莫队的正确写法,\(n,k\)的大小关系。
Lonely Mountain Dungeons
首先贪心，每个种族平均分肯定是更优的，所以先设分成 \(k\) 组，设 \(y=\dfrac{c_i}{k}\) 向下取整，\(y_1=\dfrac{c_i}{k}\) 向上取整，\(mod=c_i\% k\)，那每个种族可以分出：
\[C_{mod}^2 \times y_1^2+C_{k-mod}^2 \times y^2+mod\times (k-mod) \times y \times y_1 \]暴力求时间复杂度报表，分为三种方法优化方法了。
方法1：三分法。
上式化简下来一定是关于 \(k\) 的二次函数，显然随着 \(k\) 的增大，值先增大，后减小，是个单峰函数（可以打表试试）。
然后普通三分就可以了。
方法2：差分前缀和法（也是官方题解的方法）
定义 \(f[k]\) 为分为 \(k\) 个小组的最大方案。
可以发现当 \(k>c_i\) 时，当前种族的值是不变的。
\(\sum c_i\) 是 \(2\times 10^5\)，所以遍历所有 \(1\) 到 \(n\)，让 \(f[j]\) 加上每个种族的贡献。因为当 \(i\) 超过 \(c[j]\) 时，后面的值不变，所以用差分来处理。
for(int i=1;i<=n;i++)
{
for(int j=1;j<c[i];j++)
f[j]+=get(i,j)*b,f[j+1]-=get(i,j)*b;
f[c[i]]+=get(i,c[i])*b;
}
最后遍历小组数即可。
方法3：
与上中方法类似，我们知道 $k $ 一定不大于 \(maxc\)，按 \(c\) 的大小从小到大排序，从 \(2\) 到 \(n\) 枚举小组数，小于 \(i\) 的种族就暴力计算，大于的因为值都不变了，拿一个数组记录一下前缀即可。
时间复杂度可以证明不超过 \(O(n \sqrt {\sum c})\)
标签：sum,好题,times,数学,binom,数据结构,方法,种族,mod From： https://www.cnblogs.com/hutongzhou/p/18169030