ZJOI

ZJOI2019:1/?

ZJOI2018:0/?

ZJOI2017:3/6

ZJOI2016:2/?

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(1<l,r)=询问[l-1,r-1]$的异或和,正确当且仅当$now_{l-1}=now_r$;

设$al=l-1,ar=r$,分别统计覆盖的($bl \le al,ar \le br$)和单个在里面的($al<bl \le ar \le br或bl \le al \le ar<br$)的,其对于答案的贡献都是形如,记原本不同的概率为x,$x’ \leftarrow Ax+B$,可以用${A,B}$表示。该二元组与询问无关且满足交换律,相当于每次询问是个二维偏序求积

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

统计覆盖r的区间,即$bl \le r \le br$的数量,维护的是自己是0的概率,但完全可以和上面用同一套逻辑做而不用写另写代码。

因为不满足差分性,不能套树状数组,只能线段树套线段树,建议使用标记永久化,$O(nlog^2)$

「ZJOI2017」线段树

题解

「ZJOI2017」仙人掌

请先思考后再展开

很明显把环边去掉后就是各个独立的树,相当于在上面选偶数个点,配对后每条边最多被覆盖一次,且相邻两点不能配对

此时无脑地用分治NTT优化Dp就是$O(nlog^2)$,直接处理已经没什么空间了,我们需要想办法搞出点转化

核心转化:既然当前方案一定没有重边,给所有没被覆盖的边搞个重边上去方案唯一,于是等价于用若干条链覆盖每条边恰好一次

记$f_i=i条边选择性配对=f_{i-1}+(i-1)f_{i-2}$,$ans=\prod_x f_{deg_x}$,$O(n+m)$,code

ZJOI2016

「ZJOI2016」小星星

请先思考后再展开

首先注意到暴力做法复杂度为阶乘,而给出的是树形结构,很自然的想法是在上面状压dp

但这样搞半天,时间好像和暴力没啥区别……考虑我们状压的目的是保证一个编号不会被用多次

那这个东西用容斥也是可以解决的,设f为恰好g为至多且保证$g(S)=\sum_{T \subseteq S} f(T)$

二项式反演(准确的说是子集反演)可得$f(S)=\sum_{T \subseteq S} (-1)^{|S|-|T|} g(T)$,而对于每个$g(T)$是可以$O(n^3)$求的

code,跑得很快,毕竟常数很小

「ZJOI2016」线段树

请先思考后再展开

感叹人类的智慧,核心思想就是利用前缀和把多次复杂的变换变成多次简单的点积

考虑求$g(x,i)$表示最后位置i上的值不超过x的方案数,则$ans_i=mx*g(mx,i)-\sum_{j<mx} g(j,i)$

注意到这样的话,我们只需要关心不超过x的那若干个连续极长段(即$max(a_l..a_r) \le x,min(a_{l-1},a_{r+1})>x$)的变化,可以在这个基础上考虑dp,发现连续极长段只会缩小,所以是可以独立考虑的

枚举每个x,设$dp_{i,l,r}=第i次操作后,[l,r]是极长段的方案数$,初始化显然,$g(x,i)=\sum_{i \in [l,r]} dp_{q,l,r}$

$dp_{i,l,r}=dp_{i-1,l,r}*(C_{l-1}+C_{n-r}+C_{r-l+1})+dp_{i-1,a<l,r}(a-1)+dp_{i-1,l,b>r}(n-b)$,前缀和优化到单次$O(qn^2)$,至于X的范围本质不同的是$O(n)$个(而且数据保证随机的话有重复数字概率很小),总计$O(qn^3)$

既然x与转移无关,我们做x次不同初始化的dp并求和,等价于把初始化的结果求和再做一次dp,这样就变成$O(qn^2)$了

实现的时候设$a_0=a_{n+1}=MOD$会很方便,这样能统一用$dp_{0,l,r}=-(min(a_{l-1},a_{r+1})-max(a_l..a_r))$处理,code

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