当前位置: 首页 > news >正文

题解:P6162 [Cnoi2020] 四角链

传送门

绝大多数的计数题都可以用 dp 和容斥解决。

本题的 dp 比较好想,设 \(f_{i,j}\) 表示前 \(i\) 个位置填了 \(j\) 个数。考虑如果第 \(i\) 个位置不填,则贡献是 \(f_{i-1,j}\);否则前面 \(i-1\) 个位置一共填了 \(j-1\) 个数,由于第 \(i\) 个位置可以填 \(1\sim i\),则第 \(i\) 个位置有 \(i-j+1\) 种填的方法,贡献是 \((i-j+1)f_{i-1,j-1}\)。那么有状态转移方程:

\[f_{i,j}=f_{i-1,j}+(i-j+1)\times f_{i-1,j-1} \]

我们先把 \(i,j\) 用题目中的 \(n,k\) 替换一下,得到:

\[f_{n,k}=f_{n-1,k}+(n-k+1)\times f_{n-1,k-1} \]

再用 \(n-k+1\) 代换掉 \(k\),得到:

\[f_{n,n-k+1}=f_{n-1,n-k+1}+k\times f_{n-1,n-k} \]

\(S_{n,k}=f_{n,n-k+1}\),得到:

\[S_{n,k}=S_{n-1,k-1}+k\times S_{n-1,k} \]

这就是第二类 Stirling 数的递推式,因此答案是 \(\begin{Bmatrix}n\\n-k\end{Bmatrix}\),直接用通项公式计算即可:

\[\begin{Bmatrix}n\\m\end{Bmatrix}=\sum_{i=0}^m\frac{(-1)^i(m-i)^n}{i!(m-i)!}\Rightarrow\begin{Bmatrix}n\\{n-k}\end{Bmatrix}=\sum_{i=0}^{n-k}\frac{(-1)^i(n-k-i)^n}{i!(n-k-i)!} \]

我们还可以用另一种方法推导出本题的答案,考虑下面关于 \(n=6,k=3\) 的填数方案(第一行代表位置,第二行代表所填的数,不填的位置假设填 \(0\)):

\(1\) \(2\) \(3\) \(4\) \(5\)
\(0\) \(1\) \(2\) \(0\) \(4\)

我们给这个数表加一个表头,再在 \(i=1\) 的列前面加一个 \(i=0\) 的列(因为原题中 \(n\) 这个数对答案不产生贡献,所以这里其实是把多出来的那个 \(n\) 等价替换成数表最前面的 \(0\)):

\(i\) \(0\) \(1\) \(2\) \(3\) \(4\) \(5\)
\(fa_i\) \(0\) \(0\) \(1\) \(2\) \(0\) \(4\)

注意到按该表连边之后形成的图是一棵以 \(0\) 为根节点、根节点的 \(n-k-1\) 棵子树形态均为链的树。

证明:由于一共填 \(k\) 个数,也即有 \(n-k-1\) 个数没有填,在该表中表现为填了 \(n-k-1\)\(0\),因此若以 \(0\) 为根节点,则根节点有 \(n-k-1\) 棵子树。同时因为不允许填重复的数,所以除了根节点以外,其它节点最多只有一棵子树,因此这些根节点的子树形成了链状结构。

那么现在问题等价转化为:将 \(1\sim n-1\)\(n\) 个数有祖孙关系地挂在 \(n-k-1\) 条链上的方案数。再等价转化一步,即将 \(1\sim n-1\)\(n-1\) 个数划分为 \(n-k-1\) 个互不区分的非空子集方案数。再用 \(n\) 代换掉 \(n-1\),即将 \(1\sim n\)\(n\) 个数划分为 \(n-k\) 个互不区分的非空子集方案数。

这就是第二类 Stirling 数的定义,因此答案为 \(\begin{Bmatrix}n\\n-k\end{Bmatrix}\)

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 998244353, N = 1e6 + 10;
int n, k;
int qpow (int a, int b) {int res = 1;for (; b; b >>= 1, a = a * a % mod)if (b & 1)res = res * a % mod;return res;
}
int fac[N], inv[N];
void init () {fac[0] = 1;for (int i = 1; i <= n; ++i)fac[i] = fac[i - 1] * i % mod;inv[n] = qpow(fac[n], mod - 2);for (int i = n; i; --i)inv[i - 1] = inv[i] * i % mod;
}
int S (int n, int m) {int res = 0;for (int i = 0; i <= m; ++i)res = (res + qpow(m - i, n) * inv[i] % mod * inv[m - i] % mod * ((i & 1) ? -1 : 1) + mod) % mod;return res;
}
signed main () {cin >> n >> k, init(), cout << S(n, n - k);return 0;
}
http://www.hskmm.com/?act=detail&tid=26314

相关文章:

  • 题解:P3301 [SDOI2013] 方程
  • # 20232321 2025-2026-1 《网络与系统攻防技术》实验一实验报告
  • 题解:CF1292E Rin and The Unknown Flower
  • 打印A3大小的PDF文件为A4幅面
  • 课程总结2
  • 解码查找算法与哈希表
  • 第二次课动手动脑合集
  • centos8的防火墙管理
  • 如何生成和制作PDF文件 - 实践
  • 1.2 马尔可夫决策过程(Markov Decision Process, MDP)
  • 博弈论dp复习笔记
  • 10.7阅读笔记
  • 如果你的微信支付界面出现“摇一摇”,说明你的隐私正在泄露
  • 多线程和网络总结
  • 8.RV1126-OPENCV 视频中添加LOGO - 指南
  • 学习记录:响应式系统、文件通知与游戏输入机制的异同
  • oppoR9m刷Linux系统: 制作 scatter.txt 和 导出手机preloader
  • 详细介绍:ASR技术(自动语音识别)深度解析
  • 1.1 采样问题 Sampling and Bandits
  • 10.7 NOIP 模拟赛 T2. 中心极限定理
  • 【题解】10.6 国庆中秋 提高组 热身赛
  • UCB-CS70_离散数学_个人笔记:至少和至多 - Zeeh
  • 几个重要的偏微分方程
  • 虚拟机器人学习自然语言指令技术解析
  • 题解:换乘旅行
  • 2025企业级AI数据防泄漏指南:精准选型与核心指标全景透视
  • 感觉你是那种
  • 鲜花:不会说明你有抑郁症1
  • 【比赛记录】2025CSP-S模拟赛59
  • 使用 C 语言实现英文数字验证码识别系统