fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. double prob[2][100047];
  5. double sprob[100047];
  6.  
  7. int main() {
  8. int N, M; cin >> N >> M;
  9. if (M == 1) { cout << "1" << endl; return 0; }
  10. vector<int> K(N);
  11. int Krank = 0;
  12. for (int &k:K) { cin >> k; Krank += k; }
  13. prob[0][0] = 1;
  14. for (int n=0; n<N; ++n) {
  15. int prev=n&1, curr=1-prev;
  16. sprob[0]=0;
  17. for (int i=0; i<=Krank; ++i) sprob[i+1] = sprob[i] + prob[prev][i];
  18. for (int i=0; i<=Krank; ++i) {
  19. prob[curr][i] = sprob[i] - (i-M >= 0 ? sprob[i-M] : 0) - (i-K[n] >= 0 ? prob[prev][i-K[n]] : 0);
  20. prob[curr][i] /= M-1;
  21. }
  22. }
  23. double better = 0;
  24. for (int i=1; i<Krank; ++i) better += prob[N&1][i];
  25. better *= M-1;
  26. cout << fixed << setprecision(15) << (better+1) << endl;
  27. }
Success #stdin #stdout 0s 5760KB
stdin
4 10
2
1
2
1
stdout
1.000000000000000