「营业日志 2020.11.26」一道纳什均衡数数题

数数题"/>

「营业日志 2020.11.26」一道纳什均衡数数题

和 xzz 讨论的一道集训队自选题。

简要题意 一颗二叉树，划分成 A , B , L A,B,L A,B,L 三部分，其中 L L L 为叶节点，其余点均有两个孩子。每个叶节点有 c , d c,d c,d 值，一组策略为给每个点选择一个重子，称双方的收益为从根沿重子走到的对应 c , d c,d c,d 值。称一个策略纳什均衡当且仅当任取 A A A 中策略改变均不使得 c c c 更大，任取 B B B 中策略改变均不使 d d d 更大。对所有 ∀ u ∈ L , 1 ≤ c u , d u ≤ k \forall u\in L,1\le c_u,d_u\le k ∀u∈L,1≤cu​,du​≤k 的情况，对纳什均衡的策略数求和。

首先一个简单的想法是考虑一个朴素的 DP， F u ( i , j ) F_u(i, j) Fu​(i,j) 表示 u u u 所在的子树达到纳什均衡，其中 A A A 的最优策略达到了 i i i， B B B 的最优策略达到了 j j j。我们来先看一下假设 u ∈ A u\in A u∈A 的情况。其 u ∈ B u\in B u∈B 的转移是完全对称的：

设两子为 l , r l, r l,r。若以 l l l 为重子，注意此时 l l l 的子树维持纳什均衡，但 r r r 的子树只需保证修改 A A A 可达的最大值 ≤ i \le i ≤i。我们记 X r ( i ) X_r(i) Xr​(i) 表示最大值 ≤ i \le i ≤i 的情况。那么就有

F u ( i , j ) ← F l ( i , j ) ⋅ X r ( i ) F_u(i,j) \leftarrow F_l(i,j) \cdot X_r(i) Fu​(i,j)←Fl​(i,j)⋅Xr​(i)

对称地，我们可得此时有

F u ( i , j ) = F l ( i , j ) ⋅ X r ( i ) + F r ( i , j ) ⋅ X l ( i ) F_u(i,j) = F_l(i,j) \cdot X_r(i) + F_r(i,j) \cdot X_l(i) Fu​(i,j)=Fl​(i,j)⋅Xr​(i)+Fr​(i,j)⋅Xl​(i)

而此时的 X , Y X,Y X,Y 呢？对于本层的 X X X，两个子树均能取到，故有

X u ( i ) = 2 X l ( i ) ⋅ X r ( i ) X_u(i) = 2X_l(i)\cdot X_r(i) Xu​(i)=2Xl​(i)⋅Xr​(i)

而对于 Y Y Y（ B B B 的最优化）来说，这被 A A A 完全摆布，另一子树的细节就没用了，所以是

Y u ( i ) = Y l ( i ) ⋅ 2 ∣ A r ∣ + ∣ B r ∣ k 2 ∣ L r ∣ + Y r ( i ) ⋅ 2 ∣ A l ∣ + ∣ B l ∣ k 2 ∣ L l ∣ Y_u(i) = Y_l(i) \cdot 2^{|A_r|+|B_r|}k^{2|L_r|} + Y_r(i) \cdot 2^{|A_l|+|B_l|}k^{2|L_l|} Yu​(i)=Yl​(i)⋅2∣Ar​∣+∣Br​∣k2∣Lr​∣+Yr​(i)⋅2∣Al​∣+∣Bl​∣k2∣Ll​∣

不难看出 X , Y X,Y X,Y 是多项式，但 F F F 是个二元多项式。然而经过归纳，我们发现 F F F 的两元是实质上独立的！我们考虑归纳，若

F u = U u ⋅ V u F_u = U_u \cdot V_u Fu​=Uu​⋅Vu​

有良定义的关系

X u ( i ) = 2 ∣ A u ∣ k ∣ L u ∣ U u ( i ) ⋅ i Y u ( i ) = 2 ∣ B u ∣ k ∣ L u ∣ V u ( i ) ⋅ i \begin{aligned} X_u(i) &= 2^{|A_u|} k^{|L_u|} U_u(i)\cdot i\\ Y_u(i) &= 2^{|B_u|} k^{|L_u|} V_u(i)\cdot i \end{aligned} Xu​(i)Yu​(i)​=2∣Au​∣k∣Lu​∣Uu​(i)⋅i=2∣Bu​∣k∣Lu​∣Vu​(i)⋅i​

我们进行归纳。在叶节点处，令 U u ( i ) = V u ( i ) = 1 U_u(i)=V_u(i)=1 Uu​(i)=Vu​(i)=1 即可。还是考虑 A A A 位置。

