AtCoder ARC #113 : D - Sky Reflector

おおむねレート通りの結果になった回。
https://atcoder.jp/contests/arc113/tasks/arc113_d

問題

正整数H,W,Kが与えられる。
各要素に1～Kのいずれかの整数を埋めたH*Wの行列Pを考える。
各行の最小値を並べた数列をA、各列の最大値を並べた数列をBとする。
(A,B)の組み合わせは何通りか。

解法

H=1またはW=1の場合はそれぞれK^H、K^Wで自明。
以下HもWも2以上のケースを考える。

f(x) := Aの最大値がx以下であるAの組み合わせ
g(x) := Aの最大値がちょうどxであるAの組み合わせ
とすると、
g(x) = f(x) - f(x-1)
となる。
この時、行毎にAを取る要素、すなわちA[r]=P[r][x]となるxを行ごとに散らしたとすると、各列x以上の任意の値を取れる要素が1つ以上確保できる。なので、Bはx以上の任意の値で構成できる。
よってg(x)*((K+1-x)^W)をx毎に足し合わせればよい。

int H,W,K;
const ll mo=998244353;
ll dp[202020];

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>K;
	
	ll ret=0;
	if(H==1) {
		ret=modpow(K,W);
	}
	else if(W==1) {
		ret=modpow(K,H);
	}
	else {
		for(i=1;i<=K;i++) {
			dp[i]=modpow(i,H);
		}
		for(i=K;i>=1;i--) {
			(dp[i]+=mo-dp[i-1])%=mo;
			(ret+=dp[i]*modpow(K+1-i,W))%=mo;
		}
	}
	
	
	cout<<ret<<endl;
	
	
}

まとめ

これは割とすんなり解けたね。