洛谷 P5509 派遣
心路历程：
每想到一种思路，就有一种要做出来的感觉。但一接着想就会发现这种方法有一些极小的问题，但是我没法解决。。。
于是就再换思路。。。
最后在请教了出题人神仙zcq之后，终于做出来了 ~~ (面向数据编程 ~~
口胡一下思路：
首先，我们手玩一波柿子。
[sum_{x=0}^{n}prod_{y=0}^{x}frac{x}{kx+y-x}=
]
[=prod_{x=0}^nprod_{y=0}^{k}(frac{x}{kx+y-x}+1)
]
[=prod_{x=0}^nprod_{y=0}^{k}frac{kx+y}{kx+y-x}
]
[=prod_{x=0}^{n}frac{prod_{i=1}^x(kx+k-i)}{prod_{j=1}^x(kx-j)}
]
[=frac{prod_{i=1}^{n-1}(kn-i)}{prod_{j=1}^{k-1}(kj-j)}
]
[=frac{(nk-1)!}{(nk-n-1)!n!(k-1)^n}
]
然后我们看怎么求这个东西。
大概就是把分子和分母写成
[frac{p=a*m^x}{q=b*m^y}
]
(m是模数)的形式。
然后。。。
如果(x>y)，那么约分后(pequiv 0)，所以(a=0)即可，输出(0)
如果(x<y)，那么约分后(qequiv 0)，所以无论(a)取什么值，都不可能满足条件，输出(-1)
如果(x=y)，那么(pequiv 0,qequiv 0),p!=0,q!=0，这样可以用逆元求出值
额，对，出处是i_m_a_的博客
（还有，他的博客哪里写成了p=0,q=0,而不是同余（大雾
emmmm..
Code
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
const ll P = 1145141;
ll T;
ll n,k;
ll f[P+1];
inline void readx(ll &x)
{
x=0;
int s=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
s=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+ch-'0';
ch=getchar();
}
x*=s;
}
inline void pre()
{
f[0]=1;
for(int i=1;i<P;++i)
f[i]=f[i-1]*i%P;
}
inline ll qpow(ll a,ll b)
{
ll x=1;
while(b)
{
if(b&1)
x=x*a%P;
a=a*a%P;
b>>=1;
}
return x;
}
inline ll inv(ll x)
{
return qpow(x,P-2);
}
int main()
{
pre();
readx(T);
while(T--)
{
readx(n);readx(k);
ll a_mo=1,a_de=1,x_mo=0,x_de=0;
ll r=n*k-1;
while(r)
{
a_mo=a_mo*f[r%P]%P;
r/=P;
x_mo+=r;
}
a_mo=a_mo*qpow(f[P-1],x_mo)%P;
//处理分子
ll tmp=0;
r=k-1;
while(r%P==0)
{
++tmp;
r/=P;
}
tmp*=(n-1);
a_de=qpow(r,n-1);
x_de+=tmp;
r=n*k-n;
tmp=0;
while(r)
{
a_de=a_de*f[r%P]%P;
r/=P;
tmp+=r;
}
a_de=a_de*qpow(f[P-1],tmp)%P;
x_de+=tmp;
r=n-1;
tmp=0;
while(r)
{
a_de=a_de*f[r%P]%P;
r/=P;
tmp+=r;
}
a_de=a_de*qpow(f[P-1],tmp)%P;
x_de+=tmp;
//处理分母
ll ans=a_mo*inv(a_de)%P;
if(x_mo>x_de)
printf("0
");
else if(x_mo<x_de)
printf("-1
");
else
printf("%lld
",ans);
}
return 0;
}