date: 2020.07.05 13:00-18:00

practice link

题目大意：给一个串，$n\le3000$，$\Sigma\le70$。问将这个串重排后回文子串数量的最大值，以及达到该数量的重排方案数。

题解：考虑所有回文子串的集合和所有相同字符对的集合。容易注意到前者有一到后者的单射。因而回文子串数量 $\le$ 相同字符对的数量。而当所有相同字符排列在一起时，能取到最大值。

接下来考虑有哪些其它 pattern 也能达到最大值。首先一个字符可以如前所述全部排在一起。除此之外，若一个字符 a 有三个以上，首先它们自己的位置必须成一等差数列，其次相邻两个 a 之间的串都相等，且是回文串。考虑 a***a***a，第一个 a 后的 * 和第二个 a 后的 * 应当相等，这将导致第一个 a 后的第二个 *=a，矛盾。因此相邻 a 之间只能是单个字符，即 ababab... 的模式。对于有两个的字符，还可以包在某个回文串的外部，如 abcbcba。只有一个的字符，要么单独排列，要么被若干有两个的字符包围，如 abcba。

使用 $dp$ 计数。考虑出现次数从大到小转移。设 $dp[i][j][k][u][v]$，表示当前字符出现次数为 $i$，已经使用出现 $i$ 次的字符 $j$ 个，已经使用出现 $i-1$ 次的字符 $k$ 个，有 $u$ 个回文串，$v$ 个非回文串。

• 首先将出现次数为 $1$ 的字符直接算入 $u$ 中，不参与转移，即 $dp[\Sigma+1][0][0][cnt[1]][0]=1$
• $dp[i][j+1][k][u+1][v]+=dp[i][j][k][u][v]$
• $dp[i][j+2][k][u][v+1]+=dp[i][j][k][u][v]*2(cnt[i]-j-1)$
• $dp[i][j+1][k+1][u+1][v]+=dp[i][j][k][u][v]*(cnt[i-1]-k)$
• 这些转移都不难。最后当 $i=2$ 时，要注意记录用来包围 $u$ 的字符
• 最后所有 $u+v$ 可任意排列

其中 $i,j$ 可滚动。时间复杂度 $O(\Sigma^{4})$。