http://acm.hdu.edu.cn/showproblem.php?pid=5159
考虑没一个数的贡献，一个数一次都不出现的次数是(x-1)^b,而总的排列次数是x^b，所以每一个数有贡献的次数都是x^b-(x-1)^b，所以最后推导的公式就是：
(x^b-(x-1)^b)*(1+2+...+x)/(x^b)=(1-((x-1)/x)^b)*(1+x)*x/2
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 typedef long long LL; 7 8 int x,b; 9 10 int main(){ 11 int tc,kase=0; 12 scanf("%d",&tc); 13 while(tc--){ 14 scanf("%d%d",&x,&b); 15 double tmp=(x-1)*1.0/x; 16 tmp=pow(tmp,b*1.0); 17 tmp=1-tmp; 18 double sum=1.0*(1+x)*x/2; 19 tmp*=sum; 20 printf("Case #%d: %.3lf\n",++kase,tmp); 21 } 22 return 0; 23 }
计数问题如果规模很大的话，可以考虑每个个体的贡献，或者是和的贡献等等。
原文：http://www.cnblogs.com/fenice/p/5447802.html