2020牛客夏季多校訓練キャンプ(第5回)C Easy

15747 ワード

2020牛客夏季多校訓練キャンプ(第5回)C Easy
に言及
C Easyにはkの長さの正の整数列Aが2つあり,BはΣi＝1 ka i＝Nsum＿を満たす{i=1}^ka_i=N ∑i=1kai=N, ∑ i = 1 k b i = M\sum_{i=1}^kb_i=MΣi=1 kbi=M P=∏i=1 km i n(a i,b i)P=prod_を求める{i=1}^kmin(a_i,b_i)P=∏i=1 kmin(ai,bi)の種類.
問題解
n( x + x 2 … + … + x n ) k ( y 1 + y 2 … + … + y m ) k (x+x^2…+…+x^n)^k(y^1+y^2…+…+y^m)^k (x+x2…+…+xn)k(y1+y2…+…+ym)k
ここでx,y x,y x,yのべき乗は与えられた値を表すので、(x+x 2...+...+x n)k(x+x^2...+...+x^n)^k(x+x 2...+...+xn)k分解後のx nx^n xn項の係数はa i a_i aiの種類数,yは同じである.
従って、x ny m x^ny^m xnymの係数は、付与値によって求められるスキーム数であることが分かる.そして構築問題におけるm i n(a i,b i)min(a_i,b_i)min(ai,bi)の値は、単一の一対(a i,b i)(a_i,b_i)(ai,bi)であり、その生成関数は(x+x 2...+...+x n)(y 1+y 2...+y...+y m)(x+x^2...+x^n)(y^1+y^2...+y^2...+y^m)(x+x x 2...+xn)(y 1+y 2...+y 2...+ym)である.この場合、この項の寄与価値はm i n(a i,b i)min(a_i,b_i)min(ai,bi)であり、生成関数の各項の係数は1であることは明らかである.正しい寄与の生成関数を構築するために、各ペアの(a i,b i)(a_i,b_i)(ai,bi)にm i n(a i,b i)min(a_i,b_i)min(ai,bi)の係数があるように、従って、各x i y j x^iy^j xiyj(iコード#コード#

#include
typedef long long ll;
using namespace std;
#define N 1000005
#define mod 998244353
ll powmod(ll a, ll b){
	ll res = 1;
	a %= mod;
	while(b) {
		if(b & 1) {
			res = res * a % mod;
		}
		b >>= 1;
		a = a * a % mod;
	}
	return res;
}
ll fac[N], inv[N];
void init() {
	fac[0] = 1;
	for(int i = 1; i < N; i++) {
		fac[i] = fac[i - 1] * i % mod;
	}
	inv[N - 1] = powmod(fac[N - 1], mod - 2);
	for(int i = N - 2; i >= 0; i--) {
		inv[i] = inv[i + 1] * (i + 1) % mod;
	}
}
ll c(ll n, ll m) {
	if(m > n) {
		return 0;
	}
	if(m == 0) return 1;
	if(n < N) return fac[n] * inv[m] % mod * inv[n - m] % mod;
	//c(m,k) = m!/(k! * (m - k))= m-k+1~m/(k!)
	ll res = inv[m];
	for(int i = n - m + 1; i <= n; i++) {
		res = res * i % mod;
	}
	return res;
}
int main() {
	init();
	int t;
	scanf("%d", &t);
	while(t--) {
		int n, m, k;
		scanf("%d%d%d", &n, &m, &k);
		if(n > m) swap(n, m);
		ll res = 0;
		for(int i = 0; i <= n - k; i++) {
			res = ((ll)res + c(k + i - 1, i) 
						* c(k + n - k - i - 1, n - k - i) % mod 
			 			* c(k + m - k - i - 1, m - k - i) % mod) % mod;
		}
		printf("%lld
", res);
	}
}

dbpediaの研究その16

DOMDocument::loadHTML が meta の charset を解釈してくれない問題と対策