24pht春5

admin2024-05-15  0

pht春5

A

相当于规定了每一位的操作次数的奇偶性。

随便排序显然不影响。

因此有 f i = f i − 1 × i n + f i + 1 × n − i n f_i=f_{i-1}\times \dfrac i n+f_{i+1}\times \dfrac{n-i}n fi=fi1×ni+fi+1×nni,是个经典问题,差分一下?


f i f_i fi 表示当前 i i i 个正面到 n n n 个操作次数的期望。

递推边界 f n = 0 f_n=0 fn=0

f i = i n f i − 1 + n − i n f i + 1 f_i=\dfrac i n f_{i-1}+\dfrac{n-i}nf_{i+1} fi=nifi1+nnifi+1

又有向上,又有向下。

但是 f 0 = 1 + f 1 f_0=1+f_1 f0=1+f1。此类问题解法:待定系数法。

f i = a i f 0 + b i f_i=a_if_0+b_i fi=aif0+bi

a i f 0 + b i = i n ( a i − 1 f 0 + b i − 1 ) + n − i n ( a i + 1 f 0 + b i + 1 ) a_if_0+b_i=\dfrac i n (a_{i-1}f_0+b_{i-1})+\dfrac{n-i}n(a_{i+1}f_0+b_{i+1}) aif0+bi=ni(ai1f0+bi1)+nni(ai+1f0+bi+1)

然后可以推出 a , b a,b a,b 分别的转移式。

a 1 , b 1 a_1,b_1 a1,b1 是什么事易求的。

f n = a n f 0 + b n f_n=a_nf_0+b_n fn=anf0+bn 可以反求 f 0 f_0 f0

然后由 f i = a i f 0 + b i f_i=a_if_0+b_i fi=aif0+bi 可以反求 f i f_i fi


更简单的做法:

d i d_i di 表示首次从有 i i i 个相同到 i + 1 i+1 i+1 个相同的期望次数(也就是差分法)

d i = 1 + i n × 0 + n − i n ( d i − 1 + d i ) d_i=1+\frac i n \times 0+\frac{n-i}n(d_{i-1}+d_i) di=1+ni×0+nni(di1+di)

那么 f i = ∑ j ≥ i d j f_i=\sum_{j\ge i}d_j fi=jidj

就可以从小往大推 d i d_i di,再从大往小推 f i f_i fi,就做完了。

B

一道题测出我极低的概率期望水平。

盲测了个结论,然后自己也不知道为什么,因为过了样例交就过了。

大概就是先算出当前末尾期望长度 f f f。然后正常应该是要加 2 f − 1 2f-1 2f1 的期望,但是事实证明加 2 f − p 2f-p 2fp 才能过,非常神奇,我也不知道为什么,可能是因为本身就要乘个 p p p,然后我在 f f f 那里已经乘了,那么这里就需要给1单独乘。

你看,如果不计这一位,就相当于加 p × ( 2 f + 1 ) p\times(2f+1) p×(2f+1),那就解释得通了。


考虑第 i i i 个位置对答案的贡献 d i d_i di(增量贡献)。

求出第 i i i 个的期望长度是 f i f_i fi

对于 f i f_i fi

f i = ( 1 − p i ) × 0 + p i × ( f i − 1 + 1 ) f_i=(1-p_i)\times 0 + p_i\times (f_{i-1}+1) fi=(1pi)×0+pi×(fi1+1)

d i = [ f i ] 2 − [ f i − 1 ] 2 d_i=[f_i]^2-[f_{i-1}]^2 di=[fi]2[fi1]2

但是算期望不能直接丢进去算平方会出问题。

考虑 [ f i ] 2 = ( 1 − p i ) × 0 + p i × ( f i − 1 + 1 ) = p i × [ f i − 1 ] 2 + 2 p i f i − 1 + p i [f_i]^2=(1-p_i)\times 0+ p_i\times (f_{i-1}+1)=p_i\times [f_{i-1}]^2+2p_if_{i-1}+p_i [fi]2=(1pi)×0+pi×(fi1+1)=pi×[fi1]2+2pifi1+pi

期望乘数是没问题的,但是期望乘期望有问题。

定义 g i g_i gi 表示长度的期望的平方。

g i = p i g i 1 2 + 2 p i f i − 1 + p i g_i=p_i g_{i_1}^2+2p_if_{i-1}+p_i gi=pigi12+2pifi1+pi

后面那个就是 2 p i f i − 1 + p i 2p_if_{i-1}+p_i 2pifi1+pi 增量部分。

答案为 ∑ ( 2 p i f i − 1 + p i ) \sum(2p_if_{i-1}+p_i) (2pifi1+pi)

