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

# | User | Rating |
---|---|---|

1 | Benq | 3783 |

2 | jiangly | 3666 |

3 | tourist | 3611 |

4 | Um_nik | 3536 |

5 | inaFSTream | 3477 |

6 | fantasy | 3468 |

7 | maroonrk | 3464 |

8 | QAQAutoMaton | 3428 |

9 | ecnerwala | 3427 |

10 | Ormlis | 3396 |

# | User | Contrib. |
---|---|---|

1 | Um_nik | 184 |

2 | adamant | 178 |

3 | awoo | 177 |

4 | nor | 169 |

5 | maroonrk | 165 |

6 | -is-this-fft- | 164 |

7 | antontrygubO_o | 152 |

8 | ko_osaga | 151 |

9 | dario2994 | 150 |

10 | SecondThread | 149 |

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

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/04/2023 10:04:15 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

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.

Seems like you are new to competitive programming. Its not possible to run a loop till 10^11.

This technique is called contant array and it's a very important technique. You 're too fucking stupid.

I have pity on your shit life. Keep blabbering bad words as they define who you are . Keep up.

OMG. You 're a bad word.

can you explain contant array technique? I do not understand sorry

.

good luck storing a 10 ^ 11 array.

Divide&Conquer + NTT + FFT

Please explain it more clearly.

The problem doesn't have a solution!!!!!!!!!!! The solution is absolutely incorrect! Shut up tzc_wk. Stop lying! You're a 822E - Liar!

It has. 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.

Why do you repeat it again?

And there's a grammar mistake. It should be "It does" instead of "It has".

You get the meaning then its ok.

You're a SolarFlea!

You're a PolarFlea!

You'd better shut up

You'd better shut up too.

Shut up SolarFlea. You are a PolarFlea!

I think you don't know how to do it.

Are you crazy?!!

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

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.

Or segment tree.

Segment tree? U r making me laugh.

Why not? We use Segment Tree to calculate [1..sqrt(n)]'s Point Value in O(sqrt(n)log^2).

Or link-cut-tree.

link-cut-tree? U r making me laugh.

/bx cnnfls_csy

why downvote? he is actually another account of cnnfls_csy. you can see that in submission https://codeforces.com/contest/1720/submission/168832594, despite the template, the remaining part is very similar to cnnfls_csy's code.

Actually not. In fact SolarFlea is another account of Alex_Wei. You can see this submission using Alex_Wei's coding style.

Actually not. He is the sum of all OIers in NFLS who competed in NOI2022. https://codeforces.com/contest/1734/submission/175218475

How do you get the values at those points quickly? P(1) and P(1+sqrtp) and so on

There is a tool of getting polynomial values at many points. You can just search it on the internet.

https://www.cnblogs.com/zzqsblog/p/7923192.html TLE has a blog about this.

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.

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

$$$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

in mind