[ACNOI2022]张士超的钥匙

话题

主题背景
“要想成为标杆,绝对没有捷径;成为标杆之后,就没有回头路了!” %5Csf%20DD%28XYX%29从未忘记自己的使命。 “所谓标杆,就是为走在大家面前的人,忍受所有的赞美!”

我最大的错误是试图与%5Csf%20DD%28XYX%29进行比较。有些错误需要一辈子来偿还。

主题描述
i%5C%3B%281%5Cleqslant%20i%5Cleqslant%20m%29日,%5Csf%20OneInDark有概率参加考试,然后被%5Csf%20DD%28XYX%29超越;也有不参加考试的概率,什么都不会发生。如果在m天后,%5Csf%20OneInDark至少被%5Csf%20DD%28XYX%29超过n,则称为“太阳东打西出”。

现在求所有满足%5Csum%20b_i%3DN%5C%7Bb%5C%7D%5C%3B%280%5Cleqslant%20b_i%5Cleqslant%20a_i%29的“太阳从东方出来”的概率之和。

数据范围和提示
m%5Cleqslant%201001%5Cleqslant%20n%5Cleqslant%20N%5Cleqslant%20%5Cmin%2810%5E9%2C%5Csum%20a_i%29。输入中还给出了一个非负整数d,使得d%5Cmid%28a_i%2B1%29N%5Cleqslant%20100da_i%5Cleqslant%2010%5E9%2C%5C%3Bd%5Cleqslant%2010%5E7 等范围的其余部分是无用的。输出为模⒒。

想法

有一种奇怪的情况d%5Cmid%28a_i%2B1%29。它将在哪里使用?

在求解n%3D1n%3DN的子任务时,发现解的总数的计算可以是%5Bx%5EN%5D%5Cprod%5Cfrac%7B1-x%5E%7Ba_i%2B1%7D%7D%7B1-x%7D,那么分子实际上是关于x%5Ed的多项式,长度不超过%7BN%5Cover%20d%7D%5Cleqslant%20100。最后乘以一个%281-x%29%5E%7B-m%7D,就可以解出一个简单的数字组合。

继续做好工作,继续思考生成函数。可以看出,当前%5Csum%20b和“已经获得的keys”的个数是有用的,独立的,所以需要写成二进制生成函数
%5Cbegin%7Baligned%7D%20F_i%28x%2Cy%29%20%26%3D%5Csum_%7Bj%3D0%7D%5E%7Ba_i%7Dx%5Ej%28p_iy%5Ej%2B1-p_i%29%5C%5C%20%26%3Dp_i%5Ccdot%20%7B1-%28xy%29%5E%7Ba_i%2B1%7D%5Cover%201-xy%7D%2B%281-p_i%29%5Ccdot%5Cfrac%7B1-x%5E%7Ba_i%2B1%7D%7D%7B1-x%7D%20%5Cend%7Baligned%7D

那么答案是%5Csum_%7Bi%5Cgeqslant%20n%7D%5Bx%5ENy%5Ei%5D%5Cprod_j%20F_j%28x%2Cy%29。如何解决这个问题?

显然我们要保留分子的指数%28a_i%7B%5Crm%2B%7D1%29,所以分母要分开记录。也就是说,用%281-xy%29%5Ei%5Ccdot%281-x%29%5E%7Bm-i%7D的分母记录%5Cmathcal%20O%28m%29多项式(分子)。

然后我们依次做乘法,得到的结果相当于分母为%281-xy%29%5Ea%281-x%29%5Eb时求f%28a%2Cb%2Cc%2Cd%29的系数。既然是%5Cmathcal%20O%281%29过渡,复杂度当然是状态数%5Cmathcal%20O%5Bm%5E2%28%7BN%5Cover%20d%7D%29%5E2%5D

最后需要除以%281-xy%29%5Ea%281-x%29%5Eb,相当于乘以%5Csum_%7Bi%5Cgeqslant%200%7D%7Bi%2Ba-1%5Cchoose%20i%7D%28xy%29%5Ei%5Csum_%7Bi%5Cgeqslant%200%7D%7Bi%2Bb-1%5Cchoose%20i%7Dx%5Ei,也就是乘以
%5Csum_%7Bi%5Cgeqslant%200%7Dx%5Ei%5Csum_%7Bj%3D0%7D%5E%7Bi%7D%7Bj%2Ba-1%5Cchoose%20j%7D%7Bi-j%2Bb-1%5Cchoose%20i-j%7Dy%5Ej

不幸的是,我们必须计算%5Csum_%7Bi%5Cgeqslant%20n%7D%5By%5Ei%5DF%28y%29。也就是%5Cmathcal%20O%28m%5E3%29枚举出a%2Cbx%2Cy的指数后,我们面临的问题其实是
%5Csum_%7Bj%3Dl%7D%5E%7Bi%7D%7Bj%2Ba-1%5Cchoose%20j%7D%7Bi-j%2Bb-1%5Cchoose%20i-j%7D

