运输货物题解

小 Z 要用 \(n+1\) 只骡子运送 \(k\) 种物资。每只骡子可以任选物资运输（也可以选择运输 \(0\) 种物资）。

由于骡子并不是马，所以 没有任何一种物资能够同时被 第 \(0\sim n-1\) 只这 \(n\) 只骡子运输。

由于骡子并不是马，所以 第 \(1\sim n\) 只 这 \(n\) 只骡子并不能运输全部的 \(k\) 种物资。

根据以上 骡子并不是马 原则，一共有多少种运输方案？
请给出答案 对 \(10^9+7\) 取模的结果。

共有 \(T\) 组测试数据。

数据范围：
对于所有数据，满足 \(0\le T\le 10^5,3\le n,k\le 10^{18}\)。

子任务编号	分值	数据范围
\(1\)	\(5pts\)	\(T=0\)
\(2\)	\(25pts\)	\(T\le 10,n,k\le 4\)
\(3\)	\(35pts\)	\(T=1,n,k\le 3000\)
\(4\)	\(35pts\)	无特殊限制

题目可以转化为：
求出满足下列条件的 \(n+1\) 行 \(k\) 列的 \(01\) 矩阵的数量：

• 前 \(n\) 行（第 \(0\sim n-1\) 行）每列至少存在一个 \(0\)。
• 后 \(n\) 行（第 \(1\sim n\)）至少有一列全是 \(0\)。

可以发现题意简化后，第 \(1\sim n-1\) 行这 \(n-1\) 行需要满足上面两个条件，因此我们把原矩阵拆成第 \(0\) 行、第 \(1\sim n-1\) 行、第 \(n\) 行三部分进行计数。

首先对于第二部分（第 \(1\sim n-1\) 行），我们需要强制规定一些限制，以方便计数，怎么规定呢？

根据条件，我们可以想出：对于第二部分，设有 \(i\) 列全是 \(0\)，有 \(j\) 列全是 \(1\)。

列只要别选重，时可以随便选的，因此共有 \(\binom{k}{i}\binom{k-i}{j}\) 种选法。对于没有选到的列，我们随便填即可（别填满 \(0\) 或 \(1\) 了），那么 \(k-i-j\) 没选的列共有 \((2^{n-1}-2)^{k-i-j}\) 种合法方案。

然后分别考虑第一三部分。

对于第一部分：
如果有一列第二部分全放了 \(1\)，那么第一部分只能放 \(0\)，其他的随便放即可，共 \(2^{k-j}\) 种放法。

对于第二部分：
如果有一列已经放了 \(1\)，那么我们在第三部分可以随便放，如果有几列全放了 \(0\)，那么我们需要至少留一列放 \(0\)，共 \(2^{k-i}(2^i-1)\)。

把上面那些东西乘在一块就是：

\[\sum\limits_{i=0}^k\sum\limits_{j=0}^{k-i}\binom{k}{i}\binom{k-i}{j}(2^{n-1}-2)^{k-i-j}2^{k-j}2^{k-i}(2^i-1) \]

这个可以直接 \(\mathcal{O}(k^2)\) 做，但不足以通过本题数据。

我们把能往外放的东西尽量往外放试试，也就是无脑提取公因式：

\[\begin{aligned} YS&=\sum\limits_{i=0}^k\sum\limits_{j=0}^{k-i}\binom{k}{i}\binom{k-i}{j}(2^{n-1}-2)^{k-i-j}2^{k-j}2^{k-i}(2^i-1)\\ &=\sum\limits_{i=0}^k\binom{k}{i}2^{k-i}(2^i-1)\sum\limits_{j=0}^{k-i}\binom{k-i}{j}(2^{n-1}-2)^{k-i-j}2^{k-j}\\ &=2^k\sum\limits_{i=0}^k\binom{k}{i}2^{-i}(2^i-1)\sum\limits_{j=0}^{k-i}\binom{k-i}{j}(2^{n-1}-2)^{k-i-j}2^{k-j} \end{aligned}\]

注：\(YS=\) 原式。

然后就提不动了，考虑使用公式。

该用哪个呢？

\(\binom{k-i}{j}(2^{n-1}-2)^{k-i-j}\) 这个看上去可以二项式定理化简。

但是后面的 \(2^{k-j}\) 的很难受，如果是 \(2^{k-i-j}\) 就好了，我们需要 \(2^{-i}\)。

等等！\(2^{-i}\)？这个我们可以从外面拿回来！

于是

\[\begin{aligned} YS&=2^k\sum\limits_{i=0}^k\binom{k}{i}2^{-i}(2^i-1)\sum\limits_{j=0}^{k-i}\binom{k-i}{j}(2^{n-1}-2)^{k-i-j}2^{k-j}\\ &=2^k\sum\limits_{i=0}^k\binom{k}{i}(2^i-1)\sum\limits_{j=0}^{k-i}\binom{k-i}{j}(2^{n-1}-2)^{k-i-j}2^{k-i-j}\\ &=2^k\sum\limits_{i=0}^k\binom{k}{i}(2^i-1)\sum\limits_{j=0}^{k-i}\binom{k-i}{j}[2(2^{n-1}-2)]^{k-i-j}\\ &=2^k\sum\limits_{i=0}^k\binom{k}{i}(2^i-1)[2(2^{n-1}-2)+1]^{k-i}\\ &=2^k\sum\limits_{i=0}^k\binom{k}{i}(2^i-1)(2^n-3)^{k-i}\\ &=2^k\left[\sum\limits_{i=0}^k\binom{k}{i}2^i(2^n-3)^{k-i}-\sum\limits_{i=0}^k\binom{k}{i}(2^n-3)^{k-i}\right]\\ &=2^k[(2^n-1)^k-(2^n-2)^k] \end{aligned}\]

把 \(j\) 所在的那个 \(\sum\) 化简掉之后 \(2^k\sum\limits_{i=0}^k\binom{k}{i}(2^i-1)(2^n-3)^{k-i}\) 看上去不好化简，但实际上可以直接强拆，再分别用二项式定理化简就行了。

最终答案即为

\[2^k[(2^n-1)^k-(2^n-2)^k] \]

这个可以直接用快速幂做。