2025.6.10【ZR NOI模拟赛 T3】 过啥题 题解（Lucas 定理， 数位dp， 组合意义）

为什么70分这么唐考试没写啊。。。。

题意

$T$ 组数据， 每组给定 $n,m,k$， 对于所有长度为 $k$ 并且满足以下条件的 正整数 数列 { a i } \{a_i\} {ai​}， { b i } \{b_i\} {bi​}：

• $\sum _{i=1}^k{a}_i=n$
• $\sum _{i=1}^k{b}_i=m$

计算 $\prod _{i=1}^k\min (a_i,b_i)$ 的和。对 $10007$ 取模。

$1\le T\le 100,1\le k\le n,m\le 10^{18}$

分析

注意到模数比较小， 并且 $n,m$ 范围比较大，感觉起来就是数位 $dp$ 题。

先来尝试给 $\prod _{i=1}^k\min (a_i,b_i)$ 编一个组合意义：发现它就等于 有多少长度为 $k$ 的正整数序列 { x i } \{x_i\} {xi​}，满足 $\forall i\in [1,k],x_i\le a_i且x_i\le b_i$。

那么可以枚举 { x i } \{x_i\} {xi​}，计算一个 { x i } \{x_i\} {xi​} 会被算几次。在 $x_i$ 的基础上调整 $a_i,b_i$，设枚举的 $x_i$ 的和为 $S$，那么答案就等于：

$$\sum _{S=k}^{\min (n,m)}\left(\genfrac{}{}{0ex}{}{S-1}{k-1}\right)\left(\genfrac{}{}{0ex}{}{n-S+k-1}{k-1}\right)\left(\genfrac{}{}{0ex}{}{m-S+k-1}{k-1}\right)$$

将式子化的好看一些。令 $k^{\prime }=k-1,n^{\prime }=n+k^{\prime }-1,m^{\prime }=m+k^{\prime }-1$，
那么答案为：

$$\sum _{S=k^{\prime }}^{\min (n^{\prime },m^{\prime })-k^{\prime }}\left(\genfrac{}{}{0ex}{}{S}{k^{\prime }}\right)\left(\genfrac{}{}{0ex}{}{n^{\prime }-S}{k^{\prime }}\right)\left(\genfrac{}{}{0ex}{}{m^{\prime }-S}{k^{\prime }}\right)$$

注意到 $S$ 如果不在 $[k^{\prime },\min (n^{\prime },m^{\prime })-k^{\prime }]$ 之间那么这个式子的值肯定等于 $0$，因此可以认为对 $S$ 的范围没有限制。

根据 卢卡斯定理，可以将组合数拆成 $mod$ 进制下每位求组合数然后相乘。我们不能枚举 $S$，考虑在 $mod$ 进制下依次考虑 $S$ 的每一位。

此时 $k^{\prime },n^{\prime },m^{\prime }$ 固定，先把它们在 $mod$ 进制下的每一位求出来，用 $0$ 将最高位补到 $\max (n^{\prime },m^{\prime })$ 的最高位。

那么 $n^{\prime }-S$ 就是每一位分别相减，由于是减法，可能会涉及退位，因此我们从高位到低位 $dp$。

发现由于 $S$ 没有范围限制，那么状态只需要记录是否退位。设 $d{p}_{x,0/1,0/1}$ 表示从高到低考虑到第 $x$ 位， $n^{\prime }-S$ 是否向 $x-1$ 位退位， $m^{\prime }-S$ 是否向 $x-1$ 位退位的方案数。转移就是枚举第 $x-1$ 位上 $S$ 的数字，然后乘上这一位上组合数的贡献。

最后答案就是 $d{p}_{0,0,0}$。

复杂度 $O(T\times mod\times {\log }_{mod}\max (n,m))$。

CODE：

// 首先需要根据组合意义推导出来一个简洁的式子。 然后发现模数比较小， 并且形式比较好
// 可以根据lucas定理拆成 mod 进制下数位dp
// 复杂度是 T * mod * log_{mod}max(n, m)
#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
const int mod = 10007;
int fac[mod], inv[mod]; 
LL n, m, k;
int dp[6][2][2]; // dp[x][0/1][0/1] 表示从高到低考虑到第 x 位， 前面确定了 i 的若干位， n - i 前面往 x - 1 是否退位， m - i 往 x - 1 是否退位的方案数之和
inline int Pow(int x, int y) {int res = 1, k = x;while(y) {if(y & 1) res = res * k % mod;y >>= 1;k = k * k % mod;}return res;
}
inline int C(int n, int m) {if(n < m) return 0;return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
inline int solve(LL n, LL m, LL k) {vector< int > N, M, K;while(n) N.pb(n % mod), n /= mod;while(m) M.pb(m % mod), m /= mod;while(k) K.pb(k % mod), k /= mod;int sz = max({N.size(), M.size(), K.size()});while(N.size() < sz) N.pb(0);while(M.size() < sz) M.pb(0);while(K.size() < sz) K.pb(0);memset(dp, 0, sizeof dp);dp[sz][0][0] = 1;for(int i = sz; i > 0; i -- ) // 刷表for(int a = 0; a <= 1; a ++ ) for(int b = 0; b <= 1; b ++ ) if(dp[i][a][b]) for(int c = 0; c <= 1; c ++ ) for(int d = 0; d <= 1; d ++ ) for(int x = 0; x < mod; x ++ ) {int u = N[i - 1] - x + a * mod - c, v = M[i - 1] - x + b * mod - d;if(u >= 0 && u < mod && v >= 0 && v <= mod) dp[i - 1][c][d] = (dp[i - 1][c][d] + dp[i][a][b] * C(x, K[i - 1]) % mod * C(u, K[i - 1]) % mod * C(v, K[i - 1]) % mod) % mod;}return dp[0][0][0];						
}
int main() {fac[0] = 1; for(int i = 1; i < mod; i ++ ) fac[i] = fac[i - 1] * i % mod;inv[mod - 1] = Pow(fac[mod - 1], mod - 2); for(int i = mod - 2; i >= 0; i -- ) inv[i] = inv[i + 1] * (i + 1) % mod;int T; scanf("%d", &T);while(T -- ) {scanf("%lld%lld%lld", &n, &m, &k);k --; n = n + k - 1, m = m + k - 1;printf("%d\n", solve(n, m, k));}return 0;
}