[NOI2009]管道取珠

NOI dp

题目链接： [NOI2009]管道取珠

题目大意：

有两个管道，管道 $A$ 中有 $n$ 个小球，管道 $B$ 中有 $m$ 个小球，每个小球都为白色或黑色。
每次可以从任一管道取第一个小球，进行 $n+m$ 次操作后形成一个长为 $n+m$ 的序列，不同的操作方式可能会得到相同的序列。
设有 $a[i]$ 种操作方式可以得到第 $i$ 个序列，求 $\sum_{i=1}^n a[i]^2$。

解题思路：

这题最主要的是明白 $a[i]^2$ 相当于有两套管道分别进行操作，最后得到相同的序列 $i$ 的方案数。
byvoid 证明：

已知：
X,Y分别为一个取珠方法，某个输出序列S的取珠方法数为a[i]。求证：a[i]2是输出序列为S的有序对(X,Y)的数量。

证明：
设Z为输出序列为S的取珠方法。Z的数量|Z| = a[i]。(X,Y)是一个有序对，且X与Y相互独立，所以X可以有|Z|种取值。对于X的某个特定取值，Y都有|Z|种取值。根据分步计数原理，有序对(X,Y)的取值有|Z|2 = a[i]2种，命题得证。

设 $f[i][j][k][l]$ 为第一套管道分别取到第 $i$ 和第 $j$ 个数，第二套管道分别取到第 $k$ 和第 $l$ 个数时的方案数，
可以得到

if(A[i+1]==A[k+1]) f[i+1][j][k+1][l]+=f[i][j][k][l];
if(A[i+1]==A[l+1]) f[i+1][j][k][l+1]+=f[i][j][k][l];
if(A[j+1]==A[k+1]) f[i][j+1][k+1][l]+=f[i][j][k][l];
if(A[j+1]==A[l+1]) f[i][j+1][k][l+1]+=f[i][j][k][l];

代码实现

挖个坑，之后再补吧