2020牛客暑期多校训练营（第五场）C Easy

2020牛客暑期多校训练营（第五场）C Easy

2020牛客暑期多校训练营（第五场）C Easy

题意

C Easy
有两个长度为k的正整数序列A，B满足 ∑ i = 1 k a i = N sum_{i=1}^ka_i=N ∑i=1k​ai​=N, ∑ i = 1 k b i = M sum_{i=1}^kb_i=M ∑i=1k​bi​=M
求 P = ∏ i = 1 k m i n ( a i , b i ) P=prod_{i=1}^kmin(a_i,b_i) P=∏i=1k​min(ai​,bi​)的得分和。

zjut4 题解

设 n < m n<m n<m，满足条件的a和b的方案构造的生成函数如下

( 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+x2…+…+xn)k拆开后的 x n x^n xn项的系数就表示 a i a_i ai​的种类数，y同理。

因此可知 x n y 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 m ) (x+x^2…+…+x^n)(y^1+y^2…+…+y^m) (x+x2…+…+xn)(y1+y2…+…+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 < j i<j i<j）,考虑 x i − 1 y j − 1 x^{i-1}y^{j-1} xi−1yj−1, x i − 2 y j − 2 x^{i-2}y^{j-2} xi−2yj−2… x 1 y j − i + 1 x^1y^{j-i+1} x1yj−i+1项，每一项都乘上 x y xy xy的某个幂次，就可以使每一项都具有 m i n ( a i , b i ) min(a_i,b_i) min(ai​,bi​)的系数。因此对于单一的一项，构造如下生成函数
( x + x 2 … + … + x n ) k ( y 1 + y 2 … + … + y m ) k ( 1 + x y + ( x y ) 1 + ( x y ) 2 + … + ( x y ) n − k ) (x+x^2…+…+x^n)^k(y^1+y^2…+…+y^m)^k(1+xy+{(xy)}^1+{(xy)}^2+…+{(xy)}^{n-k}) (x+x2…+…+xn)k(y1+y2…+…+ym)k(1+xy+(xy)1+(xy)2+…+(xy)n−k)
再扩展到k项为如下生成函数
( x + x 2 … + … + x n ) k ( y 1 + y 2 … + … + y m ) k ( 1 + x y + ( x y ) 1 + ( x y ) 2 + … + ( x y ) n − k ) k (x+x^2…+…+x^n)^k(y^1+y^2…+…+y^m)^k(1+xy+{(xy)}^1+{(xy)}^2+…+{(xy)}^{n-k})^k (x+x2…+…+xn)k(y1+y2…+…+ym)k(1+xy+(xy)1+(xy)2+…+(xy)n−k)k
这个式子通过公式 G ( x ) = 1 1 − x = x + x 2 … + … + x n G(x)=frac{1}{1-x}=x+x^2…+…+x^n G(x)=1−x1​=x+x2…+…+xn就可以转化为题解中的式子 x y ( 1 − x ) ( 1 − y ) ( 1 − x y ) frac{xy}{(1-x)(1-y)(1-xy)} (1−x)(1−y)(1−xy)xy​（所以题解为什么要转过来啊orz）
在生成函数中构造 x n y m x^ny^m xnym就可以枚举xy的系数 i = [ 0 , n − k ] i=[0,n-k] i=[0,n−k]（因为序列要是正整数，所以先减去k个数），然后补全x，y的系数，其中通过广义二项式 G n ( x ) = ∑ k = 0 ∞ C n + k − 1 k x k G^n(x)=displaystylesum_{k=0}^{infty}C_{n+k-1}^kx^k Gn(x)=k=0∑∞​Cn+k−1k​xk扩展。公式如下： r e s = ∑ i = 0 n − k C k + i − 1 i C k + n − k − i − 1 n − k − i C k + m − k − i − 1 m − k − i res=displaystylesum_{i=0}^{n-k}C_{k+i-1}^iC_{k+n-k-i-1}^{n-k-i}C_{k+m-k-i-1}^{m-k-i} res=i=0∑n−k​Ck+i−1i​Ck+n−k−i−1n−k−i​Ck+m−k−i−1m−k−i​

代码

#include<bits/stdc++.h>
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("%lldn", res);}
}