2020牛客夏季多校訓練キャンプ(第5回)C Easy
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コード#コード#
に言及
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,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);
}
}