1 条题解

  • 0
    @ 2025-12-11 21:16:19

    根据题意分析,所有生长顺序的总数为 N!N!,不便度的期望 EE 乘以 N!N! 即为所有生长顺序的不便度总和 F(N)F(N)。通过推导得到:

    [ F(N) = \sum_{k=1}^{N-1} k! \cdot (k^2 + 3k) \mod P ]

    其中 PP 为模数。对于 N=1N=1F(1)=0F(1)=0;对于 N2N \ge 2,按公式计算即可。

    算法步骤

    1. 初始化 ans = 0fac = 1
    2. 循环 kk11N1N-1
      • fac = fac * k % P
      • ans = (ans + fac * (k*k + 3*k)) % P
    3. 输出 ans

    时间复杂度为 O(N)O(N),满足 N2000N \le 2000 的限制。

    验证样例

    • 输入 N=3,P=109+7N=3, P=10^9+7,计算:
      • k=1k=1: 1!×(1+3)=41! \times (1+3) = 4
      • k=2k=2: 2!×(4+6)=202! \times (4+6) = 20
      • 总和 2424,与样例输出一致。

    因此,答案即为 F(N)modPF(N) \mod P

    • 1

    信息

    ID
    6102
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者