核桃 OJ 题解 · 小核桃玩核桃棋

· · 个人记录

前言

内容有违反洛谷社区规则的或不规范的，请私信蒟蒻或直接发在评论区。欢迎奆佬们给蒟蒻的题解提出建议！
其实是重现讲评，写的是蒟蒻的理解 QAQ。

下文中所有变量均为正整数。

正文

题目和题意

HT-015-Div.3 普及组 T4：小核桃玩核桃棋

题意：现有棋盘 U=\{(x,y)\,|\,1\le y\le n,1\le x\le a_y\}，其中 \{a_n\} 满足 n\ge a_1\ge a_2\ge\cdots\ge a_n\ge1。定义 g(s)=(s\subseteq U)\wedge(\forall(x,y)\in U,(\exists c,(x,c)\in s)\vee(\exists r,(r,y)\in s))。设 M=\displaystyle\min_{(s\subseteq U)\wedge g(s)}|s|，求 \displaystyle\sum_{(s\subseteq U)\wedge g(s)}[|s|=M]，即最佳方案的个数。1\le n\le5\times10^3。答案对 10^9+7 取模。

解法

正解

容易想到 M\le a_1，放满第一列即可。下文中无特殊说明，s 都满足 s\subseteq U。令 f(s)=g(s)\wedge(|s|=M)，S=\{s\,|\,f(s)\},ans=|S|。

我们可以找到一个边长为 d=\max_{i\le a_i}\{i\} 的正方形。那么很明显，这个正方形至少需要 d 颗棋子，即 M\ge d。但是又因为可以令 s=\{(x,x)\,|\,1\le x\le d\}，此时 g(s) 为真且当前的 |s|=d，所以 M=d。

因为合法方案要么每行都至少有一个棋子，要么每列都至少有一个棋子，（看不懂没有关系，先看下面的证明）所以令 f_1(s)=(\forall1\le x\le d,(\exists1\le y\le n,(x,y)\in s)),\,f_2(s)=(\forall1\le y\le d,(\exists1\le x\le a_y,(x,y)\in s)),\,S_1=\{s\,|\,f(s)\wedge f_1(s)\},\,S_2=\{s\,|\,f(s)\wedge f_2(s)\}。那么，就有以下式子（下面莫名其妙的换行是因为太长了）：

\begin{array}{l} \because 1\le y_2,x_1\le d\le n\\\therefore\forall1\le x_2,y_1\le n,(x_1,y_1)\notin s,(x_2,y_2)\notin s\\\because\neg g(s)=(\exists(x,y)\in U,(\forall c,(x,c)\notin s)\wedge(\forall r,(r,y)\notin s))\\\therefore\neg g(s)\text{ is true}\\\therefore g(s)\text{ is false}\\\because f(s)=g(s)\wedge(|s|=M)\\\therefore f(s)\text{ is false}\\\therefore(\neg f_1(s))\wedge(\neg f_2(s))\Rightarrow \neg f(s)\\\because(p\Rightarrow q)\Rightarrow(\neg q\Rightarrow\neg p)\\\therefore f(s)\Rightarrow\neg((\neg f_1(s))\wedge(\neg f_2(s)))\\\therefore f(s)\Rightarrow f_1(s)\vee f_2(s)\\\therefore f(s)\Rightarrow f(s)\wedge(f_1(s)\vee f_2(s))\\\therefore S_1\cup S_2=\{s\,|\,f(s)\wedge(f_1(s)\vee f_2(s))\}\\\qquad\qquad\,\,=\{s\,|\,f(s)\}\\\qquad\qquad\,\,=S\\\therefore ans=|S|=|S_1\cup S_2|=|S_1|+|S_2|-|S_1\cap S_2| \end{array}

其中，|S_2| 和 |S_1| 几乎一样，翻转一下就行。而 |S_1\cap S_2|=d!，所以只需考虑 |S_1| 的求法。设 row_i 表示第 i 行有几个格子，令 t=row_{d+1}，dp_{i,j} 表示已经在前 i 行中放了 i 个棋子，其中有 j 个棋子的列小于等于 t。那么最终结果是 dp_{d,t}。而 dp 的转移方程就是：

dp_{0,0}=1\\dp_{i+1,j}\gets dp_{i+1,j}+(row_{i+1}-t+j)\times dp_{i,j}\\dp_{i+1,j+1}\gets dp_{i+1,j+1}+(t-j)\times dp_{i,j}\\dp_{i,j}=(row_i-t+j)\times dp_{i-1,j}+(t-j+1)\times dp_{i-1,j-1}\\dp_{i,0}=(row_i-t)\times dp_{i-1,0}

而 row 的求解是这样的：

row_x=\sum_{y=1}^n[x\le a_y]

复杂度直接就是 O(n^2)，也可以用双指针优化。总体时间复杂度为 O(n^2)\approx O(2.5\times10^7)，可以通过。

AC 链接

附录

蒟蒻其他的核桃 OJ 题解。