CSP模拟50联测12 T2 赌神
Ps:超链接为衡水中学OJ。
思路
\(subtask2\)：
由于\(x_i\)较小，考虑 dp。
假设一开始球的颜色为红和蓝，设 \(dp[i][j]\) 为剩 \(i\) 个红球，\(j\) 个蓝球时可获得的最大筹码数。
如果不同球掉落所获得的筹码不同，那么肯定会掉落最少筹码的那一堆球。所以保证各堆获得筹码相同时最优。
设蓝球堆放\(x\)个筹码，红球堆放\(y\)个筹码，则有：
易得每次把筹码投完比不投优。可得：
解 \(x\) 得：\(x=\frac{dp[i][j-1]}{dp[i-1][j]+dp[i][j-1]}\)
所以
\(subtask3\)：
任然考虑 \(n=2\) 的情况，设 \(f[i][j]=\frac{dp[i][j]}{2^{i+j}}\)。
将 \(dp[i][j]\) 通过 \(subtask2\) 中的方程化简，得：
同时取倒数，并裂项得：
不难发现 \(f[i][j]\) 为在二维平面内由 \((0,0)\) 走向 \(i,j\) 的方案数，所以 \(f[i][j]=\dbinom{i+j}{i}\)。
\(subtask4\)
其实 \(n>2\) 时也有上述性质，那么 \(f(x_1,x_2,\cdots,x_n)\) 为 \(n\) 维平面内从 \((0,0,0,\cdots,0)\) 走到 \((x_1,x_2,\cdots,x_n)\) 的方案数。
那么\(f(x_1,x_2,\cdots,x_n)=\dbinom{\sum_{i=1}^n x_i}{x_n}*\dbinom{\sum_{i=1}^{n-1}x_i}{x_{n-1}}*\cdots*\dbinom{x_1}{x_1}\)。
展开，得：
发现每一项的分子与后一项的分母都存在共同部分，再次化简，得：
于是答案为 \(\frac{n^{x_1+x_2+\cdots+x_n}}{f(x_1,x_2,\cdots,x_n)}\)。