F u ( i , j ) = F l ( i , j ) ⋅ X r ( i ) + F r ( i , j ) ⋅ X l ( i ) = U l ( i , j ) V l ( i , j ) U r ( i , j ) i 2 ∣ A r ∣ k ∣ L r ∣ + U r ( i , j ) V r ( i , j ) U l ( i , j ) i 2 ∣ A l ∣ k ∣ L l ∣ U u ( i , j ) V u ( i , j ) = U l ( i , j ) U r ( i , j ) i ( V l ( i , j ) 2 ∣ A r ∣ k ∣ L r ∣ + V r ( i , j ) 2 ∣ A l ∣ k ∣ L l ∣ ) U u ( i , j ) = U l ( i , j ) U r ( i , j ) i V v ( i , j ) = V l ( i , j ) 2 ∣ A r ∣ k ∣ L r ∣ + V r ( i , j ) 2 ∣ A l ∣ k ∣ L l ∣ X u ( i ) = 2 X l ( i ) ⋅ X r ( i ) = 2 ( 2 ∣ A l ∣ k ∣ L l ∣ U l ( i ) ⋅ i ) ( 2 ∣ A r ∣ k ∣ L r ∣ U r ( i ) ⋅ i ) = 2 ∣ A u ∣ k ∣ L u ∣ U l ( i ) U r ( i ) i 2 = 2 ∣ A u ∣ k ∣ L u ∣ U u ( i ) ⋅ i Y u ( i ) = Y l ( i ) ⋅ 2 ∣ A r ∣ + ∣ B r ∣ k 2 ∣ L r ∣ + Y r ( i ) ⋅ 2 ∣ A l ∣ + ∣ B l ∣ k 2 ∣ L l ∣ = ( V l ( i ) ⋅ 2 ∣ A r ∣ k ∣ L r ∣ + V r ( i ) ⋅ 2 ∣ A l ∣ k ∣ L l ∣ ) ⋅ 2 ∣ B l ∣ + ∣ B r ∣ k ∣ L u ∣ = Y l ( i ) ⋅ 2 ∣ A r ∣ k ∣ L r ∣ + Y r ( i ) ⋅ 2 ∣ A l ∣ k ∣ L l ∣ \begin{aligned} F_u(i,j) &= F_l(i,j) \cdot X_r(i) + F_r(i,j) \cdot X_l(i)\\ &= U_l(i,j)V_l(i,j)U_r(i,j)i 2^{|A_r|} k^{|L_r|} +U_r(i,j)V_r(i,j)U_l(i,j)i 2^{|A_l|} k^{|L_l|}\\ U_u(i,j)V_u(i,j)&= U_l(i,j)U_r(i,j) i\left( V_l(i,j) 2^{|A_r|} k^{|L_r|}+ V_r(i,j) 2^{|A_l|} k^{|L_l|} \right)\\ U_u(i,j)&=U_l(i,j)U_r(i,j) i\\ V_v(i,j)&=V_l(i,j) 2^{|A_r|} k^{|L_r|}+ V_r(i,j) 2^{|A_l|} k^{|L_l|}\\ X_u(i)&=2 X_l(i)\cdot X_r(i)\\ &=2 \left(2^{|A_l|} k^{|L_l|} U_l(i)\cdot i\right) \left(2^{|A_r|} k^{|L_r|} U_r(i)\cdot i\right)\\ &=2^{|A_u|}k^{|L_u|} U_l(i)U_r(i)i^2\\ &=2^{|A_u|}k^{|L_u|} U_u(i)\cdot i\\ Y_u(i)&= Y_l(i) \cdot 2^{|A_r|+|B_r|}k^{2|L_r|} + Y_r(i) \cdot 2^{|A_l|+|B_l|}k^{2|L_l|}\\ &= \left( V_l(i) \cdot 2^{|A_r|}k^{|L_r|} + V_r(i) \cdot 2^{|A_l|}k^{|L_l|} \right)\cdot 2^{|B_l|+|B_r|} k^{|L_u|}\\ &= Y_l(i) \cdot 2^{|A_r|}k^{|L_r|} + Y_r(i) \cdot 2^{|A_l|}k^{|L_l|} \end{aligned} Fu​(i,j)Uu​(i,j)Vu​(i,j)Uu​(i,j)Vv​(i,j)Xu​(i)Yu​(i)​=Fl​(i,j)⋅Xr​(i)+Fr​(i,j)⋅Xl​(i)=Ul​(i,j)Vl​(i,j)Ur​(i,j)i2∣Ar​∣k∣Lr​∣+Ur​(i,j)Vr​(i,j)Ul​(i,j)i2∣Al​∣k∣Ll​∣=Ul​(i,j)Ur​(i,j)i(Vl​(i,j)2∣Ar​∣k∣Lr​∣+Vr​(i,j)2∣Al​∣k∣Ll​∣)=Ul​(i,j)Ur​(i,j)i=Vl​(i,j)2∣Ar​∣k∣Lr​∣+Vr​(i,j)2∣Al​∣k∣Ll​∣=2Xl​(i)⋅Xr​(i)=2(2∣Al​∣k∣Ll​∣Ul​(i)⋅i)(2∣Ar​∣k∣Lr​∣Ur​(i)⋅i)=2∣Au​∣k∣Lu​∣Ul​(i)Ur​(i)i2=2∣Au​∣k∣Lu​∣Uu​(i)⋅i=Yl​(i)⋅2∣Ar​∣+∣Br​∣k2∣Lr​∣+Yr​(i)⋅2∣Al​∣+∣Bl​∣k2∣Ll​∣=(Vl​(i)⋅2∣Ar​∣k∣Lr​∣+Vr​(i)⋅2∣Al​∣k∣Ll​∣)⋅2∣Bl​∣+∣Br​∣k∣Lu​∣=Yl​(i)⋅2∣Ar​∣k∣Lr​∣+Yr​(i)⋅2∣Al​∣k∣Ll​∣​

故归纳成立，因此我们只需维护 U , V U,V U,V 即可。注意到这一关系是两个孩子的乘法或线性组合，我们可以对表达式树通过分治在 Θ ( n log ⁡ 2 n ) \Theta(n\log ^2 n) Θ(nlog2n) 内完成计算。然后藉由伯努利数即可在 Θ ( n log ⁡ n ) \Theta(n\log n) Θ(nlogn) 内求出答案。