ARC113D题解

ARC113D - Sky Reflector

题目大意

有一个$n$行$m$列的表格，你可以在每个表格中填入一个$1$到$k$之间的整数，定义序列$A,B$如下：

• 对于每一个$i=1,2,\dots ,n$，$A_i$是第$i$行的最小值
• 对于每一个$j=1,2,\dots ,m$，$B_i$是第$j$行的最大值

求有多少对不同的序列$(A,B)$，答案模$998244353$。

题解

当$n==1$或$m==1$时，答案如下：

• 若$n==1$，则答案为$k^m$
• 若$m==1$，则答案为$k^n$

接下来来讨论$n\ge 2$且$m\ge 2$的情况。

设第$i$行第$j$列的数为$C_{i,j}$，根据题意，我们可以得到：
$$\forall i\in [1,n],j\in [1,m]，A_i\le C_{i,j}\le B_j$$

推得 max ⁡ { A i } ≤ min ⁡ { B j } \max\{A_i\}\leq\min\{B_j\} max{Ai​}≤min{Bj​}

对于一对序列$(A,B)$，若满足 max ⁡ { A i } ≤ min ⁡ { B j } \max\{A_i\}\leq\min\{B_j\} max{Ai​}≤min{Bj​}，则可以由以下方法来构造表格。

其中蓝色代表这个位置的数是这一行的最小值，橙色代表这个位置的数是这一列的最大值。由于 max ⁡ { A i } ≤ min ⁡ { B j } \max\{A_i\}\leq\min\{B_j\} max{Ai​}≤min{Bj​}，所以对于表格上的任意的格子$(i,j)$，都满足$A_i\le B_j$，$C_{i,j}$可以取$A_i$和$B_j$之间的任意值。

于是，题意就变为：求有多少对序列$(A,B)$，满足$A_i$和$B_j$都为$1$到$k$之间的整数，且 max ⁡ { A i } ≤ min ⁡ { B j } \max\{A_i\}\leq\min\{B_j\} max{Ai​}≤min{Bj​}。

我们可以枚举$A_i$的最大值，若最大值为$t$，则不同的$A$序列的数量为$(t^n-t^{n-1})$，不同的$B$序列的数量为$(k-t+1{)}^m$，此时不同的序列对$(A,B)$的数量为$(t^n-t^{n-1})\cdot (k-t+1{)}^m$。

code

#include
using namespace std;
long long n,m,k,ans;
long long mod=998244353;
long long mi(long long t,long long v){
	if(t==0) return 0;
	if(v==0) return 1;
	long long re=mi(t,v/2);
	re=re*re%mod;
	if(v&1) re=re*t%mod;
	return re;
}
int main()
{
//	freopen("mirror.in","r",stdin);
//	freopen("mirror.out","w",stdout);
	scanf("%lld%lld%lld",&n,&m,&k);
	if(n==1||m==1){
		ans=mi(k,n+m-1);
		printf("%lld",ans);
		return 0;
	}
	for(int i=1;i<=k;i++){
		ans=(ans+(mi(i,n)-mi(i-1,n)+mod)%mod*mi(k-i+1,m)%mod)%mod;
	}
	printf("%lld",ans);
	fclose(stdin);
	fclose(stdout);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30