首页 > 其他分享 >[ABC331G] Collect Them All 题解

[ABC331G] Collect Them All 题解

时间:2024-02-27 22:00:51浏览次数:24  
标签:dots Them frac int 题解 sum Collect ans define

\(\textbf{Statement.}\)

有 \(M\) 种颜色,用 \(1\sim M\) 编号,每次抽奖抽中第 \(i\) 种颜色的概率为 \(\frac{c_i}{N}\),其中 \(\sum c_i=N\),求抽中每种颜色至少一次的期望次数。

\(1\le M\le N\le 2\times 10^5\)。

\(\textbf{Solution.}\)

发现直接求不好做,考虑容斥。记 \(f(n)\) 表示在前 \(n\) 天抽中每种颜色至少一次的概率,\(g(S)=\frac{\sum_{i\in S}c_i}{N}\)。枚举第 \(n\) 天时抽过的颜色集合作容斥,易得:

\[f(n)=\sum_{S\subset \{1,2,\dots,M\}}(-1)^{M-|S|}g(S)^n \]

那么在第 \(n+1\) 天还没收集完的概率就是 \(1-f(n)\),所以答案就转化为(注意,\(\subset\) 是真包含于,不能相等,\(\subseteq\) 是包含于,可以相等):

\[\begin{aligned} &\sum_{n=0}^{\infty}1-f(n)\\ &=\sum_{n=0}^{\infty}\left(1-\sum_{S\subset \{1,2,\dots,M\}}(-1)^{M-|S|}g(S)^n\right)\\ &=\sum_{n=0}^{\infty}\sum_{S\subseteq \{1,2,\dots,M\}}(-1)^{M-|S|+1}g(S)^n\\ &=\sum_{S\subseteq \{1,2,\dots,M\}}(-1)^{M-|S|+1}\sum_{n=0}^{\infty}g(S)^n\\ &=\sum_{S\subseteq \{1,2,\dots,M\}}(-1)^{M-|S|+1}\frac{1}{1-g(S)}\\ &=\sum_{k=0}^{N-1}\frac{N}{N-k}\sum_{g(S)=\frac k N}(-1)^{M-|S|+1} \end{aligned} \]

然后就可以用生成函数做了,跟 P9773 相同的做法,答案就是:

\[\sum_{k=0}^{N-1}[x^k](-1)^{M+1}\prod_{i=1}^{M}(1-x^{c_i}) \]

考虑怎么求出 \(\prod_{i=1}^{M}(1-x^{c_i})\),可以先将这些次数为 \(c_i\) 的多项式加入一个堆,每次弹出两个次数最小的,用 NTT 暴力合并,时间复杂度 \(O((N+M)\log M\log N)\)。

参考代码:

#include<bits/stdc++.h>
#define ll long long
#define int long long
#define mxn 500003
#define md 998244353
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define rept(i,a,b) for(int i=a;i<b;++i)
#define drep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
int power(int x,int y){
	int ans=1;
	for(;y;y>>=1){
		if(y&1)ans=(ll)ans*x%md;
		x=(ll)x*x%md;
	}
	return ans;
}
struct node{
	vector<int>a;
};
inline bool operator<(node x,node y){
	return x.a.size()>y.a.size();
}
int n,m,a[mxn],f[mxn],f1[mxn],rev[mxn];
ll ans;
priority_queue<node>q;
void ntt(int *a,int n,int flag){
	rept(i,0,n)if(i<rev[i])swap(a[i],a[rev[i]]);
	for(int h=1;h<n;h<<=1){
		int x,y,s=power(3,499122176/h);
		for(int j=0;j<n;j+=h<<1){
			int w=1;
			for(int k=j;k<j+h;++k){
				x=a[k],y=w*a[k+h]%md;
				a[k]=(x+y)%md;
				a[k+h]=(x-y+md)%md;
				w=w*s%md;
			}
		}
	}
	if(flag==-1){
		int p=power(n,md-2);
		reverse(a+1,a+n);
		rept(i,0,n)a[i]=a[i]*p%md;
	}
}
signed main(){
	scanf("%lld%lld",&n,&m);
	rep(i,1,m){
		scanf("%lld",&a[i]);
		node s;
		s.a.resize(a[i]+1);
		s.a[0]=1,s.a[a[i]]=-1;
		q.push(s);
	}
	while(q.size()>1){
		node a=q.top();q.pop();
		node b=q.top();q.pop();
		node c;c.a.resize(a.a.size()+b.a.size()-1);
		int k,s;
		for(k=0,s=1;s<c.a.size();s<<=1,++k);
		rept(i,0,s)rev[i]=(rev[i>>1]>>1)|((i&1)<<(k-1));
		rept(i,0,a.a.size())f[i]=a.a[i];
		rept(i,a.a.size(),s)f[i]=0;
		rept(i,0,b.a.size())f1[i]=b.a[i];
		rept(i,b.a.size(),s)f1[i]=0;
		ntt(f,s,1);ntt(f1,s,1);
		rept(i,0,s)f[i]=f[i]*f1[i]%md;
		ntt(f,s,-1);
		rept(i,0,c.a.size())c.a[i]=f[i];
		q.push(c);
	}
	node s=q.top();
	rept(i,0,n){
		ans=(ans+(m&1?1:-1)*s.a[i]%md*n%md*power(n-i,md-2))%md;
	}
	cout<<(ans+md)%md;
	return 0;
}

