题号 NC17621
名称 管道取珠
来源 NOI2009比赛真题
戳我进入往期每日一题汇总贴~
往期每日一题题单

如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情

题解

这个题的难点或者说关键点究竟在哪里呢？
——弄清楚究竟是什么意思！因为是肯定不能直接算的！（我们考虑把数学式子弄出一个物理意义或者说实际操作的意义）
表示：如果有两个相同的装置同时进行取珠子的操作，两个装置取得相同的序列的方案数有多少。
想想哈：ai是组成第i个序列的方案数，那么 是两个装置都取得第i个序列的方案数是理所当然的哈！
这样就简单了，f[i][j][k] 表示已经取了i个珠子，第一个装置第一行取了j个，第二个
装置第一行取了k个，所得到的序列是一样的的方案数，转移方程显而易见， 注意，由于空间限制要01滚动的……
转移方程如下：
if (j > 0 && k > 0 && a[j] == a[k]) f[i%2][j][k] += f[(i-1)%2][j-1][k-1];
if (b[i-j] == b[i-k]) f[i%2][j][k] += f[(i-1)%2][j][k];
if (j > 0 && a[j] == b[i-k]) f[i%2][j][k] += f[(i-1)%2][j-1][k];
if (k > 0 && b[i-j] == a[k]) f[i%2][j][k] += f[(i-1)%2][j][k-1];
（这种思路在当年noi之后就成为了套路……但是第一次见真的很难想到。）

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目6月5日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