2025.11.20训练记录

noip模拟赛。
开了空调的机房真是太舒服了。闭上眼睛就可以缩短醒着的时间。

A

比较唐氏的题。
正整数 (n) 最多只有 (1) 个大于 (sqrt{n}) 的因数，这个是经典结论。
同理的，正整数 (n) 最多只有两个 ((sqrt{3}{n}, sqrt{n}]) 中的因数。
于是只要特判 (k=2)且「(n) 做完三次根号内的质因数分解后为完全平方数」的情况即可。

C

神秘推式子，大抵算是知道怎么推了。
观察原式：

[f_{n, x, y}(a, b) = sum_{i = a}^{n - b} binom{i}{a} x^{i - a} binom{n - i}{b} y^{n - i - b} ]

找出递推式

首先平移下标，改为将 (i)从 (0) 开始枚举，相当于平移了一个 (a)，那么需要将 (sum) 中的所有 (i) 都换成 (i+a)。

[f_{n, x, y}(a, b) = sum_{i = 0}^{n - b - a} binom{i + a}{a} x^i binom{n - i - a}{b} y^{n - i - a - b} ]

这样子的平移好像是在这种一堆求和的式子中推的基础操作。
但是平移多少感觉非常巧思。明显感觉这种操作上限很高但是非常难想到。
大部分时候看到 (sum) 都有一种难变换的感觉。/ll

接下来考虑组合数的基本变换：

[binom{n}{m} = binom{n - 1}{m} + binom{n - 1}{m - 1} ]

由杨辉三角即可得出。
将原式中的 (binom{i + a}{a}) 用这种方法代替。即变为：

[f_{n, x, y}(a, b) = 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 - b - a} binom{i + a - 1}{a} x^i binom{n - i - a}{b} y^{n - i - a - b} ]

这里回到题意，由于我们要对于多组 (a_i, b_i) 回答询问，所以考虑预处理 (f[a][b]) 表示 (f_{n, x, y}(a, b))。
尝试使用递推的方式预处理。我们一步步对式子的化简的最终目的是找到关于 (f[a][b]) 的递推式。
到这一步为止，等式的右边被我们拆成了两个部分。我们一部分一部分的考虑，尝试将它们都转化成与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) 相似的形式。
这个式子即为：

[f_{n - 1, x, y}(a - 1, b) ]

然后我们再考虑第二部分：

[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) 提出，得到第二部分为：

[x f_{n - 1, x, y}(a, b) ]

结合两个部分，我们得到：

[f_{n, x, y}(a, b) = f_{n - 1, x, y}(a - 1, b) + x f_{n - 1, x, y}(a, b) ]

总的来讲，这个式子由关于 (a) 的组合数拆分得到。同理的，将关于 (b) 的另一个组合数 (binom{n - i - a}{b}) 拆分，得到：

[f_{n, x, y}(a, b) = f_{n - 1, x, y}(a, b - 1) + y f_{n - 1, x, y}(a, b) ]

将两个式子联立，得到

[f_{n - 1, x, y}(a - 1, b) + x f_{n - 1, x, y}(a, b) = f_{n - 1, x, y}(a, b - 1) + y f_{n - 1, x, y}(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) 位，我们就得到了递推式：

[f[a][b] = frac{f[a][b - 1] - f[a - 1][b]}{x - y} ]

一般情况下这个式子都是成立的。
观察这个式子，它会在 (a=0)、(b=0)、(x=y) 这三种状况下出问题。
于是将这三种情况分开来研究。

(a=0) / (b=0) 时：

考虑倒数第二步的式子：

[f_{n, x, y}(a, b) = f_{n - 1, x, y}(a - 1, b) + x f_{n - 1, x, y}(a, b) ]

发现是(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)，大力拆分，得到：

[S = sum_{i = 0}^{n - a - b} binom{i + a}{a} x^{i} binom{n - i - a}{b} y^{n - i - a - b} - sum_{i = 0}^{n - a - b} binom{i + a - 1}{a} x^{i} binom{n - i - a}{b} y^{n - i - a - b} ]

发现右边两项大部分是一样的，将一样的部分全部提出，得到：

[S = sum_{i = 0}^{n - a - b} x^{i} binom{n - i - a}{b} y^{n - i - a - b} (binom{i + a}{a} - binom{i + a - 1}{a}) ]

将 (a=0) 代入，得到：

[S = sum_{i = 0}^{n - b} x^{i} binom{n - i}{b} y^{n - i - b} (binom{i}{0} - binom{i - 1}{0}) ]

发现括号内的项 (binom{i}{0} - binom{i - 1}{0}) 只在 (i) 取 (0) 时有 (1) 的值，其余情况都为 (0)。
在 (i) 取 (0) 时，此式即为：

[S = binom{n}{b} y^{n - b} ]

所以我们在 (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) 代入。
发现有：

[f_{n, x, y}(a, b) = x^{n - a - b} sum_{i = a}^{n - b} binom{i}{a} binom{n - i}{b} ]

使用神秘组合意义理解这个式子：
先不管前面 (x) 的系数，后面这个式子的组合意义大概为：
「有 (n)个小球，枚举一个分界线 (i)，在 ([1, i]) 选 (a) 个球，同时在 ([i + 1, n]) 选 (b) 个球」的方案数。
神秘地，我们人为的添加一个球作为原来的「分界线 (i)」，即在 (n + 1) 个球中选出 (a + b + 1) 个，此时从左往右数的第 (a + 1) 个被选出的球就代表了原来的分界线。
这是不重不漏的。
所以 (x=y) 时，有：

[f_{n, x, y}(a, b) = x^{n - a - b} binom{n + 1}{a + b + 1} ]

初始化

现在对于所有情况，我们的递推过程都完整了。
但是我们还没有考虑过递推的初始状态 (f[0][0])。将 (a=0)，(b=0) 代入原式，得到：

[f_{n, x, y}(0, 0) = sum_{i = 0}^{n} x^{i} y^{n - i} ]

整理成为：

[f_{n, x, y}(0, 0) = y^n sum_{i = 0}^{n} (frac{x}{y})^{i} ]

这是个等比数列求和。

整体代码如下：

    cin >> n >> x >> y >> Q;     if(x == y) {         for(int i = 1; i <= 10001; i ++) {             val[i] = C(n + 1, i);         }         while(Q --) {             int wasd,dsaw; cin >>wasd >>dsaw;             cout << val[wasd + dsaw + 1] * kuai(x, n - wasd - dsaw) % mod <<endl;         }         return 0;     }     int ratio = x * kuai(y, mod - 2) % mod;     f[0][0] = kuai(y, n) * (kuai(ratio, n + 1) - 1) % mod * kuai(ratio - 1, mod - 2) % mod;     int inv1 = kuai(x - y, mod - 2);     for(int a = 0; a <= 5000; a ++) {         for(int b = 0; b <= 5000; b ++) {             if(a == 0 && b == 0) continue;             // cout << a << ' ' << b << endl;             if(a == 0) f[a][b] = (f[a][b - 1] - C(n + 1, b) * kuai(y, n + 1 - b) % mod) * inv1 % mod;             else if(b == 0) f[a][b] = (C(n + 1, a) * kuai(x, n + 1 - a) % mod - f[a - 1][b]) * inv1 % mod;             else f[a][b] = (f[a][b - 1] - f[a - 1][b]) * inv1 % mod;             f[a][b] = (f[a][b] + mod) % mod;         }     }     // cout << f[1][1] << endl;     while(Q --) {         int wasd, dsaw; cin >> wasd >>dsaw;         cout << f[wasd][dsaw] << endl;     }