QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#363889#8511. Greek Casinoucup-team2000#WA 2ms6004kbC++201.8kb2024-03-24 04:54:372024-03-24 04:54:37

Judging History

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

  • [2024-03-24 04:54:37]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:6004kb
  • [2024-03-24 04:54:37]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
#define f first
#define s second
#define lep(i,a,b) for (int i=(a); i <= (b); i++)
#define rep(i,b,a) for (int i = (b); i >= (a); i--)

typedef long double D;

const int maxn = 2e5 + 5;
D dp[maxn];
vector<int> divs[maxn];

// dp[i] = sum_j{ P(i->j) * (1+dp[j])}
// = sum_{div}sum_{j} ( P(i->j | div) * (1 + dp[j]))
// lcm(a,b) = ab / gcd(a,b)
// lcm / gcd needs to be coprime with a

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    lep(i,1,n) {
      for (int j = i; j <= n; j += i) divs[j].pb(i);
    }
    int totW = 0;
    vector<int> W(n+1);
    lep(i,1,n) {
      cin >> W[i];
      totW += W[i];
    }
    rep(i,n,1) {
      D num = 0;
      int p_i = 0;
      for (int d: divs[i]) {
        p_i += W[d];
      }
      for (int j = 2 * i; j <= n; j += i) {
        D prob = 0;
        for (int d: divs[i]) {
          if (__gcd(j/d,i/d)==1) {
            prob+= W[d * (j/i)];
          }
        }
        num += D(prob) * (D(1) + dp[j]);
      }
      num += D(p_i);
      D den = D(totW - p_i);
      dp[i] = num / den;
      // map<int,int> probs;
      // for (int d: divs[i]) {
      //   p_i += W[i]; // pick any divisor, gcd will be the same
      //   for (int j = 2 * i; j <= n; j += i) {
      //     if (__gcd(j/d,a/d) == 1) {
      //       // ab / gcd = j
      //       // b = j * gcd / a
      //       probs[j] += W[j * d / i];
      //     }
      //   }
      // }
      // // dp[i] = p_i(1 + dp[i]) + sum_j p[j](1 + dp[j])
      // // c dp[i] = d
      // int c = (1 - p_i);
      // int d

    }
    cout << fixed << setprecision(12) << dp[1] << "\n";

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5828kb

input:

3
1 1 1

output:

3.500000000000

result:

ok found '3.500000000', expected '3.500000000', error '0.000000000'

Test #2:

score: 0
Accepted
time: 1ms
memory: 5812kb

input:

3
1 1 2

output:

3.666666666667

result:

ok found '3.666666667', expected '3.666666667', error '0.000000000'

Test #3:

score: -100
Wrong Answer
time: 2ms
memory: 6004kb

input:

1337
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

1.010368266826

result:

wrong answer 1st numbers differ - expected: '1.0183368', found: '1.0103683', error = '0.0078251'