首页 > 技术文章 > [校内赛20200903/牛客2020多校赛第五场]简单题 Easy

crashed 2020-09-04 18:08 原文

题目

题目描述

对于给定参数 \(n, m, k\) ,合法的正整数序列 \(a,b\) 分别满足:

  1. \(a\)\(b\) 的长度都是 \(k\)

  2. \(\sum_{i=1}^k a_i=n\)\(\sum_{i=1}^k b_i=m\)

现在对于合法的 \(a\)\(b\),定义它们的贡献 \(f(a,b)\) 为:

\[\prod_{i=1}^k \min\{a_i,b_i\} \]

现在请求出,所有合法的 \(a,b\)\(f(a,b)\) 之和。

数据范围:

对于 \(60\%\) 的数据,满足 \(1\le n,m,k\le 100\)

对于 \(80\%\) 的数据,满足 \(1\le n,m,k\le 1000\)

对于 \(100\%\) 的数据,满足 \(1\le n,m,k\le 10^6\)

分析

第一次见到二元生成函数的题目,我人傻了。

60 pts

不难想到如下的 DP :

\(f(i,j,k)\):前 \(i\) 个数,此时 \(\sum a=j,\sum b=k\) 的贡献之和。

暴力转移是 \(O(kn^4)\) 的:

\[f(i,j,k)=\sum_{p=1}^{j}\sum_{q=1}^{k}f(i-1,j-p,k-q)\times \min\{p,q\} \]

然后不难想到运用经典技巧优化:我们枚举一下 \(\min\{p,q\}\) 。那么此时合法的 \(f(i-1,j-p,k-q)\) 就对应了一段一维前缀和,每次转移之前预处理一下就可以做到 \(O(n)\) 转移。

时间是 \(O(kn^3)\) ,可以获得 60 pts 。

80 pts

from Lucky_Glass

从另一个角度来看问题,我们现在对 \(p\) 序列:

\[p_i=\min\{a_i,b_i\} \]

直接计算。首先我们可以 DP 处理出来 \(p\) 序列的贡献:

\(g(i,j)\):前 \(i\) 个数, \(p\) 序列的和为 \(j\) 时的贡献和。

转移有:

\[g(i,j)=\sum_{k=1}^j g(i-1,j-k)\times k \]

转移时 \(O(kn^2)\) 的,之后再来优化。

然后考虑,对于一个和固定为 \(s\)\(p\) 序列来说,它被计算的次数之和。

首先我们确定 \(a_i\)\(b_i\) 每一位至少要填上 \(p_i\) 。我们现在可以让 \(a_i\)\(b_i\) 中的一个变大。

首先枚举 \(a\) 中变大的值的数量,设为 \(t\) 。这里我们要求必须变大,那么就是隔板法的问题:

\[\binom{k}{t}\times \binom{n-s-1}{t-1} \]

然后考虑 \(b\) 中变大的值的数量。 \(a\) 变大了的位置 \(b\) 就不能变了。并且,此时 \(b\) 也可以选择不变大,于是总共方案就是:

\[\binom{k}{t}\times \binom{n-s-1}{t-1}\times \binom{m-s+t-1}{t-1} \]

此时单次询问就是 \(O(n^2)\) 的。

之后再来优化一下 DP 。可以发现,这就是一个三角形的前缀和,可以直接维护。于是就变成了 \(O(kn)\)

Lucky_Glass txdy!

100 pts

这里有两种我听得懂的推导方法。

方法 1

注意这里 \(a\)\(b\) 两个序列是不同的,因此我们的生成函数需要用不同的形式变量

不考虑 \(\min\{a,b\}\) 的贡献,我们可以利用如下的生成函数来表示:

\(a\) 的一项可以表示为:\(\frac{x}{1-x}=\sum_{i=1}x^i\) 。同理有 \(b\) 的一项: \(\frac{y}{1-y}\)

那么总共的方案数就是:

\[\left(\frac{xy}{(1-x)(1-y)}\right)^k=\frac{x^ky^k}{(1-x)^k(1-y)^k} \]

但是此时没有 \(\min\{a,b\}\) 的贡献 ......

注意到一个性质。对于自然数 \(n\) ,满足:

\[n=\sum_{0\le k< n} 1 \]

那么对于一项 \(x^ny^m\) ,我们就可以通过类似的方法,将 \(\min\{n,m\}\) 的贡献均摊:

\[\min\{n,m\}x^ny^m=\sum_{k=0}^{\min\{n,m\}}x^ky^k\times x^{n-k}y^{m-k} \]

仔细一看,你会发现,这就是一个卷积的形式。这提示我们,对于 \(a,b\) 的每一项,我们可以额外卷上:

\[\sum_{i=0}x^iy^i \]

这个式子,以达到计算 \(\min\{n,m\}\) 这个贡献的目的。

不难得到 \(\sum_{i=0}x^iy^i\) 的闭形式:

\[\sum_{i=0}x^iy^i=\frac{1}{1-xy} \]

然后原问题的生成函数就是:

\[f(x,y)=\frac{x^ky^k}{(1-xy)^k(1-x)^k(1-y)^k} \]

原问题的答案是 \([x^ny^m]f(x,y)\) ,我们现在就要计算这个系数。

显然可以发现 \([x^{n-k}y^{m-k}]\frac{1}{(1-xy)^k(1-x)^k(1-y)^k}=[x^ny^m]f(x,y)\) 。问题转化为了求等式左侧的值。

不难想到,我们应该枚举 \(\frac{1}{(1-xy)^k}\) 用到的指数 \(t\) 。此时它的系数是 \(\binom{k+t-1}{t}\)

然后再考虑: \([x^{n-t-k}]\frac{1}{(1-x)^k}=\binom{n-t-1}{k-1},[y^{m-t-k}]\frac{1}{(1-y)^k}=\binom{m-t-1}{k-1}\)

