CF2120D Matrix game
字典序要求 \(n\) 最小，所以考虑最小化 \(n\)。由于获胜需要的子矩阵中每一行有 \(a\) 个相同元素，根据鸽笼原理，有 \(k\) 种取值的元素中出现 \(a\) 个相同的元素至少需要 \(k(a-1)+1\)。
这是 \(n\) 的下界，如果此时存在 \(m\) 满足题设条件，证明 \(n\) 可以取到 \(k(a-1)+1\)，最小性也就证明了。于是我们考虑在这种情况下最小化 \(m\)。
考虑最小化 \(m\)。还是考虑鸽笼，如果对手每取 \(x+1\) 个就会出现一对可以同时的被包含在获胜需要的子矩阵中，同上计算答案为 \(x(b-1)+1\)。
由于对手会采取最优行动，所以考虑求 \(x\) 的最大值。首先考虑 \(x\) 的上界，我们只考虑获胜需要的子矩阵中的元素，这种元素只有 \(n\choose a\) 种选法。但原矩阵中每个元素有 \(k\) 种选法，所以 \(x\) 的上界为 \(k{n\choose a}\)。
接下来考虑证明 \(x\) 可以取到上界。由于 \(n=k(a-1)+1\)，去掉 \(a\) 个获胜需要的子矩阵中的元素还剩 \((k-1)(a-1)\) 个位置，其他每种取值 \(c\) 各取 \(a-1\) 个，由于其他取值 \(c\) 与取值 \(c\) 作为获胜需要的子矩阵中的元素时的数量不同，所以一定不会产生冲突。
于是我们证明了 \(x\) 的上界，通过鸽笼得出了 \(m\) 的下界，进而证明了 \(n\) 的下界。
实现的时候组合数暴力计算即可。
#include <bits/stdc++.h>
using namespace std;
long long t,a,b,k,jc[200000],inv[200000];
const long long mod=1e9+7;
long long power(long long a,long long p)
{long long x=a,ans=1;while(p){if(p&1)ans=ans*x%mod;p>>=1;x=x*x%mod;}return ans;
}int main()
{jc[0]=1;for(int i=1;i<=100000;i++)jc[i]=jc[i-1]*i%mod;inv[100000]=power(jc[100000],mod-2);for(int i=99999;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;scanf("%lld",&t);while(t--){scanf("%lld%lld%lld",&a,&b,&k);long long n=k*(a-1)+1,m=inv[a]*k%mod*(b-1)%mod;for(long long i=n;i>=n-a+1;i--)m=m*(i%mod)%mod;m=(m+1)%mod;printf("%lld %lld\n",n%mod,m); }return 0;
}