ShinriiTin/notes/Counting_and_Expectation

计数与期望问题选讲

K Perm Counting

题目大意：

求有多少个\(1\)到\(n\)的排列\(a\)，满足\(\forall 1\le i\le n\to|a_i-i|\not=k\).

\(2\le n\le2000,1\le k\le n-1\).

题解：

令\(f[i]\)表示选择\(i\)个数并决定它们的位置，使得这\(i\)个数都满足\(|a_i-i|=k\)，即\(a_i\)可以是\(i-k\)或\(i+k\)，的方案数。

则由容斥原理可得\(\displaystyle ans=\sum\limits_{i=0}^n f[i]\times(n-i)!\times(-1)^i\).

接下来介绍如何计算\(f[i]\).

将\(1\)到\(n\)按\(\mod{k}\)的余数分组，则不同的组之间相互独立。

对于同组的情况，我们考虑一个dp，令\(g[i][j][mask]\)表示只考虑前\(i\)个数，一共选了\(j\)个数，最右边的两个数是否占用了\(x+k\)位置的状态为\(mask\)的方案数。

则有递归基：

\[g[1][0][0]=1,g[1][1][1]=1\]

以及转移方程：

\[\displaystyle\begin{aligned}g[i][j][0]&=g[i-1][j][0]+g[i-1][j][2]+g[i-1][j-1][0]\\g[i][j][1]&=g[i-1][j-1][0]+g[i-1][j-1][2]\\g[i][j][2]&=g[i-1][j][1]+g[i-1][j][3]+g[i-1][j-1][1]\\g[i][j][3]&=g[i-1][j-1][1]+g[i-1][j-1][3]\end{aligned}\]

令\(getS(i,j)=g[i][j][0]+g[i][j][2]\)，则可以做一个分组背包来计算\(f[i]\)：

枚举\(\mod{k}\)的余数\(x\)，然后枚举这一组选择的数量\(i\)，则背包时应该用\(f[i]+=f[i-j]\times getS(siz[x],i)\)更新，其中\(siz[x]\)为该组的大小。

计算\(g\)部分的时间复杂度为\(O(n^2)\)，空间复杂度为\(O(n^2)\)；计算\(f\)部分的时间复杂度为\(O(n^2)\)，空间复杂度为\(O(n)\)；计算\(ans\)部分的时间复杂度为\(O(n)\)，空间复杂度为\(O(n)\)。

因此，算法总的时间复杂度为\(O(n^2)\)，空间复杂度\(O(n^2)\)。

Dictionary

题目大意：

给出\(1\le n\le50\)个只有小写英文字母和?组成的字符串\(s_1,\cdots,s_n\)，\(1\le|s_i|\le20\).

求有多少种方案，将所有?换成小写英文字母，并且满足\(s_1<s_2<\cdots<s_n\).

题解：

首先通过给长度不够的字符串末尾添加同一个字典序小于’a’的字符的方式将所有串的长度统一，设这个长度为\(m\)。

这样，如果两个串\(s_i\)与\(s_j\)长度为\(k\)的后缀已经决定了大小关系，则它们除去该后缀之外的两个前缀应该完全相同。

这样我们可以考虑从后往前进行dp，从后往前为每个字符串填上小写字母。

令\(f[len][l][r]\)表示\(s_l,\cdots,s_r\)通过后缀\(s[len\cdots m]\)确定了\(s_l<s_{l+1}<\cdots<s_r\)的大小关系的方案数，则有递归基\(f[m+1][i][i]=1\).

这样我们就可以横向地进行dp，而纵向的部分需要另一个dp来辅助。

假设我们当前正在做\(f[len][l][r]\)的dp，令\(g[i][x]\)表示\(s_l,\cdots,s_i\)可以确定大小关系，且\(s_i\)当前位置填的字符为\(x\)的方案数。

则有递归基\(g[l-1][x]=1\)，

转移方法为，枚举\(s_r\)当前位可以填的字符\(k\)，再枚举\(i\)满足\(s_i,\cdots,s_r\)都可以填字符\(k\)，则有\(\displaystyle g[r][k]=\sum_i\sum_{j<k}g[i-1][j]\times f[len+1][i][r]\)。

做完\(g\)之后，当前位置的\(f\)也得到了：\(f[len][l][r]=\sum_k g[r][k]\).

