I was trying to solve problem F from CERC 15. The problem was basically reduced to finding the sum . How can I find this sum in better than quadratic time without FFT?

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

1 | tourist | 3822 |

2 | Benq | 3745 |

3 | ksun48 | 3560 |

4 | Radewoosh | 3538 |

5 | peehs_moorhsum | 3532 |

6 | Um_nik | 3489 |

7 | maroonrk | 3424 |

8 | Petr | 3380 |

9 | sunset | 3338 |

10 | ecnerwala | 3336 |

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

1 | 1-gon | 206 |

2 | Errichto | 181 |

2 | awoo | 181 |

4 | Um_nik | 180 |

5 | -is-this-fft- | 175 |

6 | maroonrk | 174 |

7 | Radewoosh | 172 |

7 | tourist | 172 |

9 | SecondThread | 170 |

10 | rng_58 | 166 |

I was trying to solve problem F from CERC 15. The problem was basically reduced to finding the sum . How can I find this sum in better than quadratic time without FFT?

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/31/2021 03:33:48 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

I didn't realize the FFT solution (which is pretty straightforward) while doing virtual so here's my (a bit messy) approach:

Think of the sum as a polynomial of

a. More precisely, let then we are looking forNow let's calculate

F_{y}(a) according toF_{y - 1}(a):Hence,

Since

F_{0}(a) is easy to calculate, we can achieveO(N*log(N)) time complexity, with logarithm factor being the cost for calculating modular inversions.I have not read carefully your solution, but seeing just the last line I am pretty sure you got exactly the same solution as I got on contest. I first wrote FFT solution but at that time our FFT from library was not precise enough, so I needed to come up with completely different solution and did what you did. However there is a division by

a- 1 in your formula. So you need to also consider casea= 1 :). But I have not done this on contest. And got AC either way :DD. However it is easy to fix, so that is not a big deal.However there were other controversies about this problem. It has a really easy solution if (which can't be easily seen from presented here reduced version but can be seen from original statement). You can add to all values of

Fand you basically get rid of +c term and that makes problem very easy. But if you can't do this, you are basically screwed, there is no easy fix for this. But in tests there were no cases whereP|a+b- 1, so many people wrote this solution and got it accepted.Authors of that problem thought only about FFT solution that has no special cases and they missed other solutions (it turned out that there are at least two different approaches that were already described here), so they did not prepare tests against them what led to many participants getting not deserved AC.