因为y的指标不小于某个阈值l。由于i的范围是%5Cmathcal%20O%28n%29,所以一定不能这样计算。怎么做?

建议:组合数应递归计算。比如这个问题。虽然这看起来不太合乎逻辑。

上式也可以写成%5Csum_%7Bj%3D0%7D%5E%7Bi-l%7D%7Bj%2Bl%2Ba-1%5Cchoose%20j%2Bl%7D%7Bi-l-j%2Bb-1%5Cchoose%20i-l-j%7D。为方便递归,可简写
S%28n_1%2Cm_1%29%3D%5Csum_%7Bj%3D0%7D%5E%7Bn_2%7D%7Bj%2Bn_1%2Bm_1%5Cchoose%20j%2Bn_1%7D%7Bn_2-j%2Bm_2%5Cchoose%20n_2-j%7D

即用n_1%3Dl%2C%5C%3Bm_1%3Da-1%2C%5C%3Bn_2%3Di-l%2C%5C%3Bm_2%3Db-1代替。 m_2%2Cn_2这里没有设置为自变量,因为在后面的递归中两者不变。

最简单的方法:使用帕斯卡定律减少上指标。比如把%7Bj%2Bn_1%2Bm_1%5Cchoose%20j%2Bn_1%7D换成%7Bj%2Bn_1%2Bm_1-1%5Cchoose%20j%2Bn_1%7D%2B%7Bj%2Bn_1%2Bm_1-1%5Cchoose%20j%2Bn_1-1%7D,前者换成S%28n_1%2Cm_1%7B%5Crm-%7D1%29,后者换成S%28n_1%7B%5Crm-%7D1%2Cm_1%29。这相当于在坐标系中沿着四连通边移动;只需要选择一个边界。由于%28j%7B%5Crm%2B%7Dn_1%29是下标,必然有n_1%5Cgeqslant%200,取边界n_1%3D0。但是m_1可以取任何值。观察到m_1%3D-1可以最小化计算量。

  • n_1%3D0,那么
    %5Cbegin%7Baligned%7D%20S%280%2Cm_1%29%20%26%3D%5Csum_%7Bj%3D0%7D%5E%7Bn_2%7D%7Bj%2Bm_1%5Cchoose%20j%7D%7Bn_2-j%2Bm_2%5Cchoose%20n_2-j%7D%5C%5C%20%26%3D%5Csum_%7Bj%3D0%7D%5E%7Bn_2%7D%7Bj%2Bm_1%5Cchoose%20m_1%7D%7Bn_2-j%2Bm_2%5Cchoose%20m_2%7D%5C%5C%20%26%3D%7Bm_1%2Bm_2%2Bn_2%2B1%5Cchoose%20m_1%2Bm_2%2B1%7D%20%5Cend%7Baligned%7D

最后一步可以从%5Ctext%7Bconstructive%7D的组合含义得到:在元素%28j%7B%5Crm%2B%7Dm_1%29之后,插入一个选中的元素。或者,只需交换第一行的下标,即可获得具有二项式系数的简单卷积恒等式。

  • m_1%3D-1,那么
    S%28n_1%2C-1%29%20%3D%5Csum_%7Bj%3D0%7D%5E%7Bn_2%7D%7Bj%2Bn_1-1%5Cchoose%20j%2Bn_1%7D%7Bn_2-j%2Bm_2%5Cchoose%20n_2-j%7D%5C%5C%20%3D%5Bn_1%3D0%5D%7Bn_2%2Bm_2%5Cchoose%20n_2%7D

因为左手形式只在j%3Dn_1%3D0时产生非零值1

枚举边界值,考虑它们对S%28n_1%2Cm_1%29的贡献,然后
%5Cbegin%7Baligned%7D%20S%28n_1%2Cm_1%29%20%26%3D%5Csum_%7Bi%3D1%7D%5E%7Bn_1%7DS%28i%2C-1%29%7Bn_1%2Bm_1-i%5Cchoose%20n_1-i%7D%20%2B%5Csum_%7Bj%3D0%7D%5E%7Bm_1%7DS%280%2Cj%29%7Bn_1%2Bm_1-j-1%5Cchoose%20m_1-j%7D%5C%5C%20%26%3D%5Csum_%7Bj%3D0%7D%5E%7Bm_1%7D%7Bj%2Bm_2%2Bn_2%2B1%5Cchoose%20j%2Bm_2%2B1%7D%7Bn_1%2Bm_1-j-1%5Cchoose%20m_1-j%7D%20%5Cend%7Baligned%7D

注意“在坐标系中行走”的系数是%281%2Cj%29%5Cto%28n_1%2Cm_1%29,因为%280%2Cj%7B%5Crm%2B%7D1%29不能再通过了。

这是%5Cmathcal%20O%28m%29的枚举,所以总的时间复杂度是%5Cmathcal%20O%28m%5E4%29%5Ctext%7Bcase%20closed%7D

