bzoj 2445

bzoj 2445
求n个点的symmetric labeled clique的个数,然后求m的次方。
答案就是\(m^{\sum_{x|n}\frac{n!}{(x!)^{\frac{n}{x}}{\frac{n}{x}}!}}\).
求这个,首先减少次方数,p=999999599是一个质数。
\(m^{p-1}\equiv 1 (\% p)\),则只需求指数%(p-1)。
但是不容易一下求出阶乘。
注意到\(999999599=2*13*5281*7283\),可以利用威尔逊定理。
\(p\)为素数时,\((p-1)!\equiv -1(\% p)\)。
那么有\(n! \equiv (-1)^{\frac{n}{p}}*(n\% p)!*\frac{n}{p}!\).
那么可以分别求指数对于\(2\)、\(13\)、\(5281\)、\(7283\)的余。
最后可以用中国剩余定理进行合并,出模(p-1)意义下的指数值(注意exgcd出来的值的正负)。
最后做一次快速幂。

Leave a Reply

Your email address will not be published. Required fields are marked *