题解 P5509 【派遣】

Alex_Wei · 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：

- 当 $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;
}