派遣-题解
Hope2075
2019-08-14 15:26:41
这道题如果能推出式子，就能得高分，如果再用些技巧计算，就能AC
## 算法1
按照题意，枚举所有可能的选法
时间复杂度$O(t\cdot 2^{nk})$
期望得分：10分
## 算法2
设不选第$i$个士兵会使能力值变为原来的$a_i$倍，那么答案就是$\prod_{i=1}^{nk-1}(1+a_i)$
这样考虑：每个士兵从括号里的两项中选择一项，得到某个选法的答案
根据题目的数据范围，在$n,k\le 100$时，不会出现分子或分母在模意义下为0的情况
这部分可以用逆元直接算，也可以分别计算分子和分母
时间复杂度：$O(tnk)$
期望得分：21分
## 算法3
利用算法2打表，找出#3或#4的规律
不过规律比较复杂，不太容易看出来
期望得分：33-46分
## 先推一下式子
现在需要对式子进一步变形
$\prod_{i=1}^{nk-1}(1+a_i)$
$=\prod_{i=1}^{nk-1}(1+\frac{\lfloor \frac{i}{k}\rfloor}{i-\lfloor \frac{i}{k}\rfloor})$
$=\prod_{i=1}^{nk-1}(\frac{i}{i-\lfloor \frac{i}{k}\rfloor})$
考虑把分子和分母分别计算
分子很好算，就是$(nk-1)!$
分母：
$\prod_{i=1}^{nk-1}(i-\lfloor \frac{i}{k}\rfloor)$
添加一项
$=\prod_{i=1}^{nk}(i-\lfloor \frac{i}{k}\rfloor) \div (nk-\lfloor \frac{nk}{k}\rfloor)$
$=\prod_{i=0}^{nk-1}(i+1-\lfloor \frac{i+1}{k}\rfloor) \div (nk-n)$
把连乘变成两个
$=\prod_{i=0}^{n-1}\prod_{j=0}^{k-1}(ik+j+1-\lfloor \frac{ik+j+1}{k}\rfloor) \div (nk-n)$
将其中一个拆出来
$=\prod_{i=0}^{n-1}\prod_{j=0}^{k-2}(ik+j+1-\lfloor \frac{ik+j+1}{k}\rfloor)\cdot \prod_{i=0}^{n-1}(ik+(k-1)+1-\lfloor \frac{ik+(k-1)+1}{k}\rfloor) \div (nk-n)$
消去向下取整符号
$=\prod_{i=0}^{n-1}\prod_{j=0}^{k-2}(ik+j+1-i)\cdot \prod_{i=0}^{n-1}(ik+k-(i+1)) \div (nk-n)$
然后整理
$=\prod_{i=0}^{n-1}\prod_{j=0}^{k-2}[i(k-1)+j+1]\cdot \prod_{i=0}^{n-1}[(k-1)(i+1)] \div (nk-n)$
$=\prod_{i=0}^{n(k-1)-1}(i+1)\cdot (k-1)^n\cdot \prod_{i=0}^{n-1}(i+1) \div (nk-n)$
$=\prod_{i=1}^{n(k-1)}i\cdot (k-1)^n\cdot \prod_{i=1}^{n}(i) \div (nk-n)$
$=(nk-n)!\cdot (k-1)^n\cdot n! \div (nk-n)$
$=(nk-n-1)!\cdot n! \cdot (k-1)^n$
经过推导，变成了简单的形式
所以答案是$\frac{(nk-1)!}{(nk-n-1)!\cdot n! \cdot (k-1)^n}$
另一个表示方法是：用组合数
$\frac{C_{nk-1}^n}{(k-1)^n}$
然后就需要考虑如何计算
## 算法4
计算阶乘，然后求逆元
模数并不大，可以直接预处理阶乘
而对于#3和#4的范围，不会导致出现模意义下为0的情况
时间复杂度$O(nk+t\log n+t\log m)$,$m$为模数
期望得分46分
## 算法5
利用上面的组合数表示，同时发现范围并不大
可以先把数据全读进来确定范围，然后用杨辉三角求组合数
时间复杂度$O(nk+t\log n+t\log m)$
期望得分46分
## 算法6
用阶乘表示，把分子和分母求出来
需要求出$m$因子的个数，以及除掉所有$m$因子后在模$m$意义下的结果
威尔逊定理：
$( p -1 )! \equiv -1 (mod\ p)$,$p$是质数
先预处理$1$到$m-1$的阶乘
然后考虑任意阶乘如何计算
对于一个数$n$，首先考虑$1$到$n$中，模$m$同余$1$到$m$的连续$m$个数有几组，也就是$\lfloor \frac{n}{m} \rfloor$组
这一部分中，每一组余$1$到$m-1$的数乘起来就是$-1$，余$m$的那一个数单独考虑
对于不能构成完整一组的部分，用预处理的阶乘可以直接求出来
而对于模$m$余$0$的$\lfloor \frac{n}{m} \rfloor$个数，把它们分别除以$m$，剩下的部分还是阶乘，问题与原来一样，但规模减小，可以递归处理，也可以用循环
这样，就可以统计$m$因子的个数，以及剩余部分模$m$意义下的值
对于乘方部分就很简单了，先计算原数中$m$因子的个数，然后乘以指数就是因子总数，剩余部分用快速幂就能求出来
计算完后，比较分子和分母中$m$因子的个数
如果分子多，那么约分后$p=0$，所以$a=0$即可，输出0
如果分母多，那么约分后$q=0$，所以无论$a$取什么值，都不可能满足条件，输出-1
如果一样多，那么$p\ne 0,q\ne 0$，这样可以用逆元求出值
时间复杂度$O(m+t\log n+t \log k)$
期望得分100分
代码：
这里统计的是因子数之差，并且求的值是除掉所有$m$因子后，在$m$意义下的值
```cpp
#include<cstdio>
long long read(){
long long n=0;char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9'){n=n*10+c-'0';c=getchar();}
return n;
}
char res[25];
void write(long long num){
int t=0;
while(num){res[t++]=num%10+'0';num/=10;}
while(t--)putchar(res[t]);
}
const long long M=1145141;
long long fpow(long long a,long long n){
long long ans=1;
while(n){
if(n&1)ans=ans*a%M;
n>>=1;
a=a*a%M;
}
return ans;
}
long long f[M];
void pre(){
f[0]=1;
for(int i=1;i<M;i++){
f[i]=f[i-1]*i%M;
}
}
int t;long long n,k;
int main(){
t=read();
pre();
while(t--){
n=read();k=read();
long long r,c=0,c0;long long num1=1,num2=1;
c0=0;
r=k-1;
while(r%M==0){
c0++;
r/=M;
}
c0*=(n-1);
num1=fpow(r,n-1);
c-=c0;
c0=0;
r=n*k-1;
while(r){
num2=num2*f[r%M]%M;
r/=M;
c0+=r;
}
num2=num2*fpow(f[M-1],c0)%M;
c+=c0;
c0=0;
r=n*k-n;
while(r){
num1=num1*f[r%M]%M;
r/=M;
c0+=r;
}
num1=num1*fpow(f[M-1],c0)%M;
c-=c0;
c0=0;
r=n-1;
while(r){
num1=num1*f[r%M]%M;
r/=M;
c0+=r;
}
num1=num1*fpow(f[M-1],c0)%M;
c-=c0;
num2=num2*fpow(num1,M-2)%M;
if(c>0){puts("0");}
else if(c==0){write(num2);putchar('\n');}
else puts("-1");
}
}
```