运输货物
题目描述：
小 \(Z\) 要用 \(n+1\) 只骡子运送 \(k\) 种物资。每只骡子可以任选物资运输（也可以运输 \(0\) 种物资）。
但是 \(0 \sim n-1\) 这 \(n\) 只骡子不能运输同一种物资。
即不能存在一种物资同时被 \(0 \sim n-1\) 的骡子运输。
并且设 \(1 \sim n\) 这 \(n\) 只骡子不能运输全部 \(k\) 种物资。
求运输方案。
简化题意：
给定 \(n,k\)，求有多少个 \(n+1\) 行 \(k\) 列的 \(01\) 矩阵，使得：
- 前 \(n\) 行不能存在一列全 \(1\)。
- 后 \(n\) 行必须存在至少一列全 \(0\)。
\(n,k \leq 1e18\)。\(t\) 组数据，\(t \leq 1e5\)。
解决方案：
先考虑中间的 \(n-1\) 行。
设有 \(i\) 列全 \(0\)，\(j\) 列全是 \(1\)。
选择列的方案为 \(\binom{k}{i} * \binom{k - i}{j}\)。
其他列填数总方案为 \(2^{n-1}-2^{k-i-j}\)。
对于第一行，\(j\) 列全为 \(1\) 的只能填 \(0\)，其他格子可填集合不变。方案为 \(2^{k-j}\)。
对于最后一行， \(i\) 列全为 \(0\) 的至少一个填 \(0\)，其他格子可填集合不变。方案为 \(2^{k-i} \times (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-i}2^{k-j}(2^i-1) \]可以直接枚举 \(i,j\) 计算答案，复杂度 \(O(tn^2)\)。
考虑二项式定理优化。
原式可化简为：
\(=\sum \limits_{i=0}^{k} \binom{k}{i} \sum \limits_{j=0}^{k-i} \binom{k-i}{j}(2^{n-1}-2)^{k-i-j}2^{k-i-j}2^k(2^i-1)\)
\(=\sum \limits_{i=0}^{k} \binom{k}{i} 2^k \sum \limits_{j=0}^{k-i} \binom{k-i}{j}(2^{n}-4)^{k-i-j}(2^i-1)\)
\(=2^k\sum \limits_{i=0}^{k} \binom{k}{i} (2^i-1)(2^n-3)^{k-i}\)
\(=2^k\{\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}\}\)
\(=2^k \{ (2^n-1)^k - (2^n-2)^k \}\)
现在答案可以用扩展欧拉定理加快速幂直接计算。
标签：运输,limits,sum,Solution,列全,binom,物资,货物 From： https://www.cnblogs.com/foreverlcrun0817/p/18546933