自动搬运

查看原文

来自洛谷，原作者为

	离散小波变换° 有志不在年高，无志空长百岁

搬运于2025-08-24 22:41:29，当前版本为作者最后更新于2023-04-22 22:00:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题解

首先 $m>n$ 多出来的部分毫无意义，所以第一步 $m\gets \min(n,m)$ 可以避免一些无意义的讨论。

观察到 $1\le n,m\le 10^{18}$ 过大，很明显没法用正常的方法去做。不过注意到 $k\le 10^8$ 是一个质数，可以从这里先下手。

对于一个组合数模一个质数，可以想到 $\text{Lucas}$ 定理：

$$\dbinom{x}{y}\bmod p=\dbinom{x\operatorname{div} p}{y\operatorname{div} p}\times \dbinom{x\bmod p}{y\bmod p}\bmod p $$

在使用 $\text{Lucas}$ 定理计算组合数模 $p$ 的值时，通常会递归处理。因此在本题中我们也考虑递归地展开 $\dbinom{x}{y}\bmod p$ 的值。

具体地，我们把 $x$ 和 $y$ 看作 $k$ 进制数并进行分解。也就是，

$$\begin{aligned} x&= a_0+a_1k+a_2k^2+\cdots +a_u k^u \cr y&= b_0+b_1k+b_2k^2+\cdots +b_v k^v \cr \end{aligned}$$

其中，$0\le a_i,b_i<k$。那么应用 $\text{Lucas}$ 定理并将其递归展开后，可以得到如下形式：

$$\dbinom{x}{y}\bmod p=\dbinom{a_0}{b_0}\dbinom{a_1}{b_1}\dbinom{a_2}{b_2}\cdots \dbinom{a_{\max (u,v)}}{b_{\max(u,v)}}\bmod p $$

在这个式子中我们认为当 $i>u$ 时 $a_i=0$，当 $i>v$ 时 $b_i=0$。

我们随便选取其中某一项，可以发现 $\dbinom{a_i}{b_i}\neq 0$ 的充要条件是 $a\ge b$。这是因为，$a<b$ 时显然 $\dbinom{a}{b}=0$，而 $a\ge b$ 时将组合数展开为阶乘形式，就能发现最终计算结果不可能带有 $p$ 作为因子。

接着发现要存在至少一个 $i$ 满足 $a_i<b_i$，不如从总方案数里减去对于所有 $i$ 都有 $a_i\ge b_i$ 的方案数。总方案数显然为 $nm-\dfrac{m(m+1)}{2}$。但是需要特别小心对总方案数的取模，因为 $n,m$ 均为 $\text{long long}$ 级别，取模稍有不慎就会溢出！

这题到这里其实已经很容易解决了。我们只需要将每一对 $(a_i,b_i)$ 看作数码，跑一个数位 dp 就行。记 $l=\max(u,v)$ 是 $x,y$ 的最长长度，$f(i,0/1,0/1)$ 表示当前处理到第 $i\sim l$ 位，其中第 $i$ 位在 $x$ 中这一位有没有被限制，在 $y$ 中这一位有没有被限制。可以得到状态转移方程式：

$$\begin{aligned} f(i,1,1) =&\ f(i+1,1,1)\operatorname{bitand} [a_i>b_i] \cr f(i,1,0) =&\ f(i+1,1,1)\times \min(a_i+1,b_i)+f(i+1,1,0)\times (a_i+1) \cr f(i,0,1) =&\ f(i+1,1,1)\times \max(a_i-b_i,0)+f(i+1,0,1)\times (k-a_i) \cr f(i,0,0) =&\ f(i+1,1,1)\times g(a,b)+f(i+1,1,0)\times g(a,k)\cr +&\ f(i+1,0,1)\times g(k,b)+f(i+1,0,0)\times g(k,k) \end{aligned}$$

其中，

$$g(n,m)=\sum_{i=0}^{n-1}\sum_{j=0}^{m-1}[i\ge j]$$

分类讨论一下，容易可以得到 $g$ 的表达式：