答案就是:

\[[x^ny^m]f(x,y)=\sum_{t=0}^{\min\{n-k,m-k\}} \binom{k+t-1}{t}\binom{n-t-1}{k-1}\binom{m-t-1}{k-1} \]

听 zjx 巨佬说这个式子还有组合意义......恕在下太愚蠢了。

方法 2

from Tiw_Air_OAO

我们将要直接构造出原问题的生成函数。

首先考虑这个式子:

\[\sum_{i=0}ix^iy^i \]

稍微算一算可以发现它的闭形式是:

\[\sum_{i=0}ix^iy^i=\frac{xy}{(1-xy)^2} \]

推导请见后面的 部分。

然后考虑让 \(i\) 变成 \(\min\{n,m\}\) ,或者说,我们应该让 \(x^iy^i\) 变成 \(x^ny^i(n>i)\) 或者 \(x^iy^m(m\ge i)\)

第一种情况等价于乘上 \(\sum_{i=1}x^i=\frac{x}{1-x}\) ,第二种情况等价于 \(\sum_{i=0}y^i=\frac{1}{1-y}\)

于是我们就可以得到其中一项的生成函数是:

\[\begin{aligned} & \frac{xy}{(1-xy)^2}\left(\frac{x}{1-x}+\frac{1}{1-y}\right)\\=& \frac{xy}{(1-xy)^2}\times\frac{(x-xy)+(1-x)}{(1-x)(1-y)}\\=& \frac{xy}{(1-xy)^2}\times \frac{1-xy}{(1-x)(1-y)}\\=& \frac{xy}{(1-xy)(1-x)(1-y)}\end{aligned} \]

最终问题的生成函数就是:

\[\left(\frac{xy}{(1-xy)(1-x)(1-y)}\right)^k=\frac{x^ky^k}{(1-xy)^k(1-x)^k(1-y)^k} \]

Tiw_Air_OAO yyds!

本题中一些有价值的点:

  1. 60 pts 升级为 80 pts 的过程中,我们的方向从分别枚举 \(a,b\) 变成了直接枚举 \(p\) ,之后再考虑 \(p\) 的数量(或者 \(p\) 的限制)。可以发现这样的思路在很多题目中都有运用。
  2. 100 pts 中,第一种构造方法,对于 \(\min\) 的贡献的处理,具有启发性。
  3. 第二种构造方法的处理方式也很有意义。两种构造方法对应了两种对于 \(\min\) 函数的理解:
    • \(\min\) 意味着其中的一个较小值 (构造 1);
    • \(\min\) 意味着两个都至少要大于 \(\min\) 值(构造 2);
  4. 这道题可以帮助你树立 " tly 和 zjx yyds "的正确观念。

代码

#include <cstdio>

typedef long long LL;

const int mod = 998244353;
const int MAXN = 5e5 + 5;

template<typename _T>
void read( _T &x )
{
	x = 0;char s = getchar();int f = 1;
	while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}
	while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}
	x *= f;
}

template<typename _T>
void write( _T x )
{
	if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }
	if( 9 < x ){ write( x / 10 ); }
	putchar( x % 10 + '0' );
}

int fac[MAXN << 1], ifac[MAXN << 1];
int N, M, K;

int Sub( int x, const int v ) { return x < v ? x + mod - x : x - v; }
int Mul( LL x, const int v ) { x *= v; if( x >= mod ) x %= mod; return x; }
int Add( int x, const int v ) { return x + v >= mod ? x + v - mod : x + v; }
int C( int n, int m ) { return n < m ? 0 : Mul( fac[n], Mul( ifac[m], ifac[n - m] ) ); }

int Qkpow( int base, int indx )
{
	int ret = 1;
	while( indx )
	{
		if( indx & 1 ) ret = Mul( ret, base );
		base = Mul( base, base ), indx >>= 1;
	}
	return ret;
}

void Init( const int siz )
{
	fac[0] = 1;
	for( int i = 1 ; i <= siz ; i ++ ) fac[i] = Mul( fac[i - 1], i );
	ifac[siz] = Qkpow( fac[siz], mod - 2 );
	for( int i = siz - 1 ; ~ i ; i -- ) ifac[i] = Mul( ifac[i + 1], i + 1 );
}

int main()
{
	int T;
	read( T );
	Init( 1e6 );
	while( T -- )
	{
		read( N ), read( M ), read( K ); int ans = 0;
		for( int i = 0 ; i <= N && i <= M ; i ++ )
			ans = Add( ans, Mul( C( i + K - 1, i ), Mul( C( N - i - 1, K - 1 ), C( M - i - 1, K - 1 ) ) ) );
		write( ans ), putchar( '\n' );
	}
	return 0;
}

关于 \(\sum_{i-0}ix^iy^i\) 。记 \(S_n=\sum_{i=0}^{n}ix^iy^i\) 。我们可以直接错位相减:

(当然是默认 \(0<x,y<1\) 啦)

\[\begin{aligned} S_n-xyS_{n}&= \sum_{i=0}^nix^iy^i-\sum_{i=1}^{n+1}(i-1)x^{i}y^{i}\\&= \sum_{i=1}^nx^iy^i-nx^{n+1}y^{n+1}\\&= \frac{xy(1-x^{n}y^{n})}{1-xy}-nx^{n+1}y^{n+1}\\ S_n&= \frac{1}{1-xy}\times \left(\frac{xy(1-x^{n}y^{n})}{1-xy}-nx^{n+1}y^{n+1}\right)\\\Rightarrow \lim_{n\rightarrow \infty}S_n&= \frac{xy}{(1-xy)^2}\end{aligned} \]

推荐阅读