这个和之前推出来的一样

C

为什么我按照上题打就不行呢?不就是2次变成3次吗?


不知道为什么错?

直接上转移:

f i = ( 1 − p ) × f i − 1 + ∑ j ( f j − 1 + ( i − j ) 3 ) s i s j ( 1 − p j ) f_i=(1-p)\times f_{i-1}+\sum_j(f_{j-1}+(i-j)^3)\dfrac{s_i}{s_j}(1-p_j) fi=(1p)×fi1+j(fj1+(ij)3)sjsi(1pj)

然后拆开成每一项分别计算贡献。

还有去讨论恶心的 p = 0 p=0 p=0 的情况。

然后WA了,我也不知道为什么。

下次还是先看完所有题思考完再去打吧。之前那个策略对我来说还是有用的。


一样的。平方变成三次方。

f i = p i × ( f i − 1 + 1 ) f_i=p_i\times (f_{i-1}+1) fi=pi×(fi1+1)

g i = p i × ( g i − 1 + 2 f i + 1 ) g_i=p_i\times (g_{i-1}+2f_i+1) gi=pi×(gi1+2fi+1)

( x + 1 ) 3 = x 3 + 2 x 2 + 2 x + 1 (x+1)^3=x^3+2x^2+2x+1 (x+1)3=x3+2x2+2x+1 得 :

h i = p i × ( h i − 1 + 3 g i − 1 + 3 f i − 1 + 1 ) h_i=p_i\times (h_{i-1}+3g_{i-1}+3f_{i-1}+1) hi=pi×(hi1+3gi1+3fi1+1)

发现后面那坨才是增量。

所以答案就是 ∑ p i ( 3 g i − 1 + 3 f i − 1 + 1 ) \sum p_i(3g_{i-1}+3f_{i-1}+1) pi(3gi1+3fi1+1)

本质是因为期望不能数乘,只能期望和概率在一起。

D

好像直接上图了,然后还是那个经典平方问题。

但我现在C也没搞出来,就不想思考了


由线性图变成任意图了。

f i , j , k f_{i,j,k} fi,j,k 表示现在在 i i i 号点,有 j j j 的等级,走了 k k k 步的期望代价。

在这类模型里, j j j 是可以不要的。

新状态: f i , k f_{i,k} fi,k 现在在 i i i 号点,走了 k k k 步的期望(Level期望 + Level^2的期望+概率)。

  • P k ( u ) P_k(u) Pk(u) 落在 u u u 的概率
  • L k ( u ) L_k(u) Lk(u) Level期望
  • E k ( u ) E_k(u) Ek(u) Level^2的期望

对于 u → v u\to v uv,都可以去转移,概率是 1 c u \dfrac 1 {c_u} cu1,这个记为 c u c_u cu 的概率。

P k ( u ) × 1 c u → P k + 1 ( v ) P_k(u)\times \dfrac 1 {c_u}\to P_{k+1}(v) Pk(u)×cu1Pk+1(v)

下一步取决于 C v C_v Cv

  1. p ( L k ( u ) + P k ( u ) ) → L k + 1 ( v ) p(L_k(u)+P_k(u))\to L_{k+1}(v) p(Lk(u)+Pk(u))Lk+1(v)

  2. p ( L k ( u ) + 2 L k ( u ) P k ( u ) + P k 2 ( u ) ) → E k + 1 ( v ) p(L_k(u)+2L_k(u)P_k(u)+P_k^2(u))\to E_{k+1}(v) p(Lk(u)+2Lk(u)Pk(u)+Pk2(u))Ek+1(v)

对于另一种情况:

p L k ( u ) → L k + 1 ( v ) pL_k(u)\to L_{k+1}(v) pLk(u)Lk+1(v)

然后还要 a n s + = c u E k ( u ) ans+=c_uE_k(u) ans+=cuEk(u)

此题和上题区别在于每个节点不是必然到达,所以需要记录多一维表示概率。


不知道为什么这么一道小丑题我调这么久。

E

原题,忘记当时做法了。到时候pht讲的时候直接记一次笔记来理解算了


假如从期望dp应该从手里有多少个饼干来刻画。

我们先把 a a a 弄出来,然后 ∑ a = M \sum a = M a=M。任何一个多重集合在变化过程中都可能出现。