$$g(n,m)=\begin{cases}\dfrac{m(m+1)}{2}+(n-m)m & n\ge m \cr \dfrac{n(n+1)}{2} & n< m\end{cases} $$

每种情形都很简单，但是讨论起来异常麻烦。读者有兴趣可以自行推导。

参考代码

#include<bits/stdc++.h>
#define up(l, r, i) for(int i = l, END##i = r;i <= END##i;++ i)
#define dn(r, l, i) for(int i = r, END##i = l;i >= END##i;-- i)
using namespace std;
typedef long long i64;
const int INF = 2147483647;
const int MAXN=  60 + 3;
const int MOD = 1e9 + 7;
int A[MAXN], B[MAXN], k;
int F[MAXN][2][2];
void add_to(int &a, int b){
    a = (a + b) % MOD;
}
int calc(int a, int b){
    if(a >= b){
        return (1ll * b * (b + 1) / 2 + 1ll * (a - b) * b) % MOD;
    } else
        return  1ll * a * (a + 1) / 2 % MOD;
}
int dp(int l, bool f, bool g){
    if(F[l][f][g] != -1) return F[l][f][g];
    F[l][f][g] = 0;
    int a = A[l];
    int b = B[l];
    if(f == true && g == true){
        F[l][f][g] = dp(l + 1, true, true) & (a >= b);
    } else if(f == true){
        add_to(F[l][f][g], 1ll * dp(l + 1,  true,  true) * min(a + 1, b) % MOD);
        add_to(F[l][f][g], 1ll * dp(l + 1,  true, false) *    (a + 1)    % MOD);
    } else if(g == true){
        if(a - b > 0)
        add_to(F[l][f][g], 1ll * dp(l + 1,  true,  true) * (a - b) % MOD);
        add_to(F[l][f][g], 1ll * dp(l + 1, false,  true) * (k - b) % MOD);
    } else {
        add_to(F[l][f][g], 1ll * dp(l + 1,  true,  true) * calc(a, b) % MOD);
        add_to(F[l][f][g], 1ll * dp(l + 1,  true, false) * calc(a, k) % MOD);
        add_to(F[l][f][g], 1ll * dp(l + 1, false,  true) * calc(k, b) % MOD);
        add_to(F[l][f][g], 1ll * dp(l + 1, false, false) * calc(k, k) % MOD);
    }
    return F[l][f][g];
}
i64 qread(){
    i64 w = 1, c, ret;
    while((c = getchar()) >  '9' || c <  '0') w = (c == '-' ? -1 : 1); ret = c - '0';
    while((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + c - '0';
    return ret * w;
}
int main(){
    int T = qread(); k = qread();
    up(1, T, _){
        i64 n = qread(), nn = n; int a = 0;
        i64 m = qread(), mm = m; int b = 0;
        mm = m = min(n, m);
        while(nn) A[++ a] = nn % k, nn /= k;
        while(mm) B[++ b] = mm % k, mm /= k;
        int c = max(a, b);
        up(a + 1, c, i) A[i] = 0;
        up(b + 1, c, i) B[i] = 0;
        up(1, c, i){
            F[i][0][0] = F[i][0][1] = -1;
            F[i][1][0] = F[i][1][1] = -1;
        }
        F[c + 1][1][1] = 1;
        F[c + 1][1][0] = 0;
        F[c + 1][0][1] = 0;
        F[c + 1][0][0] = 0;
        int w = 0;
        add_to(w, dp(1, 0, 0));
        add_to(w, dp(1, 0, 1));
        add_to(w, dp(1, 1, 0));
        add_to(w, dp(1, 1, 1));
        int ans = ((m + 1) % MOD * ((n + 1) % MOD) % MOD - w + MOD) % MOD;
        if(m % 2 == 0)
            ans = (ans - (m / 2) % MOD * ((m + 1) % MOD) % MOD + MOD) % MOD;
        else 
            ans = (ans - m % MOD * (((m + 1) / 2) % MOD) % MOD + MOD) % MOD;
        printf("%d\n", ans);
    }
    return 0;
}