🔖 acm动态规划解题报告

题意简述

  • 一个长度为 L 的串 a0a1⋯ar−1∗ar+1ar+2⋯aL−1 表示算式：A×B。其中：

    A=∑i=0r−1(ai×10r−i−1)B=∑i=r+1L−1(ai×10L−i−1)0⩽r<L,0⩽ai⩽9,0⩽i<L且i≠r
    (1)令f(S)=f(a0a1⋯ar−1∗ar+1ar+2⋯aL−1)(2)=A×B={[∑i=0r−1(ai×10r−i−1)]×[∑i=r+1L−1(ai×10L−i−1)],0<r<L−10,r=0 或 r=L−1

  • 交换操作：从 S 中任选两个字符（可以选择 * 号），交换它们的位置

若 K 次交换后，f(S) 的期望值为 E；求 (E×(L2)K)mod(109+7)。

数据范围：1⩽L,K⩽50。

题目简析

为了计算期望，可以先求出所有的可能。对于一个长度为 N 的串 s，记它所代表的算式的的计算结果为 φ(s)。因为每交换一次后会得到多个可能的串，我们用 Γ(k,p) 表示执行 k 此交换后，所有乘号在位置 p 处的串构成的可重集合。所以我们想要的答案就是 ∑p=1N∑s∈Γ(K,p)φ(s).

设 f(k,p,a,b)=∑s∈Γ(K,p)sa×sb。注意到，

φ(s)=(∑a=1p−1sa×10p−a−1)×(∑b=p+1Nsb×10N−b)=∑a=1p−1∑b=p+1Nsa×sb×10p−a−1+N−b

所以，

∑p=1N∑s∈Γ(K,p)φ(s)=∑p=1N∑a=1p−1∑b=p+1Nf(K,p,a,b)×10p−a−1+N−b

紧接着，考虑 f(k,p,a,b) 如何进行状态转移：

#abp
1动动动
2动动不动
3动不动动
4动不动不动
5不动动动
6不动动不动
7不动不动动
8不动不动不动


我们逐一进行考虑，则所有情况的和就是 f(k+1,p,a,b).

  1. 显然不可行，故贡献为: 0

  2. 即 a 上的字符和 b 上的字符交换，贡献为: f(k,p,b,a)

  3. 即 a 上的字符和 p 上的字符交换，贡献为: f(k,a,p,b)

  4. 即 a 上的字符和剩下的 N−3 个字符中的任一字符交换，贡献为: ∑1⩽i⩽N,i≠a,i≠pf(k,p,i,b)

  5. 即 b 上的字符和 p 上的字符交换，贡献为: f(k,b,a,p)

  6. 即 b 上的字符和剩下的 N−3 个字符中的任一字符交换，贡献为: ∑1⩽i⩽N,i≠a,i≠pf(k,p,a,i)

  7. 即 p 上的字符和剩下的 N−3 个字符中的任一字符交换，贡献为: ∑1⩽i⩽N,i≠a,i≠pf(k,i,a,b)

  8. 即剩下的 N−3 个字符中的任选两个字符交换，贡献为: (2N−3)f(k,p,a,b)

对于 4、6、7 利用前缀和，可以在 O(1) 的时间内计算出来。故算法的总时间复杂度为 O(n3).

小记

最后一个小时一直和 ZPH 学长讨论这一道题，当时实在是太弱，以至于这样的数据范围竟然想着推数学公式。。。ORZ。。

题解是赛后一周写的，所以是 pdf 格式。 Markdown 中，两侧下划线表示斜体，所以书写数学公式时下划线要用 '' 转义。

Related

© 2017-2025 光和尘有花满渚、有酒盈瓯

Comments