做题感悟:感觉自己还是太水,代码水平有待提高,现在越来越感觉codeforces 的题目很好,以后决定每周刷两套codeforces的题目,希望能坚持下来,扯的有点远了。
解题思路:
这题诈一看貌似大叔级别的题目,其实不然,细心观察你会发现,最大点无非是 1 ,2……m ,只要分别算出各个最大点有多少个就可以了。
最大点 | 个数 |
1 | 1^n |
2 | 2^n - 1^n |
k | k^n - (k-1)^n |
m | m^n - (m-1)^n |
总的方法数为 m^n ,n个位置都可以有m 种放置方法,so~> p = ( 1^n + (2^n - 1) * 2 + (3^n - 2^n ) * 3 + ……(k^n - (k-1)^n) * k ……(m^n - (m-1)^n) * m ) / (m^n) 化简一下就可以得到: p = m - (pow(1/m , n ) - pow(2/m , n) - pow(3/m ,n ) ……pow(k/m ,n) - pow((m-1)/m
,n) ;
代码:
#include<iostream> #include<fstream> #include<iomanip> #include<ctime> #include<fstream> #include<sstream> #include<stack> #include<cstring> #include<cmath> #include<map> #include<vector> #include<cstdio> #include<algorithm> #define INT long long int using namespace std ; const double esp = 0.00000001 ; const int INF = 1000000000 ; const int MY = 20 ; const int MX = (1<<17) + 10 ; int main() { double n ,m ; while(~scanf("%lf%lf" ,&m ,&n)) { double p = m ; for(int i = 1 ;i < m ;i++) { double j = i ; p -= pow(j/m ,n) ; } cout<<fixed<<setprecision(10)<<p<<endl ; } return 0 ; }