题解 P1758 【管道取珠】
这是一道DP神题,直到我写下这句题解时也没有想明白……
首先，这道题要我们求所有（不同输出序列的方案数）的平方和，于是我们当然就想到求所有不同输出序列的方案数……（大雾） 。这道题一个巧妙的地方就在于对问题的转化。（以下摘自BYVoid大神的题解）
假设同时有两个人X & Y在玩这个游戏，设X从up取了i个珠子（不一定连续），从down取了j个珠子，取出来的珠子组成的序列为Q，操作序列为x，Y从up取了k个珠子，从down取了l个珠子，取出来的珠子组成的序列也为Q，操作序列为y，那么我们就得到了一个有序对（x，y），f[i][j][k][l]即表示有序对（x，y）的数量。两个有序对不相同当且仅当x和y不同时相同。
下面证明f[i][j][k][l]即为所求。
已知：取出珠子的序列为Q，x和y分别为一种取珠方法（可相同）， 取出Q的方案数为a；
求证：有序对（x，y）的数量等于a^2。
因为取出Q的方案数为a，所以x & y都有a种取值，且x & y彼此独立，故对于x的每一个取值，y都有a种取值，故有序对（x，y）的数量为a^2，命题得证。
博主是个超级大傻*，连空间优化到n^2都不会，请各路大神指教。（然而这道题不优化洛谷过不了，n^3的空间bzoj能过）
bzojAC代码点这里