Блог пользователя I_love_Saundarya

Автор I_love_Saundarya, история, 5 лет назад, По-английски

Here is the link to the problem:- https://www.spoj.com/problems/FACTMODP/

  • Проголосовать: нравится
  • -6
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Try what’s described here. https://codeforces.net/blog/entry/63491

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится -32 Проголосовать: не нравится

I don't know the actually way to implement this problem but you can loop N from 1 to 10^11 and calculate n!%p through this formula: (a * b) % c = ((a % c) * (b % c)) % c; and prefix sum. Then store them into an array. If you implement the problem with these operations, you can get the answer in about 3 hours.

»
5 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Divide&Conquer + NTT + FFT

»
5 лет назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

The problem is too hard that it is of no use to let a cyan to solve the problem! HAHAHAHA

»
5 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

I have a solution First,build a polynomial of n*(n+1)*(n+2)*(n+3).....*(n+sqrt(p)) Then use we can get the value of the polynomial at 1,sqrt(p)+1,2sqrt(p)+1.... Then we can calculate the rest of part(not exceed sqrt(p)) using bruteforce.

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

We can construct a polynomial :

$$$F(x)=\prod_{i=1}^{\lfloor\sqrt n\rfloor}(x+i)$$$

And then we have :

$$$n!=\bigg(\prod_{i=n-{\lfloor\sqrt n\rfloor}^2}^{n}i\bigg)\cdot\prod_{i=0}^{\lfloor\sqrt n\rfloor}F(i\cdot \lfloor\sqrt n\rfloor)$$$

For $$$\prod_{i=n-{\lfloor\sqrt n\rfloor}^2}^{n}i$$$ , we can calculate it use brute force.

For $$$\prod_{i=0}^{\lfloor\sqrt n\rfloor}F(i\cdot \lfloor\sqrt n\rfloor)$$$ , we can use fast polynomial multipoint evaluation to calculate. (https://cs.stackexchange.com/questions/60239/multi-point-evaluations-of-a-polynomial-mod-p)

Sorry for my poor English.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

if p is prime then the problem is pretty much implementation of wilson's theorem.

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

    $$$n=\lfloor \frac{p}{2} \rfloor$$$ is still big enough to make any naive solution exceed the TL.

    UPD: you're also 3 years late

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

in mind