ZJOI

ZJOI2019:1/?

ZJOI2018:0/?

ZJOI2017:1/?

ZJOI2019

「ZJOI2019」开关

题意:n个初始为0的变量,每次选中一个变量++,选中第i个变量的概率为$\frac{p_i}{P=\sum_{j=1}^n p_j}$,给出目标状态奇偶性$wt_i$,问首次达到的期望步数,$n \le 100,P\le 5e4$

请先思考后再展开

前置:$[i\%2=0]=\frac{(1)^i+(-1)^i}{2}$(简单的单位根反演)、概率生成函数

关于y的多项式在模$y^2$意义下可以手动实现加法、乘法、逆元($A*B=1,A_0B_0=1,A_0B_1+A_1B_0=0$,直接解)

方法一
$$
\\
设F(z)=奇偶性恰为wt的EGF=\prod_i \frac{e^{\frac{p_i}{P} z}+(-1)^{wt_i}e^{-\frac{p_i}{P}z}}{2},
f(z)为其OGF(即f[x^i]=i!F[x^i])
\\
设G(z)=恰为偶的EGF=\prod \frac{e^{\frac{p_i}{P}z}+e^{-\frac{p_i}{P}z}}{2},g(z)为其OGF;
设H(z)=第一次到达wt的EGF,h(z)为其OGF
\\
f=h*g,根据商法则ans=h’(1)=\frac{f’(1)g(1)-f(1)g’(1)}{g^2(1)},
设F(z)=\sum_{i=-P}^P a_i e^{\frac{i}{P} z},
G(z)=\sum_{i=-P}^P b_i e^{\frac{i}{P} z}
\\
显然e^{\frac{i}{P} z}对OGF的贡献为\frac{1}{1-\frac{i}{P}z},
则f(z)=\sum_{i=-P}^P \frac{a_i}{1-\frac{i}{P}z},
此时不能直接带入z=1,然后我就自闭了
\\
让我们回到[f(z)*\prod_{i=-P}^P (1-\frac{i}{P}z)]=h(z)*[g(z)\prod_{i=-P}^P (1-\frac{i}{P}z)],
问题就™这样轻松地解决了
\\
f_2(z)=\sum_{i=-P}^P a_i \prod_{j \ne i} (1-\frac{j}{P}z) ,
f_2(1)=a_P \prod_{i \ne P} (1-\frac{i}{P}),g_2同理
\\
积法则可归纳证[\prod_i T_i(x)]’=\sum T_i’(x) \prod _{j \ne i} T_i(x),故
f_2’(z)=-\sum_i \sum_{j \ne i} a_i \frac{j}{P} \prod_{k \ne i,k \ne j} (1-\frac{k}{P}z)
\\
注意到i或j必须有一个是P,
f_2’(1)=\sum_{j \ne P} \frac{j*a_P*(2P)!}{P^{2P}(P-j)}+\sum_{i \ne P} \frac{a_i*(2P)!}{P^{2P-1}*(P-i)}
$$

做法复杂度取决于求系数,直接背包是$O(nP)$,分治ntt是$O(Plog^2P)$、ln后求和再exp还原是$O(PlogP)$,code

方法二:感谢gzy解答疑惑;拓展性较好——可以处理按第i个位置的代价为ai,然后求代价的期望

统计每种状态(长为n的次数序列s)作为首次的概率,求排列方案数考虑容斥有m个前缀非法
$$
\sum_{序列s,2|s_i-wt_i}
(\prod (\frac{p_i}{P})^{s_i})
(\sum_{i=1}^n s_i)
\sum_{序列k} {(\sum_{i=1}^n k_i)! \over \prod_{i=1}^n k_i!}
\sum_{m=0}^{\infty} (-1)^m
\sum_{m个序列u,2|u_{ij}}
[\forall i,k_i+\sum_{t=1}^m u_{ti}=s_i]
\prod_{i=1}^m {(\sum_{j=1}^n u_{ij})! \over \prod_{j=1}^n u_{ij}!}
\\
非常巧妙的处理带权方案数的方法是放到模y^2意义下,
\sum s_i=[y^1]\prod_{i=1}^n (1+s_iy)=
[y^1]\prod_{i=1}^n [ (1+k_iy)\prod_{t=1}^{m}(1+u_{ti}y) ]
\\
同做法一,
F(z)=2^{-n}* \prod_i ( e^{\frac{p_i}{P}z}+(-1)^{wt_i}e^{-\frac{p_i}{P}z}+(e^{\frac{p_i}{P}z})’zy+(-1)^{wt_i}(e^{-\frac{p_i}{P}z})’zy),f(z)为其OGF
\\
设F(z)=\sum_{i=-P}^P A_ie^{\frac{i}{P}z}+B_ie^{\frac{i}{P}z}yz,f(z)=f_0(z)+f_1(z)y
\\
则f_0(z)=\sum_{i=-P}^P \frac{A_i}{1-\frac{i}{P}z},
f_1(z)=\sum_{i=-P}^P \frac{B_iz}{(1-\frac{i}{P}z)^2}即C_{i+1}^1的生成函数
\\
G(z)=2^{-n}* \prod_i ( e^{\frac{p_i}{P}z}+e^{-\frac{p_i}{P}z}+(e^{\frac{p_i}{P}z})’zy+(e^{-\frac{p_i}{P}z})’zy),设g_0中系数为C_i,设g_1中系数为D_i
\\
ans=\lim_{z \to 1} [y^1]f(z)\sum_{m=0}^{\infty}(-1)^m(g(z)-1)^m=\lim_{z \to 1} [y^1] \frac{f(z)}{g(z)},这里-1是避免\sum_{j=1}^n u_{tj}=0
\\
手动求多项式逆元得\lim_{z \to 1} \frac{f_1(z)g_0(z)-f_0(z)g_1(z)}{g_0^2(z)},注意到A_P=C_P,B_P=D_P,故分子中\frac{1}{(1-z)^3}的系数为0
$$

低阶除高阶无穷大为0,故只计算二阶无穷大,上下除二阶无穷大$\frac{1}{(1-z)^2}$,则$ans=\frac{D_p\sum \frac{A_i}{1-\frac{i}{P}}-B_p\sum \frac{C_i}{1-\frac{i}{P}}}{C_p^2}$,code

另外有个魔鬼似乎使用FWT那套理论人工推导了高斯消元的结果

ZJOI2017

「ZJOI2017」树状数组

请先思考后再展开

由人类智慧可知,这东西是在维护后缀和

$query(l,r)=询问[l-1,r-1]$的异或和,正确当且仅当$now_{l-1}=now_r$

这部分的话设某线段内包含l-1和r这两点中in个点,则$same’=\frac{1}{ln}*(same*(ln-in)+in)$

$query(1,r)=询问[r,n]的异或和$,正确当且仅当$now_r=当前修改次数奇偶性$

维护$a_i=恰为i的概率,a’_i=(1-2/ln)*a_i+\frac{1}{ln}$

可以写个二维线段树维护上述内容,尽管那个式子看上去是要按顺序算的,但理性分析操作的先后不应该有影响

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/80189232.html
转载请注明出处,谢谢!