题面

某巨犇发现了一种叫做海绵宝宝 HMBB\text{HMBB} 的神奇矩阵。

给定 ii ，记 pp 是第 ii 个质数。

矩阵 HMBBn\text{HMBB}_{n} 的大小为 pn×pnp^n \times p^n ，同时：

HMBBn[i][j]={0(ij)≡0(modp)1(ij)≢0(modp) \text{HMBB}_{n}[i][j] = \begin{cases} 0 & \binom{i}{j} \equiv 0 \pmod p \\ 1 & \binom{i}{j} \not \equiv 0 \pmod p \\ \end{cases}

记 F(n,k)F(n, k) 为矩阵 (HMBBn)k(\text{HMBB}_n)^k 中所有元素之和。给定 n,kn, k ，试求：

∑i=1n∑j=1kF(i,j)(mod109+7) \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{k} F(i, j) \pmod {10^9 + 7}

数据范围：0<n≤109,0<c,k≤1050 < n \le 10^9, 0 < c, k \le 10^5

题目链接：HDUOJ 6372: sacul

分析

考虑 Lucas 定理：

(nm)≡(nmod  pmmod  p)⋅(n/pm/p)(modp)≡(nmod  pmmod  p)⋅(n/pmod  pm/pmod  p)⋅(n/p2m/p2)(modp)… \begin{aligned} \binom{n}{m} & \equiv \binom{n \mod p}{m \mod p} \cdot \binom{n / p}{m / p} \pmod p \\ & \equiv \binom{n \mod p}{m \mod p} \cdot \binom{n / p \mod p}{m / p \mod p} \cdot \binom{n / p^2}{m / p^2} \pmod p \\ & \dots \\ \end{aligned}

不难发现其本质就是把 nn 和 mm 按照 pp 进制进行拆位，对每一位计算组合数后再乘起来。

严格地说，记 NiN_i 为 nn 在 pp 进制下的第 ii 位，MiM_i 为 mm 在 pp 进制下的第 ii 位，则有：

(nm)≡∏(NiMi)(modp) \binom{n}{m} \equiv \prod \binom{N_i}{M_i} \pmod p

接下来我们来看看什么时候存在 (nm)≡0(modp)\binom{n}{m} \equiv 0 \pmod p 。

首先，对于上面连乘式中的第 ii 项，显然有 0≤Ni,Mi<p0 \le N_i, M_i < p 。

  • 若 Ni≥MiN_i \ge M_i ，那么 (NiMi)\binom{N_i}{M_i} 一定是整数，又由于 Ni,Mi<pN_i, M_i < p ，所以模 pp 一定是正数（不可能存在 pp 这一因子）；
  • 若 Ni<MiN_i < M_i ，那么 (NiMi)=0\binom{N_i}{M_i} = 0 ，模 pp 自然为 00 。

换句话说，对于 (nm)mod  p\binom{n}{m} \mod p ，若 nn 在 pp 进制下的每一位都不小于 mm 在 pp 进制下的对应位，则有 (nm)≢0(modp)\binom{n}{m} \not \equiv 0 \pmod p 。

貌似题目标题反过来读就是题解诶，然而比赛的时候想到这里后我就不会了 QAQ。

既然 HMBB\text{HMBB} 是一个 0101 矩阵，我们不妨把它联想成一个可达性矩阵，由此可以将其对应成一张有向无权图。进一步，HMBB[i][j]\text{HMBB}[i][j] 代表从 ii 出发，走 11 步到达 jj 的方案数。再进一步，(HMBB[i][j])k(\text{HMBB}[i][j])^k 代表从 ii 出发，恰好走 kk 步到达 jj 的方案数。

根据上面根据 Lucas 定理得到的结论，如果 ii 在 pp 进制下每一位都不小于 jj 在 pp 进制下的对应位，那么我们就建一条有向边：i→ji \to j 。于是 F(n,k)F(n, k) 就变成了在包含 pnp^n 个点的这样的图中恰好走 kk 步从任意点出发到达任意点的方案总数。

现在我们考虑恰好走 jj 步的路径，那么显然这条路径上有 j+1j + 1 个点，同时这条路径上每一个点都满足：每个数的 pp 进制上的每一位不小于上一个数的对应位。这又回到了一个经典排列组合问题：

现有 kk 个数：x1,x2,…xkx_1, x_2, \dots x_k ，已知对于每个 xx 都有 0≤x<p0 \le x < p ，试问满足 x1≤x2≤⋯≤xkx_1 \le x_2 \le \dots \le x_k 的排列方案有多少种？

这可转化为 x1<(x2+1)<(x3+2)<⋯<(xk+k−1)x_1 < (x_2 + 1) < (x_3 + 2) < \dots < (x_k + k - 1) 的方案数。换句话说，就是记 yi=xi+i−1y_i = x_i + i - 1 ，y1<y2<⋯<yky_1 < y_2 < \dots < y_k 的方案数，其中 0≤y<p+k−10 \le y < p + k - 1 。显然等效于 p+k−1p + k - 1 种值里面取 kk 种不同的值：

(p+k−1k)=(p+k−1p−1) \binom{p + k - 1}{k} = \binom{p + k - 1}{p - 1}

所以说对于每一位实际上就是上面公式里面带入 k=j+1k = j + 1 ，我们可采取的方案数都为：

(p+(j+1)−1p−1)=(j+pp−1) \binom{p + (j + 1) - 1}{p - 1} = \binom{j + p}{p - 1}

记这些数的 pp 进制都有 ii 位，显然这 ii 个位之间是相对独立的，因此方案数为：

F(i,j)=(j+pp−1)i F(i, j) = \binom{j + p}{p - 1} ^ i

那么题目所要求的值即为：

∑i=1n∑j=1k(j+pp−1)i=∑j=1k∑i=1n(j+pp−1)i \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{k} \binom{j + p}{p - 1}^i = \sum\limits_{j = 1}^{k} \sum\limits_{i = 1}^{n} \binom{j + p}{p - 1}^i

由上述分析我们已经知道答案即：

∑j=1k∑i=1n(j+pp−1)i \sum\limits_{j = 1}^{k} \sum\limits_{i = 1}^{n} \binom{j + p}{p - 1}^i

其中后半部分可看作一个等比数列，用等比数列公式即可直接求出（需要注意特判公比为 11 的情况）。

如果我们预处理阶乘的话，求一个组合数的的复杂度为 O(log⁡N)\mathcal{O}(\log{N}) 级别，因此总复杂度为 O(Nlog⁡N)\mathcal{O}(N\log{N}) 级别。

另外由实践得知，第 10510^5 个质数为 12997091299709 ，因此我们在处理阶乘的时候至少需要处理至 1299709+1051299709 + 10^5 。

最后附上 我的代码 以供参考。

%%%