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

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

1 | tourist | 3775 |

2 | Benq | 3724 |

3 | orzdevinwang | 3697 |

4 | Radewoosh | 3651 |

5 | jiangly | 3632 |

6 | cnnfls_csy | 3620 |

7 | -0.5 | 3545 |

8 | inaFSTream | 3478 |

9 | fantasy | 3468 |

10 | Rebelz | 3415 |

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

1 | adamant | 178 |

2 | awoo | 167 |

3 | BledDest | 165 |

4 | Um_nik | 163 |

5 | maroonrk | 162 |

6 | SecondThread | 160 |

7 | nor | 158 |

8 | -is-this-fft- | 154 |

9 | kostka | 146 |

10 | TheScrasse | 144 |

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: Oct/02/2023 04:19:41 (j1).

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