AT_arc162_e [ARC162E] Strange Constraints 题解 / 关于平方倒数和为常数的定理学习笔记

zrl123456 · 2025-11-16 17:12:37 · 题解

:::::info[题目基本信息] 考察：组合数学，动态规划 DP（2780）。
题目简介：
给定 \{a_n\}，求有多少 \{b_n\} 满足（对 998244353 取模）：

• \forall i\in[1,n],b_i\in[1,n]
• \forall i\in[1,n],\sum_{j=1}^n[b_j=i]\le a_i
• \forall i\in[1,n],\sum_{j=1}^n[b_j=b_i]\le a_i

数据范围：

• 1\le n\le 500
• \forall i\in[1,n],1\le a_i\le n

  ::::: 通过尝试我们发现朴素地对位置 DP 或者连续段 DP 都是不行的，所以我们换一种思路，考虑对限制进行 DP，那么我们注意到一个优美的性质，如果我们按一个数在 \{b_n\} 的出现次数降序决策，那么它们之间的影响和干扰不大，所以我们尝试这条道路。
  具体地，设 f_{i,j,k} 表示考虑到所有在 \{b_n\} 中出现次数不低于 i 的数，一共有 j 个，一共出现了 k 次，考虑枚举出现次数恰好为 i 的数的个数为 l，那么我们需要转移到 f_{i-1,j+l,k+(i-1)l} ，设 t_i=\displaystyle\sum_{j=1}^n[a_j\ge i]，那么我们需要在 t_{i-1}-j 种还没填的数里面选 l 种数进行一个填，然后在 t_{i-1}-k 个位置里选 (i-1)l 个进行一个填，然后排列一下顺序，所以最终的转移方程式为：

  f_{i-1,j+l,k+(i-1)l}\leftarrow \binom{t_{i-1}-j}{l}\binom{(i-1)l}{l,l,\dots,l}\binom{t_{i-1}-k}{(i-1)l}f_{i,j,k}

  这样的话正确性是有保证的，复杂度是多少呢？
  容易发现 j,l 都是 \dfrac{n}{i} 级别，那么复杂度满足这样一个式子，然后我们将其推导：

  \begin{aligned}\sum_{i=1}^n\sum_{j=1}^{\frac{n}{i}}\sum_{k=1}^n\sum_{l=1}^{\frac{n}{i}}1&=\sum_{i=1}^n\sum_{j=1}^{\frac{n}{i}}\sum_{k=1}^n\frac{n}{i}\\&=\sum_{i=1}^n\frac{n^3}{i^2}\\&=n^3\sum_{i=1}^n\frac{1}{i^2}\end{aligned}

  那么 \displaystyle\sum_{i=1}^n\frac{1}{i^2} 是多少呢？
  :::::success[关于上式结果为常数的说明] 有个定理是 \displaystyle\sum_{i=1}^{\infty}\frac{1}{i^2}=\frac{\pi^2}{6}，但是关于它的证明太魔怔，所以我们不要用上面的定理。
  注意到我们不需要太精确，所以我们可以适当放缩：

  \begin{aligned}\sum_{i=1}^n\frac{1}{i^2}&=1+\sum_{i=2}^n\frac{1}{i^2}\\&\le1+\sum_{i=2}^{n}\frac{1}{i(i-1)}\\&=1+\sum_{i=2}^n\frac{1}{i-1}-\frac{1}{i}\\&=1+\frac{1}{1}-\frac{1}{n}\\&<2\end{aligned}

  所以这个东西只是常数复杂度。
  ::::: 综上，时空复杂度均为 \Theta(n^3)。

code