TJU 1156 Accepted…

Maigo 题解上说只能用DP,其实排列组合方法是可以的
输入的是p,n, 输出其实就是 (p-1)^(n-1)-(p-1)^(n-2)+(p-1)^(n-3)… (-1)^n*(p-1)
利用等比数列求和公式,能够得到式子,但是,模运算下的除法似乎不只有一解
最后还是想出来了,把原来的 mod 2005 改成 mod 2005*分母,就可以了,能够直接除
但是这样就需要 int64 了…… 似乎会慢一些,但是空间用的是很少的,复杂度O(log(n)),只要在 mod 2005*分母下计算   (p-1)^(n-1) 就可以了

Leave a Reply

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.