D 题题解

本题是数论题，主要用到的是求逆元的方法对除法进行优化

给定 $n$ 和 $m$ ，计算增量乘法公式之和：

$f(n,m)=\sum_{i=1}^n\prod_{j=i}^{i+m-1}j$

测试用例不超过 $50$ 组，数据范围是 $1\le n,m\le 10^6$

对于每个测试用例，输出 $f(n,m)$ 对 $10^9+7$ 取模的结果。

Solution

方法 1：整数裂项

以求 $f(98,3)$ 为例:

$f(98,3)=(1×2×3)+(2×3×4)+...+(98×99×100)$

其可以转换表达为：

$1×2×3=(1×2×3×4−0×1×2×3)/4$
$2×3×4=(2×3×4×5−1×2×3×4)/4$
$...$
$98×99×100=(98×99×100×101−97×98×99×100)/4$

相加之后，相邻项抵消，最终得到

$f(98,3)=98×99×100×101/4$

则对于 $f(n,m)$ ，有

$f(n,m)=\prod_{i=n}^{m+n}i/(m+1)$

方法 2：预处理 $n!$ 与逆元

初始化第一项为 $fact(m)$ ，之后每一项乘后一个数，除最前一个数(乘逆元)，累加求和

逆元在实际应用中，模 $n$ 意义下， $a$ 如果有逆元 $x$ ,那么除以 $a$ 相当于乘以 $x$

具体实现:

先处理好 $[1,2\times10^6]$ 的逆元inv，然后对于每个问询，先计算 $m!$ ，然后每次乘于左端逆元inv[i]与新右端点 $i+m$ 。需注意 $i\in[1,n-1]$

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e6;
const long long MOD = 1e9 + 7;
long long n, m, inv[MAXN + 1];
void inverseElement()
{
    inv[1] = 1;
    for (int i = 2; i <= MAXN; i++)
        inv[i] = (long long)(MOD - MOD / i) * inv[MOD % i] % MOD;
}
int main()
{
    inverseElement();
    while (cin >> n >> m)
    {
        long long ans = 0, sum = 1;
        for (int j = 1; j <= m; j++)
            sum *= j, sum %= MOD;
        ans += sum, ans %= MOD;
        for (int i = 2; i <= n; i++)
        {
            sum = ((sum % MOD) * (((i + m - 1) * inv[i - 1]) % MOD)) % MOD;
            ans += sum, ans %= MOD;
        }
        cout << ans % MOD << endl;
    }
    return 0;
}

D 题题解

Solution

方法 1：整数裂项

方法 2：预处理 n!n!n! 与逆元

方法 2：预处理 $n!$ 与逆元