CSP模拟50联测12 T2 赌神
Ps:超链接为衡水中学OJ。
思路
\(subtask2\)：
由于\(x_i\)较小，考虑 dp。
假设一开始球的颜色为红和蓝，设 \(dp[i][j]\) 为剩 \(i\) 个红球，\(j\) 个蓝球时可获得的最大筹码数。
如果不同球掉落所获得的筹码不同，那么肯定会掉落最少筹码的那一堆球。所以保证各堆获得筹码相同时最优。
设蓝球堆放\(x\)个筹码，红球堆放\(y\)个筹码，则有：
\[dp[i][j]=2x*dp[i-1][j]=2y*dp[i][j-1] \ \ (n=2) \]易得每次把筹码投完比不投优。可得：
\[y=1-x\\ x*dp[i-1][j]=(1-x)dp[i][j-1] \]解 \(x\) 得：\(x=\frac{dp[i][j-1]}{dp[i-1][j]+dp[i][j-1]}\)
所以
\[dp[i][j]=2x*dp[i-1][j]=\frac{2dp[i][j-1]dp[i-1][j]}{dp[i][j-1]+dp[i-1][j]} \]\(subtask3\)：
任然考虑 \(n=2\) 的情况，设 \(f[i][j]=\frac{dp[i][j]}{2^{i+j}}\)。
将 \(dp[i][j]\) 通过 \(subtask2\) 中的方程化简，得：
\[f[i][j]=\frac{f[i-1][j]f[i][j-1]}{f[i][j-1]+f[i-1][j]} \]同时取倒数，并裂项得：
\[\frac{1}{f[i][j]}=\frac{f[i][j-1]+f[i-1][j]}{f[i-1][j]f[i][j-1]}=\frac{1}{f[i][j-1]}+\frac{1}{f[i-1][j]} \]不难发现 \(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}\)。
展开，得：
\[f(x_1,x_2,\cdots,x_n)=\frac{\sum_{i=1}^n x_i}{x_n!\sum_{i=1}^{n-1}x_i}*\frac{\sum_{i=1}^{n-1} x_i}{x_{n-1}!\sum_{i=1}^{n-2}x_i}*\cdots*1 \]发现每一项的分子与后一项的分母都存在共同部分，再次化简，得：
\[f(x_1,x_2,\cdots,x_n)=\frac{(\sum_{i=1}^n x_i)!}{\prod_{i=1}^n x_i!} \]于是答案为 \(\frac{n^{x_1+x_2+\cdots+x_n}}{f(x_1,x_2,\cdots,x_n)}\)。
标签：12,frac,dbinom,筹码,sum,T2,cdots,赌神,dp From： https://www.cnblogs.com/binbinbjl/p/17757312.html