通过处理\(g\)的前缀和，算法总的时间复杂度为\(O(n^2m\sigma)\)，空间复杂度为\(O(n^2m+n\sigma)\)，\(\sigma\)为字符集大小。

Leftmost Ball

题目大意：

有\(n\le2000\)种颜色的球，每种颜色都有\(k\le2000\)个，现在将它们放在一行任意排列，然后将每种颜色最左边的球染色成\(0\)号颜色（与\(n\)种颜色都不同），问最终有多少种不同的局面。

题解：

考虑如何一个最终局面是否合法。最终局面合法，当且仅当，将出现的颜色按除了\(0\)号颜色之外的每种颜色最左边的球的顺序重新编号，第\(i\)种颜色的球左边至少有\(i\)个白球。

因此可以用\(f[i][j]\)表示仅考虑有\(i\)个\(0\)号球，\(j\)种不同颜色的球的不同局面数量，则答案为\(f[n][n]\times n!\)。

显然\(f[0][0]=1\)，\(f[i][j]\)则需要考虑当前最左边的球放\(0\)号球还是放\(j\)种颜色中编号最小的颜色的球。

  • 如果放\(0\)号球（要求\(i>0\)），则有\(f[i-1][j]\)种方案；

  • 如果不放\(0\)号球（要求\(j>i\)），则需要先将该种颜色的其余\(k-2\)个球的位置决定好，然后转化为子问题\(f[i][j-1]\)，共\(\displaystyle\binom{i+j(k-1)-1}{k-2}\times f[i][j-1]\)种方案；

时空复杂度\(O(n(n+k))\)，注意要特判\(k=1\)，此时显然只有一种方案。

BBQ Hard

题目大意：

有\(n\le2\times10^5\)包物品，第\(i\)包物品中有\(A\)类物品\(1\le A_i\le2000\)个，\(B\)类物品\(1\le B_i\le2000\)个，同类的物品个体之间不存在差异。

现在要从中取出两包物品，将其中的物品都取出，再将其中的物品按某种顺序排列，问有多少种不同的方案。

两种方案不同当前仅当选择的两包物品不同，或者其中物品的排列顺序不同。

题解：

如果确定选择第\(i\)包和第\(j\)包物品，则不同的方案共有\(\displaystyle \frac{(A_i+A_j+B_i+B_j)!}{(A_i+A_j)!(B_i+B_j)!}\).

这个几何意义可以是从只能向上和向右走的网格中从\((-A_i,-B_i)\)走到\((A_j,B_j)\)的方案数。

因此可以用dp求出从\((-A_1,-B_1),\cdots,(-A_n,-B_n)\)中任意位置出发走到\((A_i,B_i)\)的方案数求和，再减去从\((-A_i,-B_i)\)走到\((A_i,B_i)\)的方案数之和，最后再除以\(2\)消序即可。

时空复杂度\(O(n+m^2)\)，其中\(m\)为坐标范围。

其他题暂时都找不到提交的地方，后面找到了或者和队友讨论过了再放

Dancing IOI Team

占个坑，感觉会做了，写完和暴力拍一拍，没问题放上来。

题目大意：

给定两个长度为\(n\)的数列\(\{a_n\}\)和\(\{b_n\}\)，以及一个正整数\(k\)。

其中\(1\le k\le n\le100\)，\(a_1\ge a_2\ge\cdots\ge a_n\)，\(0\le a_i,b_i\le1000\)，\(a_i\)两两不同，\(b_i\)两两不同。

问有多少\(1\)到\(n\)的排列\(p\)，满足\(\displaystyle\min\limits_{i\le k}a_i+b_{p_i}\ge\max\limits_{j>k}a_j+b_{p_j}\)，对\(10^9+7\)取模。

题解：

令\(f(t)\)表示满足下面三个条件的排列数：

  • \(\forall i\le k\to a_i+b_{p_i}\ge t\)

  • \(\forall j>k\to a_j+b_{p_j}\le t\)

  • \(\exists i\le k\land a_i+b_{p_i}=t\)

则\(ans=\sum\limits_t f(t)\).

对于上述的第三个条件，我们可以简单地用一个容斥将其去掉。

