大概是21年itst集训队论文的学习笔记。
满棋盘是所有$(i,j):1\leq i\leq n,1\leq j\leq m$的集合。一个棋盘是满棋盘的一个子集。一个棋盘是轮廓线的，当且仅当每一列都是下面若干个格子存在。一个棋盘是ferrers的，当且仅当它是轮廓线的，并且每一行都是右边若干个格子存在。
棋盘多项式
定义一个棋盘$S$的rook number $r_k(S)$是在上面放互不攻击的车的方案数。hit number $h_{k,n}(S)$是在$n\times n$满棋盘上放互不攻击的车，恰好有$k$个车包含在$S$中的方案数(这里$S$可以被称为 禁区)。本文主要讨论这两个数在一些棋盘上的计算。
你可能已经感觉到hit number可以从rook number二项式反演得到，也就是钦点若干个在$S$中，剩下的随便排，那么对于有$k$个hit的方案，它会在$i$个车的方案中被选$\binom{k}{i}$次。比如错排就是这么干的。一般我们会算rook number而不是hit number。
棋盘多项式是rook number的ogf。
显然交换两行或者两列不会改变rook number和hit number。
如果经过若干次交换之后，棋盘变成了，对于某个$(i,j)$，只有$x\leq i,y\leq j$的部分和$x>i,y>j$的部分非空，那么这两部分是独立的，整个棋盘的棋盘多项式是两部分卷起来。这个操作称为分离。
考虑枚举一个格子选不选，如果不选则递归到剩下的，如果选则扔掉同一行同一列的并递归到剩下的。这个操作称为展开。
夫妻分座问题
给两个长$n$的排列$p,q$，计算棋盘$S={(i,p_i)}+{(j,p_j)}$的各hit number $h_{k,n}(S)$。$n\leq 2\times 10^5$。
转而计算rook number。给同一行或者同一列的点对连边，那么问题就是选一些点，相邻的不能都选。这个是二分图，因为横纵边必然是交替的，并且它是2-正则图所以必然是若干个独立的环，所以答案就是各环分治法法塔卷起来。问题是一个环怎么做，枚举第一个位置选没选，剩下的就是一条链，设它的长是$n$，那么选了$k$个的方案，可以考虑先把$k-1$个空位抽出来，选完了再把它们放回去，就是$\binom{n-k+1}{k}$，最后我们得到一个长$n$的环选$k$个的方案数是$\binom{n-k-1}{k-1}+\binom{n-k}{k}=\frac{n}{n-k}\binom{n-k}{k}$。也可以考虑dp完了写个方程硬解，但是那太麻烦了。
另外，如果$p_i=i,q_i=n-i+1$，那么它就是若干个四元环。d-finite。
ferrers棋盘
众所周知在$n\times n$ ferrers棋盘上放$n$个车的方案数是好算的。从左往右考虑，设每一列的高度是$a_i$，由于每一列包含前一列，前$i$列放了$i$个车，总会导致$i+1$列恰好$i$个位置不能放车，所以总有恰好$a_{i+1}-i$种方案。
定理 ferrers棋盘的下降幂棋盘多项式。设$r$是各rook number。
\[\sum_{k}r_kz^\underline{n-k}=\prod_k(z+a_k-k+1)\]证明 考虑用$z$是整数的情况插出来。我们往棋盘下面补$z$个满的行，考虑这个棋盘中放$n$个车的方案数，发现直接算就是右边。或者考虑上面放了$k$个，下面就有$z^\underline{n-k}$种方案放剩下的$n-k$个。所以两边是相等的。
所以ferrers棋盘的棋盘多项式可以分治法法塔然后普通多项式转下降幂多项式做到$O(n\log^2 n)$。更好的方法是直接维护一个下降幂多项式，乘法的时候一次卷积求出$0,…,\operatorname{deg}$处的点值，乘起来再一次卷积插值，这样就不用转下降幂多项式了。
是不是应该写写下降幂多项式乘法。要计算在$0,…$处的点值的ogf，大概是
\[\sum_iz^i\sum_ja_ji^\underline{j}=\sum_ii!z^i\sum_j\frac{a_j}{(i-j)!}\]后面是$\frac{1}{i!}$和$a_i$的普通卷积。
或者你可以说，$a$的ogf卷$e^z$就得到点值的egf。
Gnutella Chessmaster
$n\times n$的棋盘，对于每个$k$求放$k$个互不攻击的(国际象棋的)象的方案数。$n\leq 10^5$。
黑白染色，两部分是独立的。然后转一下，此时两部分看起来像是这两种样子 :
1
2
3
4
5
6
7
## #
#### ###
###### #####
###### #######
#### #####
## ###
#
考虑第一个，把它换成ferrers棋盘，它的$a=2,2,4,4,6,6,…$这样的，它的下降幂棋盘多项式就是
\[\prod_i(z+a_i-i+1)=(z+2)^{\lceil\frac{n}{2}\rceil}(z+1)^{\lfloor\frac{n}{2}\rfloor}\]注意到右边的点值可以快速幂，直接一次卷积插出下降幂多项式来。然后卷一次就好了。
q-analog
咕。