「UR 19」通用评测号&&「集训队作业2018」喂鸽子 && 「AGC038E」Gachapon

「UR 19」通用评测号
考虑一个等价问题：每个燃料舱容量无限，求在所有燃料舱\(\ge b\)的时刻，燃料\(\ge a\)的燃料舱个数的期望。
根据期望的线性性，只需要对每个燃料舱计算在它燃料\(=a\)的时刻存在其他燃料舱\(的概率
每个燃料舱等价　计算第一个燃料舱概率乘n即可
容斥原理　强制令\(p\)个小于\(b\) 容斥系数为\((-1)^{p-1}\times \binom{n-1}{p}\)
相当于每次选一个\([1,p+1]\)之间的数当出现\(a\)个一时其他数均小于\(b\)的概率
做法一：

\[ans=\sum_{x_2,x_3,\cdots,x_{p+1}\in [0,b-1]}\frac{(a-1+\sum x_i)!}{(a-1)!\prod(x_i!)}\left(\frac{1}{p+1} \right)^{a+\sum x_i} \]

\[=\sum_{i=0}^{p(b-1)}\frac{(a-1+i)!}{(a-1)!}\left(\frac{1}{p+1}\right)^{a+i}[x^i]\left(\sum_{j=0}^{b-1}\frac{x^j}{j!}\right)^p \]

复杂度\(O(n^3\log n)\)
做法二:

\[ans=\sum_{j=0}^{p(b-1)}g_{p,j}\times\binom{j+a-1}{j}\times\left(\frac{1}{p+1}\right)^{j+a} \]

其中\(g_{p,j}\)表示\(p\)个数总共出现\(j\)次且每个数出现不超过\(b\)次的方案数
\(g\)转移是总的去掉不合法的情况

\[g_{i,j}=g_{i,j-1}\times i-i\times\binom{j-1}{b-1}\times g_{i-1,j-b} \]

复杂度\(O(n^3)\)

「集训队作业2018」喂鸽子
使用min_max容斥

\[ans=\sum_{i=1}^{n}(-1)^{i+1}\binom{n}{i}\dfrac{n}{i}F(i) \]

\(F(i)\)表示有鸽子吃饱的期望次数乘\(\frac{n}{i}\)是期望\(\frac{n}{i}\)步喂食到指定集合的鸽子
和上题类似

\[F(i)=\sum_{j=0}^{(i-1)(k-1)}(j+k)g_{i-1,j}\times i\left(\frac{1}{i}\right)^{j+k}\binom{j+k-1}{j} \]

代码十分短结果犯了两个非常可笑的错误最后输出应该是(ans+mod)%mod因为我写的代码中间允许是负数乘法记得要取模
我又开小数组了
这都什么错误啊看来我适合抱灵我怎么不去入门组

「AGC038E」Gachapon
又是一个比较类似的东西但是这次概率不相同……
考虑min-max容斥
然后要对每一种所有物品出现小于\(b_i\)次的状态计算其出现的概率（包括初始时刻，这样就没有必要答案\(+1\)了）
设这种状态中\(i\)出现了\(x_i \in [0,b_i -1]\)次
令\(X=\sum x_i\) \(C=\sum A_i\) 概率是\(X!\prod_i\left(\frac{A_i}{C}\right)^{x_i}\frac{1}{x_i!}\)
dp时要考虑当前点是否要加入到容斥的集合当中去如果加入的话枚举\(x_i\)并要乘上\(-1\) 要记录\(X,C\) 类似生成函数那样转移
时间复杂度\(O((\sum B_i)^2\sum A_i)\)

#include
using namespace std;
#define fp(i,l,r) for(register int (i)=(l);(i)<=(r);++(i))
#define fd(i,l,r) for(register int (i)=(l);(i)>=(r);--(i))
#define fe(i,u) for(register int (i)=front[(u)];(i);(i)=e[(i)].next)
#define O(x) cerr<<#x<<':'<=10)wr(x/10);
	putchar('0'+x%10);
}
const int mod=998244353;
inline void rmod(int &x){x+=x>>31&mod;} 
inline void tmod(int &x){x%=mod;}
inline int qpow(int a,int b){
	int res=1;
	for(;b;b>>=1,tmod(a*=a))
	if(b&1)tmod(res*=a);
	return res;
}
inline int inv(int x){return qpow(x,mod-2);}
int g[405][405],tmp[405][405],n,a[405],b[405],fac[405],ifac[405];
main(){
	n=read();
	fp(i,1,n)a[i]=read(),b[i]=read()-1;
	g[0][0]=mod-1;
	fac[0]=1;fp(i,1,404)fac[i]=fac[i-1]*i%mod;
	ifac[404]=inv(fac[404]);fd(i,403,0)ifac[i]=ifac[i+1]*(i+1)%mod;
	int sa=0,sb=0;
	fp(i,1,n){
		fp(j,0,sa)fp(k,0,sb){
			int t=1;
			fp(l,0,b[i])
			tmod(tmp[j+a[i]][k+l]+=t*ifac[l]%mod*g[j][k]),t=t*a[i]%mod;
		} 
		sa+=a[i];sb+=b[i];
		fp(j,0,sa)fp(k,0,sb)
		rmod(g[j][k]-=tmp[j][k]),tmp[j][k]=0;
	}
	int ans=0;
	fp(i,1,sa){
		int t=inv(i),p=t*sa%mod;
		fp(j,0,sb)
		tmod(ans+=fac[j]*p%mod*g[i][j]),p=p*t%mod;
	}
	printf("%lld\n",ans);
	return 0;
}

「UR 19」通用评测号&&「集训队作业2018」喂鸽子 && 「AGC038E」Gachapon

相关

标签