### chokudai's blog

By chokudai, history, 3 years ago, 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! Comments (26)
| Write comment?
 »
 » How to solve F?
•  » » 3 years ago, # ^ | ← Rev. 2 →   Use $\sum_{i=0}^{M}{{N+i}\choose{i}}={{N+M+1}\choose{M}}$.
•  » » » what is the name of this formula ?
 » For task-D. I spent 30 mins on reading what is meant by expected value and linearity of expectation.
•  » » That was unnice problem. Still don't get it why this is wrong. Somebody explain?
•  » » » You need to take care of the precision.
•  » » » » It is all integer, and at the end I do division by 2. What can be wrong with precision there?
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   Have a look https://atcoder.jp/contests/abc154/submissions/10011578 The final answer need not to be an integer.
•  » » » 3 years ago, # ^ | ← Rev. 3 →   cout doesn't work well with big float numbers if you don't use setprecision.For example, if d is 87654321. cout << d / 2 << endl; // Prints 4.38272e+07 cout << setprecision(10) << d / 2 << endl; // Prints 43827160.5 As you can see, outputs are very different.
•  » » » » Thanks, got it.
 » Hack in problem E :  10000 3
•  » » whats correct output?
•  » » » 2916
 » Submission 10000000 goes to user lmdexpr! https://atcoder.jp/contests/abc154/submissions/10000000
 » 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.
•  » » 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 codepublic void solve(int testNumber, InputReader in, PrintWriter out) { int r1 = in.nextInt() - 1, c1 = in.nextInt() - 1; int r2 = in.nextInt(), c2 = in.nextInt(); long answer = mod.subtract(mod.add(f(r2, c2), f(r1, c1)), mod.add(f(r2, c1), f(r1, c2))); out.println(answer); } private long f(int x, int y) { return mod.subtract(mod.ncr(x + y + 2, y + 1), 1); } 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.
•  » » 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.
•  » » » Thank you very much mnbvmar for actually taking the time to edit my code and explain.
 » Peculiar similarity between E and 1036C - Шикарные числа, except in E you need to directly manipulate on strings.
 » How to solve E?
•  » » 3 years ago, # ^ | ← Rev. 2 →   Standard Digit DP problemBlog
•  » » » Thanks!
 » 7 months ago, # | ← Rev. 2 →   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); 
•  » » 7 months ago, # ^ | ← Rev. 2 →   orzorzorz, and your comment can be deleted by edit it :)
•  » » » I am sorry!I've changed it.