HDUOJ 6372 - sacul

题面

某巨犇发现了一种叫做海绵宝宝 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=1nj=1kF(i,j)\sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{k} F(i, j)
并且结果需对 109+710^9 + 7 取模。

数据范围

0<n1090 < n \le 10^9

0<c,k1050 < c, k \le 10^5

题目链接

分析

在比赛的时候立马联想到了之前做过的一道题:HDUOJ 4349 - Xiao Ming’s Hope

考虑 Lucas 定理:

(nm)(nmodpmmodp)(n/pm/p)(modp)(nmodpmmodp)(n/pmodpm/pmodp)(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}

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

严格地说,记 NiN_innpp 进制下的第 ii 位,MiM_immpp 进制下的第 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 项,显然有 0Ni,Mi<p0 \le N_i, M_i < p

  • NiMiN_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)modp\binom{n}{m} \mod p,若 nnpp 进制下的每一位都不小于 mmpp 进制下的对应位,则有 (nm)0(modp)\binom{n}{m} \not \equiv 0 \pmod p

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


另外注意到计算 F(n,k)F(n, k) 的过程中涉及矩阵乘法,我又联想到之前做过的一道题:HDUOJ 6331 - Walking Plan。我们可以借助那道题的思想,把矩阵乘法和图论知识联系在一起。

既然 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 定理得到的结论,如果 iipp 进制下每一位都不小于 jjpp 进制下的对应位,那么我们就建一条有向边:iji \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 都有 0x<p0 \le x < p,试问满足 x1x2xkx_1 \le x_2 \le \dots \le x_k 的排列方案有多少种?

我好像又联想到了之前做过的一道题:HDUOJ 3037 - Saving Beans。用其中类似的思想可以解决这一问题:

解:原问题可转化为 x1<(x2+1)<(x3+2)<<(xk+k1)x_1 < (x_2 + 1) < (x_3 + 2) < \dots < (x_k + k - 1) 的方案数。换句话说,就是记 yi=xi+i1y_i = x_i + i - 1y1<y2<<yky_1 < y_2 < \dots < y_k 的方案数,其中 0y<p+k10 \le y < p + k - 1。显然等效于 p+k1p + k - 1 种值里面取 kk 种不同的值:
(p+k1k)=(p+k1p1)\binom{p + k - 1}{k} = \binom{p + k - 1}{p - 1}

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

(p+(j+1)1p1)=(j+pp1)\binom{p + (j + 1) - 1}{p - 1} = \binom{j + p}{p - 1}

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

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

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

i=1nj=1k(j+pp1)i=j=1ki=1n(j+pp1)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=1ki=1n(j+pp1)i\sum\limits_{j = 1}^{k} \sum\limits_{i = 1}^{n} \binom{j + p}{p - 1}^i

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

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

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

完整参考代码

%%%

This blog is under a CC BY-NC-SA 4.0 Unported License.
Link to this article: https://blog.codgician.pw/2018/08/10/hduoj-6372/