2025.11.20训练记录
noip模拟赛。开了空调的机房真是太舒服了。闭上眼睛就可以缩短醒着的时间。
A
比较唐氏的题。
正整数 \(n\) 最多只有 \(1\) 个大于 \(\sqrt{n}\) 的因数，这个是经典结论。
同理的，正整数 \(n\) 最多只有两个 \((\sqrt{3}{n}, \sqrt{n}]\) 中的因数。
于是只要特判 \(k=2\)且「\(n\) 做完三次根号内的质因数分解后为完全平方数」的情况即可。
C
神秘推式子，大抵算是知道怎么推了。
观察原式：
\
找出递推式
首先平移下标，改为将 \(i\)从 \(0\) 开始枚举，相当于平移了一个 \(a\)，那么需要将 \(\sum\) 中的所有 \(i\) 都换成 \(i+a\)。
\
这样子的平移好像是在这种一堆求和的式子中推的基础操作。
但是平移多少感觉非常巧思。明显感觉这种操作上限很高但是非常难想到。
大部分时候看到 \(\sum\) 都有一种难变换的感觉。/ll
接下来考虑组合数的基本变换：
\[\binom{n}{m} = \binom{n - 1}{m} + \binom{n - 1}{m - 1}\]
由杨辉三角即可得出。
将原式中的 \(\binom{i + a}{a}\) 用这种方法代替。即变为：
\
这里回到题意，由于我们要对于多组 \(a_i, b_i\) 回答询问，所以考虑预处理 \(f\) 表示 \(f_{n, x, y}(a, b)\)。
尝试使用递推的方式预处理。我们一步步对式子的化简的最终目的是找到关于 \(f\) 的递推式。
到这一步为止，等式的右边被我们拆成了两个部分。我们一部分一部分的考虑，尝试将它们都转化成与f相似的形式。
先看到第一个部分：
\[\sum_{i = 0}^{n - b - a} \binom{i + a - 1}{a - 1} x^i \binom{n - i - a}{b} y^{n - i - a - b}\]
它可以等价地写成：
\[\sum_{i = 0}^{(n - 1) - b - (a - 1)} \binom{i + a - 1}{a - 1} x^i \binom{(n - 1) - i - (a - 1)}{b} y^{(n - 1) - i - (a - 1) - b}\]
这里我们把所有 \(n\)，\(a\) 同时存在的部分替换成 \((n-1)\) 和 \((a-1)\)，发现和原来是等价的。且变成了与 \(f\) 相似的形式。
这个式子即为：
\
然后我们再考虑第二部分：
\[\sum_{i = 0}^{n - b - a} \binom{i + a - 1}{a} x^i \binom{n - i - a}{b} y^{n - i - a - b}\]
注意到 \(i=0\) 时，式子的第一项为 \(\binom{a - 1}{a}\)，值为 \(0\)，于是可以将 \(i\) 的下界直接写为 \(1\)。
\[\sum_{i = 1}^{n - b - a} \binom{i + a - 1}{a} x^i \binom{n - i - a}{b} y^{n - i - a - b}\]
还是将 \(i\) 的枚举区间平移，使 \(i\) 从 \(0\) 开始枚举。此时上界变成 \(n - b - a - 1\)，求和中的 \(i\) 变为 \(i+1\)。即：
\[\sum_{i = 0}^{n - b - a - 1} \binom{i + a}{a} x^{i + 1} \binom{(n - 1) - i - a}{b} y^{(n - 1) - i - a - b}\]
此时它和 \(f_{n - 1, x, y}(a, b)\) 非常相似。只差一个 \(x\)。
所以将 \(x\) 提出，得到第二部分为：
\
结合两个部分，我们得到：
\
总的来讲，这个式子由关于 \(a\) 的组合数拆分得到。同理的，将关于 \(b\) 的另一个组合数 \(\binom{n - i - a}{b}\) 拆分，得到：
\
将两个式子联立，得到
\
即：
\[(x - y)f_{n - 1, x, y}(a, b) = f_{n - 1, x, y}(a, b - 1) - f_{n - 1, x, y}(a - 1, b)\]
将 \(n\) 平移 \(1\) 位，我们就得到了递推式：
\ = \frac{f - f}{x - y}\]
一般情况下这个式子都是成立的。
观察这个式子，它会在 \(a=0\)、\(b=0\)、\(x=y\) 这三种状况下出问题。
于是将这三种情况分开来研究。
\(a=0\) / \(b=0\) 时：
考虑倒数第二步的式子：
\
发现是\(f_{n - 1, x, y}(a - 1, b)\)这一项出了问题。
cdx 声称，如果这个时候你对于 \(a=0\)、\(b=0\) 的情况单独去找递推规律，是难以赢的。
这个时候我们的思路还是把它向标准情况的递推式去靠。
还是看到\(f_{n - 1, x, y}(a - 1, b)\)这一项，它在 \(a=0\) 时明显有问题。
那我们就考虑将这一项写成 \(f_{n, x, y}(a, b) - x f_{n - 1, x, y}(a, b)\)
令这一项为 \(S\)，大力拆分，得到：
\
发现右边两项大部分是一样的，将一样的部分全部提出，得到：
\
将 \(a=0\) 代入，得到：
\
发现括号内的项 \(\binom{i}{0} - \binom{i - 1}{0}\) 只在 \(i\) 取 \(0\) 时有 \(1\) 的值，其余情况都为 \(0\)。
在 \(i\) 取 \(0\) 时，此式即为：
\
所以我们在 \(a=0\)时，用 \(\binom{n}{b} y^{n - b}\) 代替 \(f_{n - 1, x, y}(a - 1, b)\) 进行转移即可。
\(b=0\) 的情况同理，用 \(\binom{n}{a} x{n - a}\) 代替$ f_{n - 1, x, y}(a, b - 1)$。
剩下的就是 \(x=y\) 的情况。
\(x=y\) 时
\(x=y\) 时，递推式的分母变成了 \(0\)。此时我们回到原式。将 \(x=y\) 代入。
发现有：
\
使用神秘组合意义理解这个式子：
先不管前面 \(x\) 的系数，后面这个式子的组合意义大概为：
「有 \(n\)个小球，枚举一个分界线 \(i\)，在 \(\) 选 \(a\) 个球，同时在 \(\) 选 \(b\) 个球」的方案数。
神秘地，我们人为的添加一个球作为原来的「分界线 \(i\)」，即在 \(n + 1\) 个球中选出 \(a + b + 1\) 个，此时从左往右数的第 \(a + 1\) 个被选出的球就代表了原来的分界线。
这是不重不漏的。
所以 \(x=y\) 时，有：
\
初始化
现在对于所有情况，我们的递推过程都完整了。
但是我们还没有考虑过递推的初始状态 \(f\)。将 \(a=0\)，\(b=0\) 代入原式，得到：
\
整理成为：
\
这是个等比数列求和。
整体代码如下：
cin >> n >> x >> y >> Q; if(x == y) { for(int i = 1; i >wasd >>dsaw; cout 鼓励转贴优秀软件安全工具和文档！ 不错，里面软件多更新就更好了 谢谢分享，试用一下 感谢发布原创作品，程序园因你更精彩 感谢分享，学习下。 感谢分享，下载保存了，貌似很强大 感谢分享，下载保存了，貌似很强大 热心回复！ 感谢分享，下载保存了，貌似很强大 东西不错很实用谢谢分享 yyds。多谢分享 过来提前占个楼 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 谢谢分享，辛苦了 热心回复！ 感谢发布原创作品，程序园因你更精彩 谢谢楼主提供！ 感谢分享，下载保存了，貌似很强大 谢谢分享，辛苦了
页:
[1]
2