ulvis.paste.net

Paste Search Dynamic
Recent pastes
solve
  1. #include <bits/stdc++.h>
  2. #include <experimental/optional>
  3. using namespace std;
  4. using namespace std::experimental;
  5.  
  6. #define all(v) v.begin(), v.end()
  7. #define db(x) cout << #x << " = " << (x) << endl
  8. #define fend(x) ((x) & ((x) + 1)) - 1
  9. #define fenu(x) (x) | ((x) + 1)
  10. #define forn(i, n) for (int i = 0; i < (int)(n); ++i)
  11. #define nrof(i, n) for (int i = (int)(n)-1; i >= 0; --i)
  12. #define forr(i, b, e) for (int i = b; i < (int)e; ++i)
  13. #define ft first
  14. #define len(s) s.length()
  15. #define mp make_pair
  16. #define pob pop_back
  17. #define pof pop_front
  18. #define pub push_back
  19. #define puf push_front
  20. #define sc second
  21.  
  22. typedef double dbl;
  23. typedef long double ldbl;
  24. typedef unsigned int uint;
  25. typedef long long ll;
  26. typedef unsigned long long ull;
  27.  
  28. template <typename T>
  29. using vec = std::vector<T>;
  30.  
  31. const long long MILLER_RABIN = 3215031751;
  32. const long double PI = acos(-1);
  33.  
  34. #if __cplusplus >= 201103L
  35.  
  36. #include <ext/pb_ds/assoc_container.hpp>
  37. #include <ext/pb_ds/tree_policy.hpp>
  38. using namespace __gnu_pbds;
  39. template <typename T>
  40. using ordered_set =
  41.     tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  42.  
  43. struct ConfigIO {
  44.   ConfigIO() {
  45.     cin.tie(nullptr);
  46.     cout.tie(nullptr);
  47.     ios_base::sync_with_stdio(false);
  48.   }
  49. } cnf_io;
  50.  
  51. // struct config_rand {
  52. //    config_rand() {
  53. //        srand(chrono::duration_cast<chrono::nanoseconds>(
  54. //                chrono::high_resolution_clock::now().time_since_epoch()).count());
  55. //    }
  56. //} cnf_rand;
  57.  
  58. namespace std {
  59. template <>
  60. struct hash<pair<int, int>> {
  61.   size_t operator()(const pair<int, int>& x) const {
  62.     return (x.first * 71ull + x.second) % ((int)1e9 + 7);
  63.   }
  64. };
  65.  
  66. template <>
  67. struct hash<vector<int>> {
  68.   size_t operator()(const vector<int>& v) const {
  69.     size_t hsh = 0;
  70.     for (int i = 0; i < v.size(); ++i) {
  71.       hsh = (hsh * 71ull + v[i]) % (int)(1e9 + 7);
  72.     }
  73.     return hsh;
  74.   }
  75. };
  76. }  // namespace std
  77.  
  78. // __builtin_popcount(x) - Returns the number of 1-bits in x.
  79. // __builtin_parity(x) - Returns the parity of x, i.e. the number of 1-bits in x
  80. // modulo 2.
  81. // __builtin_ffs(x) - Returns one plus the index of the least significant 1-bit
  82. // of x, or if x is zero, returns zero.
  83. // __builtin_clz(x) - Returns the number of leading 0-bits in x, starting at the
  84. // most significant bit position. If x is 0, the result is undefined.
  85. // __builtin_ctz(x) - Returns the number of trailing 0-bits in x, starting at
  86. // the least significant bit position. If x is 0, the result is undefined.
  87.  
  88. // inline string tobin(long long x) { bitset<63>(x).to_string(); }
  89.  
  90. template <class T>
  91. void Trace(T collection) {
  92.   for (auto elem : collection) {
  93.     cout << elem << " ";
  94.   }
  95.   cout << endl;
  96. }
  97.  
  98. int GetRand() {
  99.   static mt19937_64 gen;
  100.   static uniform_int_distribution<int> dis;
  101.   return dis(gen);
  102. }
  103.  
  104. #endif
  105.  
  106. struct Pair {
  107. #define __TYPE__ int
  108.   __TYPE__ x, y;
  109.  
  110.   Pair() {
  111.   }
  112.  
  113.   Pair(__TYPE__ _x, __TYPE__ _y) : x(_x), y(_y) {
  114.   }
  115.  
  116.   friend __TYPE__ Cross(const Pair& p1, const Pair& p2) {
  117.     return p1.x * p2.y - p1.y * p2.x;
  118.   }
  119.  
  120.   friend __TYPE__ Dot(const Pair& p1, const Pair& p2) {
  121.     return p1.x * p2.x + p1.y * p2.y;
  122.   }
  123.  
  124.   friend bool operator<(const Pair& p1, const Pair& p2) {
  125.     return p1.x > p2.x || (p1.x == p2.x && p1.y < p2.y);
  126.   }
  127.  
  128.   friend bool operator==(const Pair& p1, const Pair& p2) {
  129.     return p1.x == p2.x && p1.y == p2.y;
  130.   }
  131.  
  132.   struct Hasher {
  133.     size_t operator()(const Pair& p) const {
  134.       return p.x * 1234567ULL + p.y;
  135.     }
  136.   };
  137. };
  138.  
  139. template <typename T>
  140. inline T& RD(T& x) {
  141.   char c;
  142.   while (!isdigit(c = getchar()))
  143.     ;
  144.   x = c - '0';
  145.   while (isdigit(c = getchar()))
  146.     x = x * 10 + c - '0';
  147.   return x;
  148. }
  149.  
  150. template <typename _Type>
  151. void print(_Type arg) {
  152.   cout << arg << endl;
  153. }
  154.  
  155. template <typename _Type, typename... _Args>
  156. void print(_Type first_arg, _Args&&... args) {
  157.   cout << first_arg << " ";
  158.   print(std::forward<_Args>(args)...);
  159. }
  160.  
  161. template <typename _Type>
  162. void scan(_Type& arg) {
  163.   cin >> arg;
  164. }
  165.  
  166. template <typename _Type, typename... _Args>
  167. void scan(_Type& first_arg, _Args&&... args) {
  168.   cin >> first_arg;
  169.   scan(std::forward<_Args>(args)...);
  170. }
  171.  
  172. template <typename Out>
  173. void split(const std::string& s, char delim, Out result) {
  174.   std::stringstream ss(s);
  175.   std::string item;
  176.   while (std::getline(ss, item, delim)) {
  177.     *(result++) = item;
  178.   }
  179. }
  180.  
  181. std::vector<std::string> split(const std::string& s, char delim) {
  182.   std::vector<std::string> elems;
  183.   split(s, delim, std::back_inserter(elems));
  184.   return elems;
  185. }
  186.  
  187. class Solution {
  188.  public:
  189.   void Solve() {
  190.     static const int ML=5000;
  191.     int n;
  192.     cin>>n;
  193.     vec<vec<long double>> P(ML, vec<long double>(ML,0));
  194.     forn(i,ML) P[i][0]=0;
  195.     P[0][0]=1;
  196.     forr(i,1,ML){
  197.       forr(j,1,ML){
  198.         P[i][j]=(P[i-1][j]*j)/n + (P[i-1][j-1]*(n-j+1))/n;
  199.       }
  200.     }
  201.     double ans = 0;
  202.     forr(i,1,ML) ans+=i*(P[i][n]-P[i-1][n]);
  203.     cout<<ans<<endl;
  204.     //forr(i,0,ML)cout<<P[i][n]<<endl;
  205.   }
  206.  
  207.  private:
  208.   void Read() {
  209.   }
  210. };
  211.  
  212. int main() {
  213. #ifdef HOME
  214.   freopen("home.in", "r", stdin);
  215.   freopen("home.out", "w", stdout);
  216. #endif
  217.  
  218.   int tests = 20;
  219.   //scan(tests);
  220.   for (int test = 1; test <= tests; ++test) {
  221.     Solution().Solve();
  222.     // cin.clear();
  223.     // cin.seekg(0, ios::beg);
  224.   }
  225.   return 0;
  226.  
  227. #ifdef HOME
  228.   cout << "\n\nTime: " << clock() / (double)clocks_per_sec << endl;
  229. #endif
  230. }
  231.  
Parsed in 0.034 seconds