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

AtCoder Beginner Contest 154 Announcement
Автор chokudai, история, 5 лет назад, По-английски

We will hold AtCoder Beginner Contest 154.

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

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

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

Screencast + Brief Explanations

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

How to solve F?

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

For task-D. I spent 30 mins on reading what is meant by expected value and linearity of expectation.

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

Hack in problem E : 10000 3

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

Submission 10000000 goes to user lmdexpr! https://atcoder.jp/contests/abc154/submissions/10000000

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

What is the intended solution for F?

My solution https://atcoder.jp/contests/abc154/submissions/10004590 passed however, took 1977 ms, at which point it's just luck that it passed within the 2s time limit. So clearly either I implemented this horribly bad, or it was not the intended solution.

I simplified $$$\sum_{i=r1}^{r2}\sum_{j=c1}^{c2}{{i+j}\choose{j}}$$$ to $$$\sum_{j=c1}^{c2}{{r2+j+1}\choose{j+1}}-{{r1+j}\choose{j+1}}$$$ and then simply evaluted.

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

    You can do the same simplification again to eliminate the remaining summation, so you end up with a completely closed form that looks like $$$A-B-C+D$$$ (where $$$A$$$, $$$B$$$, $$$C$$$, $$$D$$$ are each a single binomial coefficient).

    my code

    By the way, instead of worrying about the lower bounds, since they make it a little messier, I solved the problem for the special case of $$$(r_1, c_1) = (0, 0)$$$ and then used the fact that you can use principle of inclusion-exclusion to express an arbitrary rectangle as the sum/difference of four rectangles starting at $$$(0, 0)$$$. (Very similar to how people use [a, b) = [0, b) - [0, a) all the time when there's only one dimension.)

    Doing it this way makes the final answer a lot easier to come to and code up bug-free, I think.

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

    You can precompute the inverses of factorials in $$$O(N)$$$ as well: https://atcoder.jp/contests/abc154/submissions/10024715. Then you can evaluate a single binomial in constant time instead of $$$O(\log \mathrm{MOD})$$$, and here the code runs roughly 10x quicker.

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

Peculiar similarity between E and 1036C - Classy Numbers, except in E you need to directly manipulate on strings.

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

How to solve E?

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

You can use NTT to solve it, but waste some time. Because I don't know the NTT of 1e9+7, I use the board of any mod NTT. C(x+y,x) = (x+y)! / x! / y! , Then it can be converted into an exponential generating function, multiplied, and finally multiply each bit by i!. Add it up.

mod = 1e9+7
n = m = 1e6 + 10;
int lx = read(), ly = read(), rx = read(), ry = read();
for (int i = lx;i <= rx;i++) A[i] = Int(invfac[i]);
for (int i = ly;i <= ry;i++) B[i] = Int(invfac[i]);
Poly::init(n + m);
Poly::NTT(A), Poly::NTT(B);
for (int i = 0; i < Poly::lim; ++i) A[i] = A[i] * B[i];
Poly::NTT(A, 0);
ll res = 0;
for (int i = 0; i < n + m - 1; ++i) res = (res + fac[i] * A[i].get() % mod) % mod;
printf("%lld\n", res);
→ Ответить