再聊几句:原来的公式%5Csum_%7Bj%3Dl%7D%5E%7Bi%7D%7Bj%2Ba-1%5Cchoose%20j%7D%7Bi-j%2Bb-1%5Cchoose%20i-j%7D有一个组合的意思,即第一个a框放j球,后面b框放%28i%7B%5Crm-%7Dj%29球,可以为空的方案数。唯一的限制是j%5Cgeqslant%20l,即前l格中至少有l个球。

好主意:改为枚举第l个球的位置。设为第j%5C%3B%28j%5Cgeqslant%20a%29框,则第一个%28l%7B%5Crm-%7D1%29球也在这个j框内;最后一个%28i%7B%5Crm-%7Dl%29球在最后一个%5Bj%2Ca%7B%5Crm%2B%7Db%5D盒子里,所以
%5Csum_%7Bj%3Da%7D%5E%7Ba%2Bb%7D%7Bl-1%2Bj-1%5Cchoose%20j-1%7D%7Ba%2Bb-j%2B1%2Bi-l-1%5Cchoose%20a%2Bb-j%2B1-1%7D

你会发现它和S%28l%2Ca%7B%5Crm-%7D1%29完全一样,只是S%28l%2Ca%7B%5Crm-%7D1%29中列举的j就是这里的%28a-j%29。所以上面的代数演绎是不必要的,组合的意义有时比数学演绎要好。恰恰是因为它恰好有这样的综合意义,才可以通过数学推导得到一个简单的公式!

代码

#include <cstdio> // JZM yydJUNK!!!
#include <iostream> // XJX yyds!!!
#include <algorithm> // XYX yydLONELY!!!
#include <cstring> // (the STRONG long for LONELINESS)
#include <cctype> // ZXY yydSISTER!!!
using namespace std;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long llong;
inline int readint(){
	int a = 0; int c = getchar(), f = 1;
	for(; !isdigit(c); c=getchar())
		if(c == '-') f = -f;
	for(; isdigit(c); c=getchar())
		a = (a<<3)+(a<<1)+(c^48);
	return a*f;
}

const int MAXN = 105, MOD = 998244353;
int inv[MAXN];
inline int getC(int n, int m){
	llong c = 1;
	for(int i=0; i!=m; ++i)
		c = c*(n-i)%MOD*inv[i+1]%MOD;
	return int(c);
}
inline int calc(int n1, int m1, int n2, int m2){
	if(m1 == -1) return n1 ? 0 : int(getC(n2+m2,m2)); // m2 != -1
	static int t1[MAXN], t2[MAXN]; int res = 0;
	t1[0] = 1, t2[0] = getC(m2+n2+1,m2+1);
	rep(j,1,m1) t1[j] = int(llong(n1+j-1)*t1[j-1]%MOD*inv[j]%MOD);
	rep(j,1,m1) t2[j] = int(llong(m2+n2+1+j)*t2[j-1]%MOD*inv[j+m2+1]%MOD);
	rep(j,0,m1) res = int((res+llong(t1[j])*t2[m1-j])%MOD);
	return res;
}

int dp[2][MAXN][MAXN][MAXN];
int main(){
	int m = readint(), d = readint();
	int N = readint(), n = readint();
	rep(i,(inv[1]=1)+1,m) inv[i] = int(
		llong(MOD-MOD/i)*inv[MOD%i]%MOD);

	const int Nd = N/d;
	****dp = 1; // x^0 y^0
	for(int i=1,fr=0,a; i<=m; ++i,fr^=1){
		a = (readint()+1)/d; llong p = readint();
		rep(j,0,i) rep(x,0,Nd) rep(y,0,x){
			int &v = dp[i&1][j][x][y] = int( (
				(x < a ? 0 : (p-1)*dp[fr][j][x-a][y])
				+ (MOD+1-p)*dp[fr][j][x][y] ) %MOD );
			if(!j) break; // cannot choose it here
			v = int((v+p*dp[fr][j-1][x][y])%MOD);
			if(x >= a && y >= a) v = int((v+
				(MOD-p)*dp[fr][j-1][x-a][y-a])%MOD);
		}
	}

	int ans = 0;
	rep(a,0,m) rep(x,0,Nd) rep(y,0,x) if(dp[m&1][a][x][y]){
		const int l = std::max(0,n-y*d);
		if(l > N-x*d) continue; // invalid
		ans = int((ans+llong(dp[m&1][a][x][y])
			*calc(l,a-1,N-x*d-l,m-a-1))%MOD);
	}
	printf("%d\n",ans);
	return 0;
}

版权声明:本文为博主OneInDark原创文章,版权归属原作者,如果侵权,请联系我们删除!

原文链接:https://blog.csdn.net/qq_42101694/article/details/123047901

共计人评分,平均

到目前为止还没有投票!成为第一位评论此文章。

(0)
乘风的头像乘风管理团队
上一篇 2022年2月22日 下午4:24
下一篇 2022年2月22日 下午4:47

相关推荐