QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#277265#6565. Game Show Eliminationucup-team1198#AC ✓362ms54744kbC++144.5kb2023-12-06 17:10:052023-12-06 17:10:06

Judging History

你现在查看的是最新测评结果

  • [2023-12-06 17:10:06]
  • 评测
  • 测评结果:AC
  • 用时:362ms
  • 内存:54744kb
  • [2023-12-06 17:10:05]
  • 提交

answer

#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define int int64_t

const int MAXN = 1e3 + 10, MAXK = 11;

vector<double> p[1 << MAXK][MAXK];

vector<int> operator*(const vector<int>& a, const vector<int>& b) {
  vector<int> c(a.size() + b.size() - 1);
  for (int i = 0; i < (int)a.size(); ++i) {
    for (int j = 0; j < (int)b.size(); ++j) {
      c[i + j] += a[i] * b[j];
    }
  }
  return c;
}

vector<int> operator+(const vector<int>& a, const vector<int>& b) {
  vector<int> c(max(a.size(), b.size()));
  for (int i = 0; i < (int)a.size(); ++i) {
    c[i] += a[i];
  }
  for (int i = 0; i < (int)b.size(); ++i) {
    c[i] += b[i];
  }
  return c;
}

double dp[MAXN][1 << MAXK][MAXK];
double ans[MAXN];

signed main() {
#ifdef DEBUG
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#else
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
#endif

  int n, k;
  cin >> n >> k;

  for (int mask = 0; mask < (1 << (k - 1)); ++mask) {
    for (int d = 0; d < k; ++d) {
      vector<int> a;
      for (int i = 0; i < (k - 1); ++i) {
        if (mask & (1 << i)) {
          a.push_back(i);
        }
      }
      a.push_back(k - 1);
      a.push_back(k + d);
      p[mask][d].resize(k + 1);
      for (int i : a) {
        for (int t = i; t < i + k; ++t) {
          vector<int> prod = {1};
          vector<int> sum = {0};
          int cntk = 0;
          for (int j : a) {
            if (j == i) continue;
            vector<int> up = {-j, 1};
            vector<int> down = {j + k, -1};
            ++cntk;
            if (t >= j + k) {
              up = {1};
              down = {0};
              --cntk;
            } else if (t + 1 <= j) {
              up = {0};
              down = {1};
              --cntk;
            }
            sum = sum * up + prod * down;
            prod = prod * up;
          }
          vector<double> intsum(sum.size() + 1);
          for (int i = 1; i <= (int)sum.size(); ++i) {
            intsum[i] = (double)sum[i - 1] / i;
            for (int t = 0; t < cntk; ++t) {
              intsum[i] /= k;
            }
          }
          double vall = 0, valr = 0;
          for (int i = (int)sum.size(); i >= 0; --i) {
            vall = vall * t + intsum[i];
            valr = valr * (t + 1) + intsum[i];
          }
          p[mask][d][min(i, k)] += (valr - vall) / k;
        }
      }
    }
  }

  /// cerr << "p: " << p[0][0][1] << endl;

  int mask0 = (1 << (k - 1)) - 1;
  if (n - 2 < k - 1) {
    mask0 = ((1 << (n - 2)) - 1) << (k - n + 1);
  }
  dp[n - 2][mask0][0] = 1;
  /// cerr << mask0 << endl;
  for (int mx2 = n - 2; mx2 >= 0; --mx2) {
    for (int mask = (1 << (k - 1)) - 1; mask >= 0; --mask) {
      int cnt = mx2 + 2;
      for (int i = 0; i < (k - 1); ++i) {
        if (mx2 - k + 1 + i < 0) continue;  
        if (!(mask & (1 << i))) {
          --cnt;
        }
      }
      int mx3 = mx2 - k;
      for (int i = 0; i < (k - 1); ++i) {
        if (mask & (1 << i)) {
          mx3 = mx2 - k + 1 + i;
        }
      }
      int start = mx3 - k + 1;
      int mask1 = 0;
      for (int i = start; i < mx3; ++i) {
        if (i < 0) continue;
        if (i <= mx2 - k) {
          mask1 |= (1 << (i - start));
        } else {
          if (mask & (1 << (i - (mx2 - k + 1)))) {
            mask1 |= (1 << (i - start));
          }
        }
      }
      for (int d = 0; d < k; ++d) {
        for (int i = 0; i < (k - 1); ++i) {
          if (mask & (1 << i)) {
            dp[mx2][mask ^ (1 << i)][d] += dp[mx2][mask][d] * p[mask][d][i];
            ans[mx2 - k + 1 + i] += dp[mx2][mask][d] * p[mask][d][i] * (cnt - 1);
          }
        }
        ans[mx2] += dp[mx2][mask][d] * p[mask][d][k - 1] * (cnt - 1);
        ans[mx2 + d + 1] += dp[mx2][mask][d] * p[mask][d][k] * (cnt - 1);
        if (mx3 >= 0) {
          dp[mx3][mask1][min(k - 1, mx2 + d + 1 - mx3 - 1)] += dp[mx2][mask][d] * p[mask][d][k - 1];
          dp[mx3][mask1][min(k - 1, mx2 - mx3 - 1)] += dp[mx2][mask][d] * p[mask][d][k];
        }
      }
    }
  }

  cout << fixed << setprecision(20);
  for (int i = 0; i < n; ++i) {
    cout << 1 + ans[i] << "\n";
  }

  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 5932kb

input:

3 2

output:

2.10937500000000000000
2.62500000000000000000
1.26562500000000000000

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 362ms
memory: 54744kb

input:

1000 10

output:

2.92729331661318248337
3.53731615687861156161
4.28118220331033150217
5.13122066019083966637
6.05393277902175963590
7.01918850987255815710
8.00570239911677461464
9.00129103035629007934
10.00016520768496874894
11.00000000001034017316
12.00000000001135980199
13.00000000001235278546
14.00000000001342037...

result:

ok 1000 numbers

Test #3:

score: 0
Accepted
time: 33ms
memory: 11592kb

input:

300 8

output:

2.75126305133219561938
3.39007372705479870234
4.17500686507974982931
5.06602151944115064452
6.02014655784086905044
7.00455785889803195232
8.00057259306525736520
9.00000000000009414691
10.00000000000012079227
11.00000000000013145041
12.00000000000013500312
13.00000000000015631940
14.00000000000016520...

result:

ok 300 numbers

Test #4:

score: 0
Accepted
time: 5ms
memory: 12092kb

input:

1000 3

output:

2.23025616810293714209
3.03476567111320605363
3.99999999999999511502
4.99999999999999289457
5.99999999999999200639
6.99999999999999023004
7.99999999999998756550
8.99999999999998756550
9.99999999999998401279
10.99999999999998401279
11.99999999999998046007
12.99999999999998223643
13.999999999999978683...

result:

ok 1000 numbers

Test #5:

score: 0
Accepted
time: 245ms
memory: 6968kb

input:

7 10

output:

2.98158643837177361746
3.49360496011804588790
3.96534226491272301374
4.31967705858751038761
4.50872485622269181249
4.49888084765053264391
4.23218357413660939415

result:

ok 7 numbers

Test #6:

score: 0
Accepted
time: 121ms
memory: 30332kb

input:

993 9

output:

2.84112122851619508523
3.46435924464091105079
4.22732436744438011544
5.09694259816773787009
6.03528166580504343841
7.01057424280982743880
8.00238739423920009131
9.00030251838427020061
9.99999999999402078288
10.99999999999335464906
11.99999999999269739703
12.99999999999204369772
13.999999999991409538...

result:

ok 993 numbers