FLRCNT - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: beevo
Tester & Editorialist: iceknight1093

DIFFICULTY:

2890

PREREQUISITES:

Hockey-stick identity

PROBLEM:

Given N, find for each i from 1 to N:

\sum_{j=1}^N \binom{j-1}{j - \left \lfloor \frac{j-1}{i} \right\rfloor -1}

EXPLANATION:

There are a couple of different ways to approach this task; one more visual in nature and the other one more algebraic.
They both end up at the same solution, however.

Visual approach

Let’s look at what’s going on in the context of Pascal’s triangle.
For a fixed i:

  • Let (x, y) be our position on the triangle. Initially, (x, y) = (0, 0).
  • Then, for each j from 1 to N:
    • If j is divisible by i, we move to (x+1, y).
    • Otherwise, we move to (x+1, y+1).

The answer for i is the sum of values at all points we visited.

Looking at the triangle, our path can be broken into several smaller ‘straight’ paths along diagonals.
In particular, each multiple of i is when we move from one diagonal to another.
So, there are \left \lceil \frac{N}{i} \right\rceil such movements in total.
Summing this across all i, we have \mathcal{O}(N\log N) movements in total; which also means \mathcal{O}(N\log N) diagonal segments in total.

Finally, the sum of each diagonal segment can be found in \mathcal{O}(1) time using the hockey-stick identity, and so we’re done!

Algebraic approach

Note that \displaystyle\binom{j-1}{j - \left \lfloor \frac{j-1}{i} \right\rfloor -1} = \binom{j-1}{\left \lfloor \frac{j-1}{i} \right\rfloor}, because \binom{N}{K} = \binom{N}{N-K}.

Let’s fix i. Then, notice that if we also fix x = \left \lfloor \frac{j-1}{i} \right\rfloor, we obtain a certain range of j that attain this value of x; in particular, x\cdot i \leq j-1 \lt (x+1)\cdot i.

Let this range be [L, R]. Then, we want to compute \sum_{k=L}^R \binom{k}{x}.
This can be done using the hockey-stick identity, and equals \binom{R+1}{x+1} - \binom{L}{x+1}.

Now, for a fixed i, there are only \left \lceil \frac{N}{i} \right\rceil ranges of j we care about; we don’t care about any x such that i\cdot x \gt N.

Since the sum of \frac{N}{i} is \mathcal{O}(N\log N), we compute \mathcal{O}(N\log N) binomial coefficients in total; each of which can be done in \mathcal{O}(1) time.
This is enough to solve the problem.

TIME COMPLEXITY

\mathcal{O}(N\log N) per testcase.

CODE:

Author's code (C++) 
#include <bits/stdc++.h>

#define el '\n'

typedef long long ll;
typedef long double ld;

#define Beevo ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 1e6 + 5, M = 1e9 + 7;

int fact[N], inv[N];

int add(int a, int b) {
    b = (b + M) % M;

    return (a + b) % M;
}

int mul(int a, int b) {
    return 1LL * a * b % M;
}

int modPow(int b, int p) {
    if (p == 0)
        return 1;

    int x = modPow(b, p / 2);

    return p % 2 == 0 ? mul(x, x) : mul(b, mul(x, x));
}

int modInvFer(int n) {
    return modPow(n, M - 2);
}

void pre() {
    fact[0] = 1;

    for (int i = 1; i < N; i++)
        fact[i] = mul(fact[i - 1], i);

    inv[N - 1] = modInvFer(fact[N - 1]);

    for (int i = N - 2; i >= 0; i--)
        inv[i] = mul(inv[i + 1], i + 1);
}

int ncr(int n, int r) {
    return mul(fact[n], mul(inv[r], inv[n - r]));
}

int hockeyStick(int n, int r) {
    return ncr(n + 1, r);
}

int sumDiagonal(int n1, int r1, int n2, int r2) {
    return add(hockeyStick(n2, r2), -hockeyStick(n1 - 1, r1 - 1));
}

void testCase() {
    int n;
    cin >> n;

    int sum, x1, y1, x2, y2;
    for (int i = 1; i <= n; i++) {
        sum = 0;

        for (int j = 0; j < n; j += i) {
            x1 = j, x2 = min(j + i - 1, n - 1);
            y1 = j - j / i, y2 = y1 + x2 - x1;
            
            sum = add(sum, sumDiagonal(x1, y1, x2, y2));
        }
 
        cout << sum << ' ';
    }

    cout << el;
}

signed main() {
    Beevo

    pre();

    int t = 1;
    cin >> t;

    while (t--)
        testCase();
}
Editorialist's code (Python) 
lim = 10**6 + 5
mod = 10**9 + 7

fac = [1] * lim
inv = [1] * lim
for i in range(2, lim): fac[i] = fac[i-1] * i % mod
inv[-1] = pow(fac[-1], mod-2, mod)
for i in reversed(range(2, lim-1)): inv[i] = inv[i+1] * (i+1) % mod

def C(n, r):
    if n < r or r < 0: return 0
    return ((fac[n] * inv[r]) % mod * inv[n-r]) % mod

for _ in range(int(input())):
    n = int(input())
    ans = [0]*(n+1)
    for i in range(1, n+1):
        for x in range(n+1):
            L, R = x*i, min(n, (x+1)*i)-1
            if L > n: break
            ans[i] += C(R+1, x+1) - C(L, x+1)
            ans[i] %= mod
    print(*ans[1:])