自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:11:30，当前版本为作者最后更新于2020-11-22 12:19:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题面传送门。

---

由题意，对于每个士兵 $i$，要么选，对答案产生 $a_i(\frac{x}{i-x})$ 倍的贡献，要么不选，对答案产生 $1$ 倍的贡献。

由此可知每个士兵之间是独立的，不相互影响，则根据乘法原理，答案应为

$$\prod_{i=1}^{nk-1}(a_i+1)$$

大力展开，即

$$\prod_{i=0}^{n-1}\prod_{j=0,ik+j\neq0}^{k-1}\left(\frac{i}{ik+j-i}+1\right) $$

即

$$\prod_{i=0}^{n-1}\prod_{j=0,ik+j\neq0}^{k-1}\frac{ik+j}{ik+j-i} $$

不妨将分子分母拆开来看：

• 分子：

  $$\prod_{i=0}^{n-1}\prod_{j=0,ik+j\neq0}^{k-1}ij$$

  即

  $$(nk-1)!$$

• 分母：Markdown 渲染好像不太行。。。

  |$i/j$|$0$|$1$|$2$|$\cdots$|$k-1$ |:-:|:-:|:-:|:-:|:-:|:-:|:-:| |$0$|/|$1$|$2$|$\cdots$|$k-1$ |$1$|$k-1$|$k-1+1$|$k-1+2$|$\cdots$|$2(k-1)$ |$2$|$2(k-1)$|$2(k-1)+1$|$2(k-1)+2$|$\cdots$|$3(k-1)$ |$\cdots\$|$\cdots$|$\cdots$|$\cdots$|$\cdots$|$\cdots$| |$n-2$|$(n-2)(k-1)$|$(n-2)(k-1)+1$|$(n-2)(k-1)+2$|$\cdots$|$(n-1)(k-1)$ |$\ \ n-1\ \$|$\ \ (n-1)(k-1)\ \$|$\ \ (n-1)(k-1)+1\ \$|$\ \ (n-1)(k-1)+2\ \$|$\ \ \cdots\ \$|$\ \ n(k-1)\ \$

  不难发现 $1\sim n(k-1)$ 各出现了一次，且每一行的第一个数与上一行的最后一个数相等，即 $k-1, 2(k-1), \cdots, (n-1)(k-1)$ 多出现了一次。

  那么分母为

  $$[n(k-1)]!\times \prod_{i=1}^{n-1}i(k-1)$$

  即

  $$(nk-n)!\times (k-1)^{n-1}\times (n-1)!$$

综上，可知答案为：

$$\dfrac{(nk-1)!}{(nk-n)!\times (k-1)^{n-1}\times (n-1)!} $$

但是 $nk$ 已经达到了 $10^{18}$ 的数量级，怎么求这玩意的阶乘？

---

求 $v!\ (v>10^8)$ 模 $p\ (p<10^8)$：

抓住模数 $p=1145141$，对 $1\sim v$ 的每个数取模，最终会得到 $\left\lfloor \dfrac{v}{p}\right\rfloor$ 个 $0\sim p-1$ 和 $1\sim (v\bmod p)$。

将所有 $p$ 的倍数除以 $p$，得到 $\left\lfloor \dfrac{v}{p}\right\rfloor$ 个 $1\sim p-1$ 和 $1\sim (v\bmod p)$ 和 $1\sim \left\lfloor \dfrac{v}{p}\right\rfloor$。

则答案为

$$(p-1)!^{\left\lfloor \frac{v}{p}\right\rfloor}\times (v\bmod p)!\times \left(\left\lfloor\frac{v}{p}\right\rfloor\right)! $$

预处理 $1\sim p-1$ 的阶乘，用递归 + 快速幂即可做到 $\mathcal O(\log v)$ 计算。

根据威尔逊定理 $(p-1)!\equiv -1\ (\bmod\ p),p\in \rm{prime}$，原答案可化简为

$$(-1)^{\left\lfloor \frac{v}{p}\right\rfloor}\times (v\bmod p)!\times \left(\left\lfloor\frac{v}{p}\right\rfloor\right)! $$

这样可以做到 $\mathcal O(\log_p v)$ 计算，可以近似看做常数。

代码：

ll cal(ll v){return v<mod?fc[v]:fc[v%mod]*((v/mod)&1?-1:1)%mod*cal(v/mod)%mod;}

---

接下来计算出分子和分母各含有多少个 $p$：

• $v!$：一般的，$v!$ 中含有质因子 $p$ 的个数应为 $\sum_{i=1,v\geq p^i}\left\lfloor \dfrac{v}{p^i}\right\rfloor$，但此处 $v<p^3$，则可以化简为 $\left\lfloor \dfrac{v}{p}\right\rfloor+\left\lfloor \dfrac{v}{p^2}\right\rfloor$。
• $(k-1)^{n-1}$：
  • 当 $p\mid k-1$ 时，$p$ 的个数为 $n-1$，此时一定无解（即输出 $\tt{-1}$），读者自证不难。
  • 当 $p\nmid k-1$ 时，$p$ 的个数为 $0$，此时一定有解，读者自证不难。

综上，特判掉 $p\mid k-1$ 的情况，记 $c$ 为最终答案含有质因子 $p$ 的个数，则

$$c=\left\lfloor \dfrac{nk-1}{p}\right\rfloor+\left\lfloor \dfrac{nk-1}{p^2}\right\rfloor-\left(\left\lfloor \dfrac{nk-k}{p}\right\rfloor+\left\lfloor \dfrac{nk-k}{p^2}\right\rfloor\right)-\left\lfloor \dfrac{n}{p}\right\rfloor $$

可以证明 $c\geq 0$。

那么，当 $c>0$ 时，$ans\equiv 0\ (\bmod\ p)$，输出 $0$ 即可，否则计算上文推出的答案：

$$\dfrac{(nk-1)!}{(nk-n)!\times (k-1)^{n-1}\times (n-1)!} $$

计算快速幂时根据费马小定理将质数 $n-1$ 模 $p-1$，时间复杂度 $\mathcal O(p+t\log p)$。

---

代码片段：

ll ksm(ll a,ll b){
	ll s=1,m=a;
	while(b){
		if(b&1)s=s*m%mod;
		m=m*m%mod,b>>=1;
	} return s;
} ll inv(ll x){return ksm(x%mod,mod-2);}
ll t,n,k,fc[mod+5];
ll cal(ll v){return v<mod?fc[v]:fc[v%mod]*((v/mod)&1?-1:1)%mod*cal(v/mod)%mod;}

int main(){
	cin>>t,fc[0]=1;
	for(int i=1;i<mod;i++)fc[i]=fc[i-1]*i%mod;
	while(t--){
		n=read(),k=read();
		if(n==1)pc('1');
		else if((k-1)%mod==0)pc('-'),pc('1');
		else{
			ll l=n*k-n,r=n*k-1;
			if(r/mod+r/mod/mod>l/mod+l/mod/mod+(n-1)/mod)pc('0');
			else print(cal(r)*inv(cal(l))%mod*inv(ksm(k-1,(n-1)%(mod-1))*cal(n-1))%mod);
		} pc('\n');
	} 
	return flush(),0;
}