f ( A ) = 1 + ∑ a i m ∑ 1 n − 1 f ( A ′ ) f(A)=1+\sum\dfrac {a_i} m \sum \dfrac 1 {n-1} f(A') f(A)=1+main11f(A)

显然没法直接用动态规划来解决。

考虑技巧,把 A = { a 1 , a 2 , … , a n } A=\{a_1,a_2,\dots,a_n\} A={a1,a2,,an}

希望存在这么一个函数 f ( A ) = ∑ g ( a i ) f(A)=\sum g(a_i) f(A)=g(ai) ,每个之和自己有关

∑ g ( a i ) = 1 + ∑ a i m ∑ j ≠ i 1 n − 1 ( ∑ k ≠ i , k ≠ j g ( a k ) + g ( a j + 1 ) + g ( a i − 1 ) ) \sum g(a_i)=1+\sum \frac {a_i} m\sum_{j\ne i}\frac 1 {n-1}(\sum _{k\ne i,k\ne j}g(a_k)+g(a_j+1)+g(a_i-1)) g(ai)=1+maij=in11(k=i,k=jg(ak)+g(aj+1)+g(ai1))

相当于枚举 i → j i\to j ij。其他人 k k k 不变。上面这个等式。

然后用A题中类似的待定系数法。

∑ a i a i m ( g ( a i ) − g ( a i − 1 ) ) + ∑ m − a i m × 1 n − 1 ( g ( a i ) − g ( a i + 1 ) ) = 1 \sum_{a_i} \dfrac {a_i} m(g(a_i)-g(a_i-1))+\sum \dfrac {m-a_i}m\times \dfrac 1 {n-1}(g(a_i)-g(a_i+1))=1 aimai(g(ai)g(ai1))+mmai×n11(g(ai)g(ai+1))=1

上面的式子就是假如 i i i 参与交换事件得到的等式(也可以看做上面那个式子的移项?)

为什么我感觉直接上差分法就行了?

∑ a i a i m ( ( g ( a i ) − g ( a i − 1 ) ) + m − a i a i × 1 n − 1 ( g ( a i ) − g ( a i + 1 ) ) ) = 1 \sum_{a_i} \dfrac {a_i} m((g(a_i)-g(a_i-1))+\dfrac {m-a_i}{a_i}\times \dfrac 1 {n-1}(g(a_i)-g(a_i+1)))=1 aimai((g(ai)g(ai1))+aimai×n11(g(ai)g(ai+1)))=1

一个合法解显然是: ( g ( a i ) − g ( a i − 1 ) ) + m − a i a i × 1 n − 1 ( g ( a i ) − g ( a i + 1 ) ) = 1 (g(a_i)-g(a_i-1))+\dfrac {m-a_i}{a_i}\times \dfrac 1 {n-1}(g(a_i)-g(a_i+1))=1 (g(ai)g(ai1))+aimai×n11(g(ai)g(ai+1))=1

增量法来做 d i d_i di

对于初始值直接代入 d 1 = 0 d_1=0 d1=0 就行。( d 1 d_1 d1 可以任取,会得不同 g g g,但最后得出来是相同的)

F

因为和E题放在一起,而且感觉和E题挺像的。

假如我们钦定某种颜色为结束,那么只和当前球数量、总数量有关。

而一种球只要不消亡肯定是能走到终点的?


球的总数不变。

f ( A ) − ∑ f ( A ′ ) = 1 f(A)-\sum f(A')=1 f(A)f(A)=1

= ∑ a i m × m − a i m − 1 ( g ( a i ) − g ( a i + 1 ) ) + m − a i m × a i m − 1 ( g ( a i ) − g ( a i − 1 ) ) =\sum \frac {a_i}m\times \frac{m-a_i}{m-1}(g(a_i)-g(a_i+1))+\frac {m-a_i}m\times \frac {a_i}{m-1}(g(a_i)-g(a_i-1)) =mai×m1mai(g(ai)g(ai+1))+mmai×m1ai(g(ai)g(ai1))

= ∑ a i m × m − a i m − 1 ( 2 g ( a i ) − g ( a i + 1 ) − g ( a i − 1 ) ) = 1 =\sum \frac{a_i}m\times \frac{m-a_i}{m-1}(2g(a_i)-g(a_i+1)-g(a_i-1))=1 =mai×m1mai(2g(ai)g(ai+1)g(ai1))=1

类比上题可得:

m − a i m − 1 ( 2 g ( a i ) − g ( a i + 1 ) − g ( a i − 1 ) ) = 1 \frac{m-a_i}{m-1}(2g(a_i)-g(a_i+1)-g(a_i-1))=1 m1mai(2g(ai)g(ai+1)g(ai1))=1

即:

m − a i m − 1 ( d ( x + 1 ) − d ( x ) ) = m − 1 m − a i \frac {m-a_i}{m-1}(d(x+1)-d(x))=\frac {m-1}{m-a_i} m1mai(d(x+1)d(x))=maim1

直接令 d 1 = 0 d_1=0 d1=0 可以得到合法 g x g_x gx

打表有 g ( M ) = − n 2 g(M)=-n^2 g(M)=n2,小的 g g g 可以线性求。

a n s = ∑ g ( a i ) − g ( M ) ans=\sum g(a_i)-g(M) ans=g(ai)g(M)


我看的那份题解挺好懂的,我尝试复述一下解题过程

f i f_i fi 表示当前有 i i i 个赢的期望步数, s s s 表示总球数。

p p p 表示第一步抽到这个球,第二步不抽到这个球的概率(反过来是一样的),则有 p = i ( s − i ) s ( s − 1 ) p=\frac{i(s-i)}{s(s-1)} p=s(s1)i(si)

然后显然有 f i = p f i + 1 + p f i − 1 + f i ( 1 − 2 p ) + v f_i=pf_{i+1}+pf_{i-1}+f_i(1-2p)+v fi=pfi+1+pfi1+fi(12p)+v,其中 v v v 表示当前赢的概率。因为我们需要操作一次,而期望为次数乘上概率,概率即为 v v v

v v v 的计算如下,设 g i = v g_i=v gi=v, 则:

  • g 0 = 0 , g s = 1 g_0=0,g_s=1 g0=0,gs=1
  • g i = p g i + 1 + p g i − 1 + ( 1 − 2 p ) g i g_i=pg_{i+1}+pg_{i-1}+(1-2p)g_i gi=pgi+1+pgi1+(12p)gi
  • 移项可得: g i − g i − 1 = g i + 1 − g i g_i-g_{i-1}=g_{i+1}-g_i gigi1=gi+1gi
  • 联立1式可得 g i = i s g_i=\frac i s gi=si

我们现在有 f i = p f i + 1 + p f i − 1 + f i ( 1 − 2 p ) + i s f_i=pf_{i+1}+pf_{i-1}+f_i(1-2p)+\frac i s fi=pfi+1+pfi1+fi(12p)+si,化为同构式:

f i − f i − 1 = f i + 1 − f i + s − 1 s − i f_i-f_{i-1}=f_{i+1}-f_i+\dfrac{s-1}{s-i} fifi1=fi+1fi+sis1

因为 f 0 f_0 f0 不存在,可得 f 2 = 2 f 1 − 1 f_2=2f_1-1 f2=2f11

因为 f s = 0 f_s=0 fs=0,我们有

f 1 = f 1 − f s = − ∑ i = 2 s ( f i − f i − 1 ) = ( s − 1 ) ( f 1 − f 2 ) + ∑ i = 2 s − 1 s − 1 s − i ( s − i ) = ( s − 1 ) ( f 1 − f 2 ) + ( s − 2 ) ( s − 1 ) f_1=f_1-f_s=-\sum_{i=2}^s(f_i-f_{i-1})=(s-1)(f_1-f_2)+\sum_{i=2}^{s-1}\frac{s-1}{s-i}(s-i)=(s-1)(f_1-f_2)+(s-2)(s-1) f1=f1fs=i=2s(fifi1)=(s1)(f1f2)+i=2s1sis1(si)=(s1)(f1f2)+(s2)(s1)

代入 f 2 = 2 f 1 − 1 f_2=2f_1-1 f2=2f11 可得:

f 1 = ( s − 1 ) 2 s f_1=\frac{(s-1)^2}{s} f1=s(s1)2

此时 f 1 , f 2 f_1,f_2 f1,f2 已知,可递推出 f i f_i fi。答案即为 ∑ f a i \sum f_{a_i} fai

G

大致意思就是,每天等概率一个 a i − 1 a_i-1 ai1。然后二分之一的概率生成一个新1,二分之一的概率按人数比例使一个 a i + 1 a_i+1 ai+1


如果没有第一个事件那么和前面那题几乎一样。

考虑 f ( A ) − f ( A ′ ) f(A)-f(A') f(A)f(A) 每一个 a i a_i ai 如何参与事件。

∑ 1 2 ( g ( a i ) − g ( a i − 1 ) − g ( 1 ) ) a i m ( + 1 2 ( g ( a i ) − g ( a i − 1 ) − ) ) \sum\frac 1 2(g(a_i)-g(a_i-1)-g(1))\frac{a_i}m(+\frac 1 2(g(a_i)-g(a_i-1)-)) 21(g(ai)g(ai1)g(1))mai(+21(g(ai)g(ai1)))

式子好乱,不想打了。大致就是要分讨首先被选的情况,然后是不被选的但有人加入的情况。

1 2 g 1 + ∑ \frac 1 2g_1+\sum 21g1+

然后套路化一轮, d 1 d_1 d1 随便代,就可以解出所有 d d d,解出所有 g g g

但是此题 d 1 d_1 d1 不能随便带,只能令 d 1 = − 2 d_1=-2 d1=2。因为 1 + 1 2 d 1 1+\frac 1 2 d_1 1+21d1,那样子就可以去到 d 1 d_1 d1 的影响???????

考场是因为打表得?


比较厉害的一题,需要非常大胆。下面写的东西有些latex懒得打直接复制洛谷题解区的。

构造势能函数,根据常见结论, f ( 0 ) = 0 f(0)=0 f(0)=0,答案为 ∑ f ( a i ) − f ( n ) \sum f(a_i)-f(n) f(ai)f(n)

考虑三种可能的转移情况:

  • 自己新建一个 : ϕ ( A t + 1 ) = ϕ ( A t ) − f ( a x ) + f ( a x − 1 ) + f ( 1 ) \phi(A_{t + 1}) = \phi(A_t) - f(a_x) + f(a_x - 1) + f(1) ϕ(At+1)=ϕ(At)f(ax)+f(ax1)+f(1)
  • 回到原来组: ϕ ( A t + 1 ) = ϕ ( A t ) \phi(A_{t + 1}) = \phi(A_t) ϕ(At+1)=ϕ(At)
  • 去到另一个组: ϕ ( A t + 1 ) = ϕ ( A t ) − f ( a x ) + f ( a x − 1 ) − f ( a y ) + f ( a y + 1 ) \phi(A_{t + 1}) = \phi(A_t) - f(a_x) + f(a_x - 1) - f(a_y) + f(a_y + 1) ϕ(At+1)=ϕ(At)f(ax)+f(ax1)f(ay)+f(ay+1)

转移到下一步需要-1的期望步数,把上述根据概率汇总可得:

− 1 = ∑ i = 1 m a i n ⋅ 1 2 ( − f ( a i ) + f ( a i − 1 ) + f ( 1 ) + ∑ j = 1 m [ i ≠ j ] a j n ( − f ( a i ) + f ( a i − 1 ) − f ( a j ) + f ( a j + 1 ) ) ) -1=\sum _{i = 1} ^m \dfrac {a_i} n \cdot \dfrac 1 2 \left(- f(a_i) + f(a_i - 1) + f(1) + \sum _{j = 1}^m [i\neq j] \dfrac {a_j} n \left( - f(a_i) + f(a_i-1) - f(a_j) + f(a_j+1)\right)\right) 1=i=1mnai21(f(ai)+f(ai1)+f(1)+j=1m[i=j]naj(f(ai)+f(ai1)f(aj)+f(aj+1)))

整理得:

f ( 1 ) + 2 + ∑ i a i n 2 ( − ( 3 n − 2 a i ) f ( a i ) + ( 2 n − a i ) f ( a i − 1 ) + ( n − a i ) f ( a i + 1 ) ) = 0 f(1) + 2 + \sum_i \dfrac{a_i}{n^2} (-(3n-2a_i)f(a_i)+(2n-a_i)f(a_i-1)+(n-a_i)f(a_i + 1)) = 0 f(1)+2+in2ai((3n2ai)f(ai)+(2nai)f(ai1)+(nai)f(ai+1))=0

为了消掉常数项,我们令 f ( 1 ) = − 2 f(1)=-2 f(1)=2 (也可以用pht打表做法)

再次整理的:

f ( x + 1 ) = 3 n − 2 x n − x f ( x ) − 2 n − x n − x f ( x − 1 ) f(x+1)=\dfrac{3n-2x}{n-x}f(x)-\dfrac{2n-x}{n-x}f(x-1) f(x+1)=nx3n2xf(x)nx2nxf(x1)

此时我们已经得到前两项 f f f 及其递推公式了,但是 ∑ a i ≤ 4 × 1 0 8 \sum a_i\le 4\times 10^8 ai4×108,我们要把 log ⁡ \log log 取得,直接采用分数表示:

f ( x + 1 ) = 3 n − 2 x n − x × d 1 d 2 − 2 n − x n − x × s 1 s 2 f(x+1)=\dfrac{3n-2x}{n-x}\times \dfrac{d_1}{d_2}-\dfrac{2n-x}{n-x}\times\dfrac{s_1}{s_2} f(x+1)=nx3n2x×d2d1nx2nx×s2s1

整理得:

f ( x + 1 ) = ( 3 n − 2 x ) d 1 s 2 − ( 2 n − x ) s 1 d 2 ( n − x ) d 2 s 2 f(x+1)=\dfrac{(3n-2x)d_1s_2-(2n-x)s_1d_2}{(n-x)d_2s_2} f(x+1)=(nx)d2s2(3n2x)d1s2(2nx)s1d2

H

先梳理一下题意。

每次等概率选取两个集合的代表人,把一个加入到另一个集合里,把原先集合解散。由于人之间没有区别,相当于是对于 a , b a,b a,b,变成 a − 1 a-1 a1 1 1 1 和1个 b + 1 b+1 b+1。每个集合都是等概率被选取的。


还是套路的:

f ( A ) − ∑ f ( A ′ ) f(A)-\sum f(A') f(A)f(A)

f ( A ) = { ∑ 1 c ( 当前集合大小 ) ( g ( a i ) − ( a i − 1 ) g 1 ) 1 c ( g ( a i ) − g ( a i + 1 ) ) = 1 f(A) = \begin{cases} \sum \frac 1 {c(\text{当前集合大小})}(g(a_i)-(a_i-1)g_1) \ \frac 1 c (g(a_i)-g(a_i+1)) \end{cases}=1 f(A)={c(当前集合大小)1(g(ai)(ai1)g1)c1(g(ai)g(ai+1))=1

( g ( a i ) − ( a i − 1 ) g 1 ) + ( g ( a i ) − g ( a i + 1 ) ) = 1 (g(a_i)-(a_i-1)g_1)+(g(a_i)-g(a_i+1))=1 (g(ai)(ai1)g1)+(g(ai)g(ai+1))=1 即可。令 g 1 = g_1= g1= 什么都行。

然后不知道在凑什么。


看了题解势能函数的做法,感觉势能函数真得是一个很巧妙的东西。

势能函数并没有任何实际意义,他只是一个符合一些性质而构造出来的特殊函数,而利用这个函数的一些性质我们能拿来处理一些事情。

在停时问题中,我们要求期望停止的步数,对于一个状态 f ( S ) f(S) f(S),只需要满足以下性质就是一个好的 f f f

  1. f ( E n d ) f(End) f(End) 无后继节点
  2. E ( f ( n x t S ) − f ( S ) ) = 1 E(f(nxt_S)-f(S))=1 E(f(nxtS)f(S))=1,也就是每走一步期望步数能加1。

因此 f f f 是不唯一的。

首先 S S S 的状态太大,我们可以先提一些关键信息提炼出来,比如 f ( x ) f(x) f(x) 表示有 x x x 个附属节点。

根据定义,答案即为 f ( n − 1 ) − ∑ f ( a i ) f(n-1)-\sum f(a_i) f(n1)f(ai)

考虑构造 f f f,第一个条件显然满足,第二个条件我们可以这么表示,考虑现在选的两个点分别有 u , v u,v u,v 个附属节点,则有:

f ( u ) + f ( v ) + 1 = 1 2 ( f ( u + 1 ) + v f ( 0 ) ) + 1 2 ( f ( v + 1 ) + u ( f 0 ) ) f(u)+f(v)+1=\frac 1 2(f(u+1)+vf(0))+\frac 1 2(f(v+1)+u(f0)) f(u)+f(v)+1=21(f(u+1)+vf(0))+21(f(v+1)+u(f0))

常见trick,设 f ( 0 ) = 0 f(0)=0 f(0)=0

f ( u ) + f ( v ) + 1 = 1 2 ( f ( u + 1 ) + f ( v + 1 ) ) f(u)+f(v)+1=\frac 1 2 (f(u +1)+f(v+ 1)) f(u)+f(v)+1=21(f(u+1)+f(v+1))

根据同构思想,一种合法的 f f f 为:

f ( u ) + 1 2 = 1 2 f ( u + 1 ) f(u)+\frac 1 2=\frac 1 2f(u + 1) f(u)+21=21f(u+1)

整理得 :

f ( u + 1 ) = 2 f ( u ) + 1 f(u +1)=2f(u)+1 f(u+1)=2f(u)+1

直接可得通项公式: f ( n ) = 2 n − 1 f(n)=2^n-1 f(n)=2n1

I

题意很简洁,但我依然没思路,希望今天不要来多项式。毕竟3e5还是有点慌的。不过1e9+7感觉问题不大。


环长是1e9。只有差距有意义,而且加起来才有用。

f ( A ) − f ( A ′ ) = { ∑ k n × 1 k ( g ( a i ) − g ( a i − 1 ) ) + k n 1 k ( g ( a i ) − g ( a i − 1 ) = 1 f(A)-f(A')= \begin{cases} \sum \frac k n \times \frac 1 k(g(a_i)-g(a_i-1)) \ +\frac k n \frac 1 k(g(a_i)-g(a_i-1) \end{cases}=1 f(A)f(A)={nk×k1(g(ai)g(ai1))+nkk1(g(ai)g(ai1)=1

理论上会猜 g ( a i ) − g ( a i − 1 ) + g ( a i ) − g ( a i + 1 ) = 1 g(a_i)-g(a_i-1)+g(a_i)-g(a_i+1)=1 g(ai)g(ai1)+g(ai)g(ai+1)=1,但是 k k k 有影响。

因为我们之前外面有 a i m \frac {a_i}m mai,且他们的和为 1 1 1,但现在不是。

g ( x ) − g ( x − 1 ) + g ( x ) − g ( x + 1 ) = n x m g(x)-g(x-1)+g(x)-g(x+1)=\frac {nx}m g(x)g(x1)+g(x)g(x+1)=mnx

d ( x ) − d ( x + 1 ) = n x m d(x)-d(x+1)=\frac {nx}m d(x)d(x+1)=mnx,正常代入 d 0 d_0 d0 就行。

但此题要求 ∑ M g ( 1 ) \sum^Mg(1) Mg(1).

因为差分是等差数列,所以 d d d 是等差数列求和的结果。因此 d d d 是个二次函数,然后也能打出 g g g


还是停时。

少掉的球可以用 f ( 0 ) = 0 f(0)=0 f(0)=0 解决。

每个状态的势能是 ∑ f ( d i ) \sum f(d_i) f(di),答案就是 ∑ f ( d i ) − f ( m ) \sum f(d_i)-f(m) f(di)f(m)

考虑操作一步的影响:

∑ i = 1 k f ( d i ) = 1 + 1 n ∑ i = 1 k ( f ( d i + 1 ) + f ( d i + 1 − 1 ) + ∑ j = 1 , j ≠ i , j ≠ i + 1 k f ( d j ) ) \sum_{i=1}^{k} f(d_i)=1+\frac{1}{n}\sum_{i=1}^k (f(d_i+1)+f(d_{i+1}-1 )+\sum_{j=1,j\neq i,j\neq i+1}^k f(d_j)) i=1kf(di)=1+n1i=1k(f(di+1)+f(di+11)+j=1,j=i,j=i+1kf(dj))

化简并构造同构:

( ∑ i = 1 k f ( d i ) − ∑ i = 1 k f ( d i − 1 ) ) = n + ( ∑ i = 1 k f ( d i + 1 ) − ∑ i = 1 k f ( d i ) ) \left(\sum_{i=1}^{k} f(d_i)-\sum_{i=1}^k f(d_i-1)\right)=n+ \left(\sum_{i=1}^k f(d_i+1)-\sum_{i=1}^{k} f(d_i)\right) (i=1kf(di)i=1kf(di1))=n+(i=1kf(di+1)i=1kf(di))

换元 g ( x ) = f ( x ) − f ( x − 1 ) g(x)=f(x)-f(x-1) g(x)=f(x)f(x1)

∑ i = 1 k g ( d i ) = n + ∑ i = 1 k g ( d i + 1 ) \sum_{i=1}^{k} g(d_i)=n+\sum_{i=1}^k g(d_i+1) i=1kg(di)=n+i=1kg(di+1)

继续换 h ( x ) = g ( x + 1 ) − g ( x ) h(x)=g(x+1)-g(x) h(x)=g(x+1)g(x) (其实可以一次到位,但是不方便我们逆推):

− n = ∑ i = 1 k h ( d i ) -n=\sum_{i=1}^{k} h(d_i) n=i=1kh(di)

由于 ∑ d i = m \sum d_i=m di=m,我们可以构造一种合法的 h ( x ) h(x) h(x) 满足:

h ( x ) = − n x m h(x)=-\frac{nx}{m} h(x)=mnx

等差数列求和可逆推 g g g

g ( x ) = − n x ( x − 1 ) 2 m g(x)=-\frac{nx(x-1)}{2m} g(x)=2mnx(x1)

为了方便逆推 f f f,我们改变一下 g g g 的形式:

g ( x ) = − n m ( x + 1 2 ) g(x) = -\frac{n}{m} \binom{x + 1}{2} g(x)=mn(2x+1)

经典杨辉三角按列求和问题:

f ( x ) = − n m ( x + 1 3 ) f(x) = -\frac{n}{m} \binom{x + 1}{3} f(x)=mn(3x+1)

J

初三下讲过,但我当时没打,现在忘了。


不能用停时的原因,因为 a i a_i ai 的状态总数太多了。因为球是不对称的。


我看的那份题解有点复杂,我看我能不能自己重新写一遍,毕竟我只是对着题解代码打了一遍而已

考虑当前所有值离 A A A 的最大为 i i i,我们是可以直接记做 f i f_i fi 的。这个很巧妙,因为理论上一个最大差值可以对应很多种情况,但现在直接归一了。为了证明其可行,我们只需要用转移方程说明即可。

我们找一个最大的 r r r 满足 a r < i a_r<i ar<i,显然对于一个 i i i 这个 r r r 只有一个。

f i = 1 n ( r f i − 1 + ∑ j > r f a j ) + 1 f_i=\frac 1 n(rf_{i-1}+\sum_{j>r}f_{a_j})+1 fi=n1(rfi1+j>rfaj)+1

其实就是考虑下一步我按到哪,按到前面最大值-1,按到后面清0就成为新的最大差值。

现在方程式是从两个方向转移,移一下项可得:

f i − 1 = 1 r ( n ( f i − 1 ) − ∑ j > r f a j ) f_{i-1}=\frac 1 r(n(f_i-1)-\sum_{j>r}f_{a_j}) fi1=r1(n(fi1)j>rfaj)

我们的边界是 f 0 = 0 f_0=0 f0=0,我们要求 f a N f_{a_N} faN,但这个dp是从大往小的,于是我们考虑令: g i = f a N − f i g_i=f_{a_N}-f_i gi=faNfi,那么有:

f i = f a N − g i f_i=f_{a_N}-g_i fi=faNgi

f a N − g i − 1 = 1 r ( n ( f a N − g i − 1 ) − ∑ j > r ( f a N − g a j ) ) f_{a_N}-g_{i-1}=\frac 1 r(n(f_{a_N}-g_i-1)-\sum_{j>r}(f_{a_N}-g_{a_j})) faNgi1=r1(n(faNgi1)j>r(faNgaj))

整理得:

g i − 1 = 1 r ( n ( g i + 1 ) − ∑ j > r g a j ) g_{i-1}=\frac 1 r(n(g_i+1)-\sum_{j>r}g_{a_j}) gi1=r1(n(gi+1)j>rgaj)

边界是 g A N = 0 g_{A_N}=0 gAN=0,由于 f 0 = 0 f_0=0 f0=0,因此我们求得 g 0 g_0 g0 即可,现在就符合顺序dp了。

但是我们发现状态数过大,因此我们要优化转移,记 s r = ∑ j > r g a j s_r=\sum_{j>r}g_{a_j} sr=j>rgaj,则:

g i − 1 = 1 r ( n ( g i + 1 ) − s r ) g_{i-1}=\frac 1 r(n(g_i+1)-s_r) gi1=r1(n(gi+1)sr)

考虑进行这样的变形(我验证了是成立的,但怎么推出来的不太懂):

g i − 1 + N − s r N − r = N r ( g i + N − s r N − r ) g_{i-1}+\frac{N-s_r}{N-r}=\frac N r(g_i+\frac{N-s_r}{N-r}) gi1+NrNsr=rN(gi+NrNsr)

这东西要怎么推呢?我们想要快速计算,其实就是要左右同构,回到这条式子:

g i − 1 = 1 r ( n ( g i + 1 ) − s r ) g_{i-1}=\frac 1 r(n(g_i+1)-s_r) gi1=r1(n(gi+1)sr)

既然我们希望同构,我们假设加上一个常数 t t t

g i − 1 + t = n r ( g i + 1 − s r N + r t N ) g_{i-1}+t=\frac n r(g_i+1-\frac{s_r}N+\frac {rt}N) gi1+t=rn(gi+1Nsr+Nrt)

满足 t = 1 − s r N + r t N t=1-\frac{s_r}N+\frac{rt}N t=1Nsr+Nrt,解得 t = N − s r N − r t=\dfrac{N-s_r}{N-r} t=NrNsr

此时我们就可以快速递推了:

g a i + N − s r N − r = ( N r ) a i + 1 − a i ( g a i + 1 + N − s r N − r ) g_{a_i}+\frac{N-s_r}{N-r}=(\frac N r)^{a_{i+1}-a_i}(g_{a_{i+1}}+\frac{N-s_r}{N-r}) gai+NrNsr=(rN)ai+1ai(gai+1+NrNsr)

h i = g a i h_i=g_{a_i} hi=gai,直接列出转移式子:

h i = ( N r ) a i + 1 − a i ( h i + 1 + N − s r N − r ) − N − s r N − r h_i=(\frac N r)^{a_{i+1}-a_i}(h_{i+1}+\frac{N-s_r}{N-r})-\frac{N-s_r}{N-r} hi=(rN)ai+1ai(hi+1+NrNsr)NrNsr

其中 h N = 0 h_N=0 hN=0 h 0 h_0 h0 即为答案。

非常厉害,从第一步转化,到中间改变方向,加减常数这些技巧真得太厉害了。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!