The problem can be found here

Thoughts

This was a pretty standard combinatorics problem, but still pretty interesting. Seems complicated at first but after trying to figure out a formula for the answer, it got quite a bit easier.

My Thought Process

Okay, this seems like a combinatorics problem (we are asked to find large integers MOD something and that integer isn’t the # of _____).

We need to figure out how Harshith will play optimally so lets keep that in mind as we look at the sample case with $a = 2$, $b = 2$, $k = 2$ to get some ideas.

The answer to this case is $(3, 7)$ but how does the matrix actually look like? We should build the array column by column and try to see why $m$ cannot be greater than $7$.

Matrix of Sample Test Case

Building from left to right and trying to do an optimal strategy for Harshith, we notice that we try to make it so we don’t make two equal columns. For example, in this case, we can cut the middle row and only keep the two $(2,1,2)$ columns.

This leads us to think of the Pigeonhole Principal. With $n = 3$ the columns always have atleast $2$ of one number. There are ${3\choose{2}} * 2$ different columns with two of the same numbers. We are skipping the case with all equal numbers because we are trying to do this optimally.

That’s pretty interesting but we should try to find the minimum $n$ that work to find the lexiographically smallest tuple for more general inputs. Thinking about the Pigeonhole Principal again, we should always have $a$ of one number $x$ in each column so we can delete some rows and make the submatrix with $a$ rows, all equal to $x$.

We can achieve this by setting $n = ak+1$ by Pigeonhole Principal. Now, what about columns? In the worst case, or when Harshith play optimally, he would run through all columns with $a$ same numbers.

How many columns are there then? Well, there are $n\choose a$ ways to put the $n$ of one number, $k$ ways to choose that number for ${n\choose a} * k$ ways. The other numbers in each column does not matter. Again, by PHP, are ${n\choose a} * k * (b-1) + 1$ is the smallest numbers of columns that guaranteed us $b$ columns with $a$ elements in the same row.

As a result, we should print ($ak+1$, ${{ak+1}\choose a} * k + 1$).

Implementation

#include <bits/stdc++.h>

using ll = long long;
#define pb push_back

using namespace std;

const int MOD = 1e9+7;
const int MAXN = 2e5+1;
const int INF = 2e9;

#define int long long

void ext(ll a, ll b, ll &x, ll &y) {
	if (b == 0) {
		x = 1, y = 0;
	} else {
		ext(b, a % b, x, y);
		ll tem = x;
		x = y;
		y = tem - (a / b) * y;
	}
}

ll inv(ll a, ll m) {
	ll x = 0, y = 0;
	ext(a, m, x, y);
	return (x + m) % m;
}

void solve() { 
    int a, b, k; cin >> a >> b >> k;

    if(k == 1){cout << a << ' ' << b << endl; return;}

    int n = (((a-1) * k) + 1) % MOD;
    int m = (k * (b-1)) % MOD;

    for(int i = 0; i < a; ++i){
        m = (m * ((n-i+MOD) % MOD)) % MOD;
        m = (m * inv((a-i+MOD) % MOD, MOD)) % MOD;
    }

    cout << n << ' ' << (m + 1) % MOD << endl;
}

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

    int t;
    cin >> t;
    while(t--){
        solve();
    }

    return 0;
}