It's strange I did not recieve email announcement yet. I thought generally everyone recieve it at same time.

For beginner contests there are no english editorials.

I wrote an unofficial English editorial.

place red balls then choose i gaps out of n-k+1 = (n-k+1 choose i). then place k blues in these i gaps = number of positive integral solutions of a1+..ai=k = (k-1 choose i-1) multiply both coefficients.

Let us say the number of red balls is R = N — K and blue balls is B = K.

Consider the case where it takes i moves. So the number of ways to split B balls into i non-empty groups is choose(B — 1, i — 1) by stars and bars method.

Now between any 2 groups there must be at least one red ball since if there was no red ball, they would be one large group instead. So the groups must occupy spaces between the red balls. The number of spaces are R + 1 and groups are i. So again, by stars and bars method number of ways is choose(R + 1, i).

Multiplying we get ans as choose(B — 1, i — 1) * choose(R + 1, i).

You can precompute choose values for R + 1 and B — 1 in O(N) time and answer for every i in O(1) time. So complexity is O(N + K)

Use just need to use PnC to solve the stuff look if we have K blue balls . then first place N-K red balls. then we have N-K+1 places to fill blue balls. Now just think if u use i of the places to fill K balls..

Hope This helps u. :)

Let`s count dp[i][j], what means number of ways present number i with j addends (order is important).

Then dp[i][j] = dp[i-1][j]+dp[i-1][j-1].

And the answer for i is dp[B][i]*(dp[R][i-1] + dp[R][i+1] + dp[R][i]*2), where B — blue balls, R — red balls.

m = n-k ans[i] = C(m+1, i) * C(k-1, i-1)

You have to chose i places out of a total of (n-k)+1. (n-k) red balls so (n-k+1) places and you have to take any i of them to place your blue balls.

You can arrange i blue balls by C(k-1, i-1) and the red balls with 3 options : 2 * C(n-k-1, i-1), C(n-k-1, i) and C(n-k-1, i-2). So the answer would become : (number of ways of arranging blue balls) * (sum of 3 options of arranging red balls). My code

You need to distribute K blue balls among i piles such that no pile is empty which is f1=C(k-1,i-1), now there are i-1 gaps between these piles and you need to fill at least 1 red ball in each of the i-1 gaps, after filling you will be left with z=n-k-(i-1) red balls and note that there are two more gaps one on extreme left and the other on extreme right of blue ball piles so you need to distribute z balls between i+1 piles such that each get >=0 balls which will be f2=C(n-k+1,i).So your answer will be f1*f2 . You can calculate nCr using factorial and inverse array in O(1) using O(n) preprocessing. Here is the link to my submission.

I hope this helps :)

You're good. You should write a blog :D

thanks a lot this should be a blog

The basic idea is DP with square-root decomposition. For each number of terms up to K, we store the number of valid sequences satisfying these two conditions (in two separate tables) for each X up to ceil(sqrt(N)):

• The sequence ends in X.
• The sequence ends in a term Y such that X*Y <= N but (X+1)*Y > N.

We then just have to deal with transitions. I outline this step in my full solution, which I linked above.

Hint: naive dp — f[i][j] = sum(k=1..n/j,f[i+1][k]). This can be optimized cause many f[i][j] have same values precisely those which have n/j = n/j'. Just maintain groups(they never change) and calculate above dp- Time = O(k*num_groups) = O(k*sqrt(n));

Geothermal explains the solution well, but I think I have easier code for the problem:

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;

// Finds smallest s s.t. n/s < t
ll bins(ll n, ll t) {
	ll low = 1;
	ll high = n+1;
	while(low != high) {
		ll s = (low + high) / 2;
		if (n/s < t) high = s;
		else low = s + 1;
	}
	return low;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	ll n, k;
	cin >> n >> k;
	
	vector<ll> cou, val;
	ll s = 1;
	for (; s <= n;) {
		ll v = n/s;
		ll nxt_s = bins(n, v);
		cou.push_back(nxt_s - s);
		val.push_back(v);
		s = nxt_s;
	}
	int m = cou.size();

	vector<ll> cur = cou;
	vector<ll> nxt(m);
	for (int i = 1; i < k; ++i) {
		for (int j = 0; j < m; ++j) {
			int t = m-1-j;
			nxt[t] = cur[j] % MOD;
		}
		for (int j = m-1; j >= 0; --j) {
			nxt[j] = (nxt[j] + (j+1 < m ? nxt[j+1] : 0)) % MOD;
			cur[j] = (nxt[j] * cou[j]) % MOD;
		}
	}

	ll res = 0;
	for (auto v : cur) res = (res + v) % MOD;
	cout << res << '\n';
}

Notably I only have one table, and from position j in the table, you can transition to any position in range $$$[0, m-j)$$$, so the transitions can be done with just two for-loops. To calculate the sizes of every part (where if $$$x$$$ and $$$y$$$ are in the same part if $$$\left\lfloor\frac{n}{x}\right\rfloor = \left\lfloor\frac{n}{y}\right\rfloor$$$), I just maintain the smallest s such that $$$\left\lfloor\frac{n}{s}\right\rfloor = v$$$, and then binary search the next $$$s^{'}$$$ s.t. $$$\left\lfloor\frac{n}{s^{'}}\right\rfloor \lt v$$$. Then there are $$$s^{'} - s$$$ values in the part.

Maybe I have a bit simpler solution (well, rather, interpretation) than others, which can be implemented very intuitively.

Let's call a sequence good when

• each element is positive integer $$$\leq N$$$, and
• product of any two adjacent elements is $$$\leq N$$$.

For each positive integers $$$m$$$ and $$$i$$$, let

• $$$a^{m}_{i}$$$ be the number of good sequence of length $$$m$$$ whose last element is $$$\leq i$$$, and
• $$$b^{m}_{i}$$$ be the number of good sequence of length $$$m$$$ whose last element is $$$\leq N / i$$$.

For $$$m=1$$$, $$$a^1_i = \mathrm{min}(i,N)$$$ and $$$b^1_i = n/i$$$. For $$$m \geq 2$$$, it holds that

• $$$a^m_i = a^m_{i-1} + b^{m-1}_i$$$, and
• $$$b^m_i = b^m_{i+1} + a^{m-1}_i \cdot (\frac ni - \frac n{i+1})$$$,

Also, it holds that $$$a^m_i = b^m_{N/i}$$$. Therefore, for each $$$m$$$, you can calculate $$$a^m_1, a^m_2, \cdots, a^m_{N/x} = b^m_x, b^m_{x-1}, \cdots, b^m_1$$$. Of course it's optimal when $$$x \approx \sqrt N$$$. The answer is $$$b^K_1$$$.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000000007;
const ll M = 128;
const ll X = 32768; // >= sqrt(N)

ll a[M][X], b[M][X];
int main(){
	int N, K; scanf("%d%d", &N, &K);
	for(int i=1; i<X; i++){
		a[1][i] = min(i, N);
		b[1][i] = N/i;
	}
	for(int m=2; m<=K; m++){
		a[m][0]=0;
		for(int i=1; i<X; i++){
			a[m][i] = ( a[m][i-1] + b[m-1][i] ) % MOD;
		}
		b[m][X-1]= a[m][N/(X-1)];
		for(int i=X-2; i>=1; i--){
			b[m][i] = ( b[m][i+1] + a[m-1][i] * (N/i - N/(i+1)) ) % MOD;
		}
	}
	printf("%lld\n", b[K][1]);
}

The idea is that we construct the graph in 3 parts (let's call them first, second and third), such that if there is an edge between u and v, then in our graph, there is an edge between u.first -> v.second, u.second -> v.third and u.third -> v.first. Now, if you run BFS on this Graph starting from vertex S.first and if you keep the destination as T.first, then you will find a path whose length is always divisible by 3, and hence you will get the answer by dividing the path length by 3. And if you cannot reach T.first, then print -1.

My AC submission: https://atcoder.jp/contests/abc132/submissions/6179681

See the link I posted above. A copy of my write-up of E is below:

Create a graph of 3*N vertices, where the first N vertices represent reaching a vertex before starting a ken-ken-pa, the second set of N vertices represent reaching a vertex after one of the three actions in a ken-ken-pa, and the third set of N vertices represent reaching a vertex after two actions in a ken-ken-pa. An edge from A to B in our original graph is then equivalent to three edges: one from A to B+N, one from A+N to B+2N, and one from A+2N to B.

The advantage of this approach is that once we read in the data, the solution itself is very easy to implement, as we now simply want to find one-third the distance from S to T (where the distance between two nodes is the number of edges we must traverse to reach one from the other). We can compute this using a standard BFS algorithm, which can also tell us whether T can be reached from S at all.

Are you sure your submittions were submitted before the race ended?