Advertisement
Guest User

Untitled

a guest
Sep 30th, 2012
158
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.37 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <ctime>
  6. #include <algorithm>
  7. #include <cstring>
  8. #include <vector>
  9. #include <set>
  10. #include <map>
  11. #include <bitset>
  12. #include <queue>
  13. #include <complex>
  14. #include <cassert>
  15.  
  16. using namespace std;
  17.  
  18. #define pb push_back
  19. #define mp make_pair
  20. #define fs first
  21. #define sc second
  22. #define sz(s) int((s).size())
  23. #define eprintf(...) fprintf(stderr, __VA_ARGS__)
  24. #define next _next
  25. #define prev _prev
  26. #define rank _rank
  27.  
  28. typedef long long ll;
  29. typedef long long llong;
  30. typedef unsigned int uint;
  31. typedef unsigned long long ull;
  32. typedef vector <int> vi;
  33. typedef pair <int, int> pii;
  34. typedef complex <double> tc;
  35.  
  36. const int inf = int(1e9);
  37. const double eps = 1e-9;
  38. const double pi = 4 * atan(double(1));
  39.  
  40. long double d[555][555];
  41.  
  42. int main(){
  43.     //freopen("input.txt", "r", stdin);
  44.     //freopen("output.txt", "w", stdout);
  45.     freopen("runs.in", "r", stdin);
  46.     freopen("runs.out", "w", stdout);
  47.     int n, k;
  48.     scanf("%d %d", &n, &k);
  49.     if(k >= n){
  50.         printf("0\n");
  51.         return 0;
  52.     }
  53.     for(int i = 1; i <= n; i++){
  54.         for(int j = 0; j <= min(i - 1, k); j++){
  55.             if(i == 1 && j == 0){
  56.                 d[i][j] = 1;
  57.             }
  58.             else{
  59.                 d[i][j] = (j * d[i - 1][j] + 2 * (j >= 1 ? d[i - 1][j - 1] : 0) + (i - j) * (j >= 2 ? d[i - 1][j - 2] : 0)) / i;
  60.             }
  61.         }
  62.     }
  63.     printf("%.9Lf\n", d[n][k]);
  64.     return 0;
  65. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement