以HDU 2089 不要62 为例的数位DP小结

题意不多说,不知道自己去看http://acm.hdu.edu.cn/showproblem.php?pid=2089

 

HDU 6156 Palindrome Function 数位DP

 问题主要是求$k$进制下小于等于$n$的回文串的个数。

用$dp[base][start][cur]$表示在base进制下,从第start位开始填写,当前填到了第cur位,往后继续填能构成回文的方案数。如果填写的长度超过了一半,就不需要继续DFS了。

 

HDU 6155 Subsequence Count 线段树维护矩阵DP转移

http://acm.hdu.edu.cn/showproblem.php?pid=6155

给一个01序列,有区间反转操作,询问区间内本质不同的子序列的个数 $%10^9+7$

写出dp转移方程,用$dp[i][j]$表从起点到第$i$个点,最后一位是$j$的方案数。

当第$i$位是$0$的时候:

$$dp[i][0] = dp[i-1][0] + dp[i-1][1] + 1$$

$$dp[i][1] = dp[i-1][1] $$

当第$i$位是$1$的时候:

$$dp[i][0] = dp[i-1][0] $$

$$dp[i][1] = dp[i-1][0] + dp[i-1][1] + 1$$

写成矩阵的形式进行转移

如果这一位是$0$

$$\begin{bmatrix} dp[i+1][0]\\ dp[i+1][1]\\1 \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1\\ 0 & 1 &0\\0 & 0 & 1 \end{bmatrix}\begin{bmatrix} dp[i][0]\\ dp[i][1]\\1 \end{bmatrix}$$

如果这一位是$1$

$$\begin{bmatrix} dp[i+1][0]\\ dp[i+1][1]\\1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0\\ 1 & 0 &0\\0 & 0 & 1 \end{bmatrix}\begin{bmatrix} dp[i][0]\\ dp[i][1]\\1 \end{bmatrix}$$

可以用线段树维护任意区间内的转移方程。

考虑反转,会发现把$0$矩阵交换$r_1,r_2$和$c_1,c_2$就能变成$1$矩阵,反之亦然。令$T=\begin{bmatrix} 0 & 1& 0\\ 1 & 0 &0\\0 & 0 & 1 \end{bmatrix}$,可知$TT=E$

交换行,可以在矩阵前乘以个 $T$,交换列,可以在矩阵后乘以一个$T$。假设$C=AB$ ,那么$TCT = TABT = TATTBT$。意味着,进行区间反转的时候,将维护的转移矩阵进行交换行列就好了,并打上延时标记。

 

HDU 6153 A Secret KMP计数

http://acm.hdu.edu.cn/showproblem.php?pid=6153

给定两个串$s_1$,$s_2$,求$s_2$的每一个后缀在$s_1$中出现的次数$\times$长度的和。

将$s_1$,$s_2$进行反转,就变成了求$s_2$的每一个前缀在$s_1$中出现的次数$\times$长度的和。处理出$s_2$的next数组,用$s_2$对$s_1$进行匹配,假设$s_2[j]$和$s_1[i]$匹配上了,那么新出现的前缀就有$s_2[j],s_2[next[j]],s_2[next[next[j]],……$。但是并不能在匹配的过程中进行next跳转计数,会超时的。可以记录每个匹配长度值出现的次数,那么如果前缀$j$出现过,那么前缀$next[j]$也一定出现过。匹配完后,cnt[next[j]] += cnt[j]即可算出每个前缀出现的次数。

HDU6158 The Designer 笛卡尔定理 递推

http://acm.hdu.edu.cn/showproblem.php?pid=6158

 

一个大圆$O_1$和三个小圆$O_2、O_3、O_4$内切,三个小圆相互外切,他们的半径满足如下等式:
$$(\frac{1}{r_2} + \frac{1}{r_3} + \frac{1}{r_4} - \frac{1}{r_1})^2 = 2(\frac{1}{r^2_1}+\frac{1}{r^2_2}+\frac{1}{r^2_3}+\frac{1}{r^2_4})$$

计算有标号圆的面积。
设大圆半径为$r_a$,左边的圆半径为$r_b$。则$r_1 = r_a - r_b$
只看上半部分的圆,对圆重新编号为1、2、3、……
$r_1 = r_a - r_b$
设第$k$个圆的半径为$r_k$,根据笛卡尔定理有如下等式
$$(\frac{1}{r_k}+\frac{1}{r_{k+1}}+\frac{1}{r_b}-\frac{1}{r_a})^2= 2(\frac{1}{r^2_k}+\frac{1}{r^2_{k+1}}+\frac{1}{r^2_b}+\frac{1}{r^2_a})$$
同时也有
$$(\frac{1}{r_k}+\frac{1}{r_{k-1}}+\frac{1}{r_b}-\frac{1}{r_a})^2= 2(\frac{1}{r^2_k}+\frac{1}{r^2_{k-1}}+\frac{1}{r^2_b}+\frac{1}{r^2_a})$$
上下两式相减,得到
$$(\frac{1}{r_{k+1}}-\frac{1}{r_{k-1}})(\frac{2}{r_k}+\frac{1}{r_{k+1}}+\frac{1}{r_{k-1}}+\frac{2}{r_b}-\frac{2}{r_a})=
2(\frac{1}{r^2_{k+1}} - \frac{1}{r^2_{k-1}})
$$
将右边展开,得到
$$(\frac{1}{r_{k+1}}-\frac{1}{r_{k-1}})(\frac{2}{r_k}+\frac{1}{r_{k+1}}+\frac{1}{r_{k-1}}+\frac{2}{r_b}-\frac{2}{r_a})=
2(\frac{1}{r_{k+1}}-\frac{1}{r_{k-1}})(\frac{1}{r_{k+1}}+\frac{1}{r_{k-1}})
$$
两边同时消去$(\frac{1}{r_{k+1}}-\frac{1}{r_{k-1}})$,得到
$$
\frac{2}{r_k}+\frac{1}{r_{k+1}}+\frac{1}{r_{k-1}}+\frac{2}{r_b}-\frac{2}{r_a}=
\frac{2}{r_{k+1}}+\frac{2}{r_{k-1}}
$$
合并同类项,得到
$$\frac{2}{r_k}+\frac{2}{r_b}-\frac{2}{r_a}=\frac{1}{r_{k+1}}+\frac{1}{r_{k-1}}$$
移项得到
$$
\frac{1}{r_{k+1}}=\frac{2}{r_k}+\frac{2}{r_b}-\frac{2}{r_a}-\frac{1}{r_{k-1}}
$$
这是一个关于$r_k$的递推式,知道前两项就能递推出后一项。
但是现在只知道$r_1、r_a、r_b$,还不知道$r_2$,无法进行递推。
根据笛卡尔定理有
$$(\frac{1}{r_1} + \frac{1}{r_2} + \frac{1}{r_b} - \frac{1}{r_a})^2 = 2(\frac{1}{r^2_1}+\frac{1}{r^2_2}+\frac{1}{r^2_b}+\frac{1}{r^2_a})$$
将其左右展开有
$$
\frac{1}{r^2_2} + 2 \times \frac{1}{r_2}(\frac{1}{r_1} + \frac{1}{r_b} - \frac{1}{r_a}) =
2 \times \frac{1}{r^2_2} + 2(\frac{1}{r^2_1}+\frac{1}{r^2_b}+\frac{1}{r^2_a})
$$
移项合并同类型,得到如下
$$
\frac{1}{r^2_2} - 2(\frac{1}{r_1} + \frac{1}{r_b} - \frac{1}{r_a})\frac{1}{r_2} +2(\frac{1}{r^2_1}+\frac{1}{r^2_b}+\frac{1}{r^2_a}) = 0
$$
将$\frac{1}{r_2}$看作未知量,根据实际情况,方程的两个根应该相同,所以根据韦达定理有
$$
\frac{1}{r_2} + \frac{1}{r_2} = 2(\frac{1}{r_1} + \frac{1}{r_b} - \frac{1}{r_a})
$$

$$
\frac{1}{r_2} = \frac{1}{r_1} + \frac{1}{r_b} - \frac{1}{r_a}
$$
已经求得$r_1$和$r_2$,可以进行递推