标签:dots,Them,frac,int,题解,sum,Collect,ans,define
From: https://www.cnblogs.com/zifanoi/p/18038506

相关文章

  • [ARC087F] Squirrel Migration 题解
    洛谷题面AT题面如果两条路径不存在交点,则两条路径各选一个端点交换后两路径相交,答案不会变劣。考虑所有路径两两相交的情况,因为图是一棵树,所以这些路径会交于一点。以这个点为根,那么最大的子树大小一定不超过\(\fracn2\),所以这个点是树的重心,每条路径的端点一定在两个不......
  • 个人题解:2024 年湖北省省队选拔集训暨能力测试 第一试
    时与风对每条边进行BFS。二维偏序部分用vector存一下就行了。花神诞日引理:对于\(a<b<c\),\(\min(a\text{XOR}b,b\text{XOR}c)\leqa\text{XOR}c\)。证明:考虑比较\(a,c\)二进制下第一位不同,也就是\(a=(X0\dots)_{(2)},c=(X1\dots)_{2}\)。因为\(b\in(a,c)\)所以......
  • CSP-S 2023 题解
    T1一开始所有密码都没被标记。对于每个输入的状态枚举一遍所有没标记的密码,判断是否可能是正确密码,如果不行就标记一下。最后输出没被标记的密码个数。总共只有\(10^5\)个密码,可以轻松通过。难度:橙。T2见CF1223FStackExterminableArrays题解。难度:蓝。T3大模拟,直......
  • 2024牛客寒假算法基础集训营5 题解 ( A,C,G,H,I,L,M )
    2024牛客寒假算法基础集训营5题解(A,C,G,H,I,L,M)A mutsumi的质数合数题意有一个由\(n\)个正整数组成的数组,她想知道数组中质数和合数共有几个。思路由质数和合数的定义可知,正整数范围内除\(1\)外,要么是质数要么是合数,本题直接统计不是\(1\)的正整数的个数即可代码......
  • 题解 CF963E Circles of Waiting
    令\(f_{i,j}\)表示\((i,j)\)走出以\((0,0)\)为圆心,半径为\(R\)的期望步数,显然所有在圆外的点\((i,j)\)满足\(f_{i,j}=0\)。有\(f_{i,j}=p_1f_{i-1,j}+p_2f_{i,j-1}+p_3f_{i+1,j}+p_4f_{i,j+1}\)。这东西很套路,高斯消元就行,但状态数是\(O(R^2)\)的,复杂度\(O(R^......
  • 题解 CF725G Messages on a Tree
    updateon2023.8.9修正了一些错误。\(\texttt{link}\)第\(i\)条信息的传输可以表示成\(x_i\)走到\(x_i\)的某一祖先再走回\(x_i\)的路径。所以答案只和\(x_i\)的这一祖先有关,记为\(f_i\),则\(ans_i=t_i+2\timesdep_{x_i}-2\timesdep_{f_i}\)。若\(x_i\)在\(f......
  • 题解 CF1781G Diverse Coloring
    \(\texttt{link}\)题意给定一棵\(n\)个点的二叉树,现对其每个点染成黑色或白色。一种合法的染色方案满足:对于所有黑色的点,都存在白色的点与之相邻。对于所有白色的点,都存在黑色的点与之相邻。一种染色方案的权值是染成黑色的点数与染成白色的点数之差的绝对值。\(\foral......
  • 题解 CF1523H Hopping Around the Array
    \(\texttt{link}\)题意数轴上有\(n\)个点,每个点有属性\(a_i\),在第\(i\)个点可以花费\(1\)的步数移动至\([i,i+a_i]\)中任意一个点。定义一次操作为选出一个\(i\),使\(a_i\getsa_i+1\)。\(q\)组询问,每次给出\(l,r,k\),求有\(k\)次操作机会时,从第\(l\)个点走到......
  • 题解 CF983D Arkady and Rectangles
    \(\texttt{link}\)题意平面直角坐标系上给定\(n\)个矩形,第\(i\)个矩形颜色为\(i\),颜色大的矩形将覆盖颜色小的矩形,问最后能看到几种颜色。\(1\len\le10^5,|x_i|,|y_i|\le10^9\)题解首先离散化,考虑扫描线如何维护序列上的颜色。一个区间\([l,r]\)投射到线段树上\(......
  • AT_arc117_c [ARC117C] Tricolor Pyramid 题解
    [ARC117C]TricolorPyramid博客阅读体验(也许)更佳题意给一个金字塔的底部颜色组成和生长规律,问顶部的颜色是什么。分析试几次就可以很容易得到的一种构造:令颜色B为\(0\),W为\(1\),R为\(2\)。设左右两个方块的颜色分别为\(col_l\)和\(col_r\),则生长规则可以描......