令\(g(A,B)\)表示满足下面两个条件的排列数：

  • \(\forall i\le k\to a_i+b_{p_i}\ge A\)

  • \(\forall j>k\to a_j+b_{p_j}\le B\)

则\(f(t)=g(t,t)-g(t+1,t)\).

接下来考虑如何求\(g(A,B)\)的值。

这其实是一个二分图完备匹配计数问题：

\(a,b\)分别是二分图的左右部，\(i\le k\)的\(a_i\)可以与不小于\(A-a_i\)的\(b\)匹配，\(i>k\)的\(a_i\)可以与不大于\(B-a_i\)的\(b\)匹配。

因此我们将\(i\le k\)的\(A-a_i\)，\(i>k\)的\(B-a_i\)，以及\(b_j\)，放在一起按大小排序（如果值相同，认为\(A-a_i\)最小，\(B-a_i\)最大）。

对于排序后的数组，我们从小到大扫描一次，同时用dp计算方案数。

令\(dp[i][j]\)表示扫描到了第\(i\)个位置，与\(i\le k\)的\(a_i\)匹配的\(b\)的数量为\(j\)的方案数。

显然递归基为\(f[0][0]=1\)。

转移方式视当前位置的元素类型而定，记\(A-a_i\)类型为\(0\)，\(b\)类型为\(1\)，\(B-a_i\)类型为\(2\)：

  • 如果当前元素为类型\(0\)，则只需简单的拷贝上一个位置处的dp值

  • 如果当前元素为类型\(1\)，那么可能有两种转移：

    • 第一种，当前元素不与类型\(0\)匹配，将其加入未分配组中，这种转移对\(j\)没有要求，dp[i][j]=dp[i-1][j];
    • 第二种，当前元素与类型\(0\)匹配，要求\(j\)不为零且不大于之前扫描到的类型\(0\)数量\(cnt_0\)，dp[i][j]+=dp[i-1][j-1]*(cnt_0-j+1);

  • 如果当前元素为类型\(2\)，那么分两种情况（令\(cnt_1\)为之前扫描到的类型\(1\)的数量，\(cnt_2\)为之前扫描到的类型\(2\)的数量，则未分配的类型\(1\)有\(cnt_1-j\)个）：

    • 第一种情况，若\(cnt_1-j<cnt_2\)，则当前的类型\(2\)多于未分配的类型\(1\)，无法达到完备匹配，dp[i][j]=0;
    • 否则，第二种情况，dp[i][j]=dp[i][j]*(cnt_1-cnt_2-j+1);

转移完毕之后，\(g(A,B)=dp[n<<1][k]\)。

计算一次\(g\)，时间复杂度为\(O(n^2)\)，空间复杂度为\(O(n^2)\)。

若\(t\)最多有\(m\)种取值，则总的时间复杂度为\(O(n^2m)\)，空间复杂度为\(O(n^2)\)。

本题中\(m\le2001\)。

Izhevsk Training Camp (Simplified)

占个坑，感觉会做了，写完和暴力拍一拍，没问题放上来。

题目大意：

给出三个\(1\)到\(n\)的排列\(a,b,c\)，问有多少二元组\((x,y)\)满足\(a_x<a_y,b_x<b_y,c_x<c_y\)。

\(2\le n\le5\times10^6\).

题解：

令满足\(a_x<a_y,b_x<b_y,c_x<c_y\)的二元组数量为\(A\)，满足\(a_x<a_y,b_x<b_y,c_x>c_y\)或\(a_x<a_y,b_x>b_y,c_x<c_y\)或\(a_x>a_y,b_x<b_y,c_x>c_y\)的二元组数量为\(B\)，则\(A+B=\binom{n}{2}\).

令满足\(a_x<a_y,b_x<b_y\)的二元组数量为\(u\)，满足\(b_x<b_y,c_x<c_y\)的二元组数量为\(v\)，满足\(a_x<a_y,c_x<c_y\)的二元组数量为\(w\)，则\(3A+B=u+v+w\).

因此我们可以做三次二维偏序，然后求得\(\displaystyle A=\frac{u+v+w-\binom{n}{2}}{2}\)，时间复杂度\(O(n\log{n})\)，空间复杂度\(O(n)\)。

Mixed Drinks

由于某些原因暂时不公开题解