I really don't see which part of D's statement is ambiguous. Also, you should ask for the clarification on the atcoder site if you're unsure about something, not on CF.

Guys like you are like a mad rabid dog who needs to be put to sleep legally

How to solve D?

Why not? It's ABC meant to be educational.

I think it is very adequate for a Beginner Contest. You need to understand the algorithm and understand where to insert the new code inside a known algorithm. My brother got to know Floyd-Warshall for the first time and even I learned how FW works more in detail. I am really positive that I won't mistakenly put $$$i$$$,$$$j$$$,$$$k$$$ in the wrong order from now on, knowing which invariant $$$k$$$ creates. :D

wait, was'nt the extra summation over k a modification? if I didn't understand Floyd-warshall, I don't think I could have solved it.

D was not graphs, it was just dp.

So what do you expect in a "beginner's" contest? Problems like F?

Actually that algorithm is just a greedy observation.

When I solved that problem I didn't even knew that such a algorithm exists.

Coincidentally I wrote the exact algorithm without even knowing about it.

.

You would only need one inverse if you compute factorials properly.

Why is it polynomial of degree (K+M)? Since f(n, m) defined as sum of some number of zeros and (n^k) for n from 1 to N, then: f(N, M) = b1 * 1^k + b2 * 2^k + b3 * 3^k + ... bn * N^k — (with b_i — some unknown integers) and that makes if polynomial (of variable n) of degree (K+1), because we can turn this expresion into f(N, M) = b1*(N-(N-1))^k + b2*(N-(N-2))^k+ ... + bn*N^k = a0 + a1*n^1+a2*n^2+..+ak*n^k. No?

I used 5 states DP to solve it , I am presuming that you know basic Digit DP.
map<lli,lli> dp [leading_zero][tight][product_is_zero][no_of_digit]; except no. Of digit all other states will be 0 or 1 . I am using Map as I don't know exactly how many values of K will be there ( Hoping that someone will tell me the upperbound on no. of K for each state ). Tight represents that whether the current no. through which I came here is till now equal to N or not.Then just some digit DP stuffs.
code

I did this DP from least significant digit to most significant digit. Submission link. As far as I can tell, there's no need to have the optimization they mention in the editorial where products greater than K are indistinguishable, so I'll ignore that.

The DP state I use only needs to store two values — the maximum possible value that the number can take on given the digits we already have, and the product attained so far from the digits we have already used. The starting state is therefore $$$(N, 1)$$$.

The base case for this DP is if the maximum possible value that the number can take on is zero — in this case, we can't add any more digits, so we simply check if our attained product is less than or equal to $$$K$$$.

If we are not in the base case, then we can append digits to the left. The transitions are therefore adding the digits from zero to nine (or $$$N$$$, if $$$N < 9$$$) to the left of the number we have built so far. Adding the nonzero digits is straightforward, the product just scales by the digit we added, and the maximum value goes from $$$v$$$ to $$$\left \lfloor \frac{v-d}{10} \right \rfloor$$$ if we just appended a digit $$$d$$$. The interesting transition is when we add a zero.

There are two cases — either all the digits will be zero from here to the most significant digit, or there will be a digit to the left that is nonzero. In the former case, the number we have built so far is evaluated to see if it is valid. In the latter case, we mark the current product as being equal to "zero", except that it is not valid if we run into the base case. This is necessary to avoid overcounting. If we multiply this "zero" by any non-zero digit, then the product becomes exactly zero. In my code, the sentinel ZERO is used as a placeholder for this fake zero.

Note that in the above, we cleanly handle numbers where the length is less than or equal to the length of $$$N$$$. This avoids a typical issue in digit DP where we have to keep track of when the number is "initialized", if the DP is done from most significant digit to least significant digit.

This DP also counts zero, so you'll need to decrease the answer by one at the end.

4D dp is sufficient for solving the problem (use map for storing dp) The dp will look something like this :- ~~~~~

map<pair<pair<int,int>,pair<bool,bool> >,int>dp; // {{pos,prod},{tight,st}}

pos : current pos in the number 
prod : current product of digits so far 
tight : tells whether current no is smaller than N or not 
st : tells does the number has leading zeros or not.

~~~~~

So if u know basics of digit dp , this problem can be solved :) For reference : My Accepted Code(c++)

I think the easiest way is to iterate over the most significant digit that differs, and then use the naive $$$dp[i][j] :=$$$ number of $$$i$$$-digit numbers with product $$$\leq j$$$. Since every $$$j$$$ will be of the form $$$\left \lfloor{K/x}\right \rfloor$$$ for some $$$x$$$, $$$j$$$ can take on at most $$$2\sqrt{K}$$$ distinct values. I think the editorial proves a tighter bound, but $$$O(18\cdot 2 \cdot \sqrt{K})$$$ is already good enough. (There is a small edge case with trailing 0s, but you can use the same DP to handle that.)

Unluckily,somebody have seen this thick.....

Yes, but how to calculate that for a huge N

Yeah, I caught this series pretty quick, but I tried for like 90 mins on how to get this sum and failed. Bad decision skipping E and going for F.

UPD: No, my calculation is just plain wrong.

Oh, I got

You count the paths from $$$f(n,m)$$$ to $$$f(i,0)$$$ and multiply by $$$i^K$$$ for all $$$i$$$. Is that the same?

Do you mean why the number of distinct products fits in constraints?

Declare your 'dp' array globally. Size of the array is too large (10^8) to be declared locally

Obviously, the numbers of possible x, z, and w are $$$d :=log N$$$ (the number of digits in $$$N$$$), $$$2$$$, and $$$2$$$, respectively. The non-trivial part is y. How many possible "products of digits" are there? Actually, every product of digits has only factors 2, 3, 5, and 7. Plus, the upper bound of the product is $$$9^d$$$, or more loosely $$$10^d \simeq N$$$. Now every product except for $$$0$$$ can be expressed in a form of $$$2^a 3^b 5^c 7^d$$$ for some non-negative integers $$$(a, b, c, d)$$$, and the product is $$$\leq N$$$. Applying logarithmic function we obtain $$$a \log 2 + b \log 3 + c \log 5 + d\log7 \leq \log N$$$. How many tuples of integers are there that satisfies this inequality? It is equal to the number of grid points in a certain "pyramid" on a 4-dimensional space (which is technically called a simplex). Since the number of grid points is approximately equal to the volume, we can estimate the number as $$$\dfrac{\log N}{\log 2} \cdot \dfrac{\log N}{\log 3} \cdot \dfrac{\log N}{\log 5} \cdot \dfrac{\log N}{\log 7} \cdot \dfrac{1}{4!} \simeq 51555$$$.

Alternatively, with the observation of prime factors being $$$2, 3, 5, 7$$$, one can just write a simple code to verify the number is small enough:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
  ll cnt = 0;
  ll n = 1'000'000'000'000'000'000LL;
  for(ll a = 1; a <= n; a *= 2) {
    ll na = n / a;
    for(ll b = 1; b <= na; b *= 3){
      ll nb = na / b;
      for(ll c = 1; c <= nb; c *= 5){
        ll nc = nb / c;
        for(ll d = 1; d <= nc; d *= 7){
          cnt++;
        }
      }
    }
  }
  cout << cnt << endl;
}