UVa1305/LA2522 Chocolate题目链接题意输入格式输出格式分析AC 代码题目链接本题是2002年icpc亚洲区域赛北京赛区的A题题意在2100年ACM巧克力将成为世界上最受欢迎的食物之一。“绿色、橙色、棕色、红色……”色彩鲜艳的糖衣外壳也许是ACM巧克力最吸引人的特点。你见过多少种颜色如今据说ACM从二十四色的调色板中挑选颜色用来涂装他们美味的小糖果块。一天Sandy在一大包包含五种颜色绿色、橙色、棕色、红色和黄色的ACM巧克力上玩了一个游戏。每次他从包装中取出一块巧克力放在桌子上。如果桌子上有两块颜色相同的巧克力他就把这两块都吃掉。他发现一个很有趣的现象大多数时候桌子上总是有2块或3块巧克力。现在问题来了如果包装中有C种颜色的ACM巧克力各颜色均匀分布在从包装中取出N块巧克力后桌子上恰好有M块巧克力的概率是多少请你编写一个程序来计算。输入格式本问题的输入文件包含若干测试用例每行一个。每个测试用例包含三个非负整数CC ≤ 100、N和MN, M ≤ 1000000。输入以单独一行包含一个零结束。输出格式每行输出一个实数表示每个用例的概率结果四舍五入保留三位小数。分析本题从概率转化的角度很自然地就能想到( C 1 ) × ( C 1 ) (C1)\times(C1)(C1)×(C1)的转化矩阵为∣ 0 1 0 0 ⋯ 0 1 C 0 C − 1 C 0 ⋯ 0 ⋱ ⋱ ⋱ ⋱ ⋱ ⋮ 0 0 ⋯ 0 C − 1 C 0 ∣ \begin{vmatrix} 0 1 0 0 \cdots 0\\ \frac{1}{C} 0 \frac{C-1}{C} 0 \cdots 0\\ \ddots \ddots \ddots \ddots \ddots \vdots\\ 0 0 \cdots 0 \frac{C-1}{C} 0 \end{vmatrix}0C1⋱010⋱00CC−1⋱⋯00⋱0⋯⋯⋱CC−100⋮0对于本题C ≤ 100 、 N ≤ 1000000 C ≤ 100、N ≤ 1000000C≤100、N≤1000000的规模用矩阵快速幂来做足以 AC 。当然如果追求极致效率其实可以推导出通项公式的。AC 代码#includeiostream#includeiomanipusingnamespacestd;#defineC101doublea[C][C],b[C][C],t[C][C];intc,n,m;voidmul(double(a)[C][C],constdouble(b)[C][C]){for(inti0;ic;i)for(intj0;jc;j){t[i][j]0.;for(intk0;kc;k)t[i][j]a[i][k]*b[k][j];}for(inti0;ic;i)for(intj0;jc;j)a[i][j]t[i][j];}voidpow(intx){while(x){if(x1)mul(b,a);mul(a,a);x1;}}doublesolve(){cinnm;if(mc||(m^n)1)return0.;for(inti0;ic;i){if(ic)a[i1][i](i1.)/c;if(i)a[i-1][i](c-i1.)/c;for(intj0;jc;j)if(abs(i-j)!1)a[j][i]0.;}for(inti0;ic;i)for(intj0;jc;j){b[i][j]0.;for(intk0;kc;k)b[i][j]a[i][k]*a[k][j];}for(intin1;ic;i2)for(intjn1;jc;j2)a[i1][j1]b[i][j];cn1?c11:(c1)1;for(inti0;ic;i)for(intj0;jc;j)b[i][j]ij?1.:0.;pow(n1);returnb[0][m1];}intmain(){coutfixedsetprecision(3);while(cincc)coutsolve()endl;return0;}
UVa1305/LA2522 Chocolate
UVa1305/LA2522 Chocolate题目链接题意输入格式输出格式分析AC 代码题目链接本题是2002年icpc亚洲区域赛北京赛区的A题题意在2100年ACM巧克力将成为世界上最受欢迎的食物之一。“绿色、橙色、棕色、红色……”色彩鲜艳的糖衣外壳也许是ACM巧克力最吸引人的特点。你见过多少种颜色如今据说ACM从二十四色的调色板中挑选颜色用来涂装他们美味的小糖果块。一天Sandy在一大包包含五种颜色绿色、橙色、棕色、红色和黄色的ACM巧克力上玩了一个游戏。每次他从包装中取出一块巧克力放在桌子上。如果桌子上有两块颜色相同的巧克力他就把这两块都吃掉。他发现一个很有趣的现象大多数时候桌子上总是有2块或3块巧克力。现在问题来了如果包装中有C种颜色的ACM巧克力各颜色均匀分布在从包装中取出N块巧克力后桌子上恰好有M块巧克力的概率是多少请你编写一个程序来计算。输入格式本问题的输入文件包含若干测试用例每行一个。每个测试用例包含三个非负整数CC ≤ 100、N和MN, M ≤ 1000000。输入以单独一行包含一个零结束。输出格式每行输出一个实数表示每个用例的概率结果四舍五入保留三位小数。分析本题从概率转化的角度很自然地就能想到( C 1 ) × ( C 1 ) (C1)\times(C1)(C1)×(C1)的转化矩阵为∣ 0 1 0 0 ⋯ 0 1 C 0 C − 1 C 0 ⋯ 0 ⋱ ⋱ ⋱ ⋱ ⋱ ⋮ 0 0 ⋯ 0 C − 1 C 0 ∣ \begin{vmatrix} 0 1 0 0 \cdots 0\\ \frac{1}{C} 0 \frac{C-1}{C} 0 \cdots 0\\ \ddots \ddots \ddots \ddots \ddots \vdots\\ 0 0 \cdots 0 \frac{C-1}{C} 0 \end{vmatrix}0C1⋱010⋱00CC−1⋱⋯00⋱0⋯⋯⋱CC−100⋮0对于本题C ≤ 100 、 N ≤ 1000000 C ≤ 100、N ≤ 1000000C≤100、N≤1000000的规模用矩阵快速幂来做足以 AC 。当然如果追求极致效率其实可以推导出通项公式的。AC 代码#includeiostream#includeiomanipusingnamespacestd;#defineC101doublea[C][C],b[C][C],t[C][C];intc,n,m;voidmul(double(a)[C][C],constdouble(b)[C][C]){for(inti0;ic;i)for(intj0;jc;j){t[i][j]0.;for(intk0;kc;k)t[i][j]a[i][k]*b[k][j];}for(inti0;ic;i)for(intj0;jc;j)a[i][j]t[i][j];}voidpow(intx){while(x){if(x1)mul(b,a);mul(a,a);x1;}}doublesolve(){cinnm;if(mc||(m^n)1)return0.;for(inti0;ic;i){if(ic)a[i1][i](i1.)/c;if(i)a[i-1][i](c-i1.)/c;for(intj0;jc;j)if(abs(i-j)!1)a[j][i]0.;}for(inti0;ic;i)for(intj0;jc;j){b[i][j]0.;for(intk0;kc;k)b[i][j]a[i][k]*a[k][j];}for(intin1;ic;i2)for(intjn1;jc;j2)a[i1][j1]b[i][j];cn1?c11:(c1)1;for(inti0;ic;i)for(intj0;jc;j)b[i][j]ij?1.:0.;pow(n1);returnb[0][m1];}intmain(){coutfixedsetprecision(3);while(cincc)coutsolve()endl;return0;}
