QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#363350#8511. Greek CasinoDays_of_Future_Past#WA 2ms10044kbC++142.1kb2024-03-23 21:19:502024-03-23 21:19:51

Judging History

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

  • [2024-03-23 21:19:51]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:10044kb
  • [2024-03-23 21:19:50]
  • 提交

answer

#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 7;
typedef long long LL;
#define all(x) ((x).begin()), ((x).end())
#define pb push_back
typedef double D;
const int N = 100011;
bool isp[N];
int a[N], mnp[N], p[N];
D dp[N];
vector<int> fps[N], fs[N];
int sumf[N];
int main() {
    int n;
    scanf("%d", &n);
//n = 100000;
    int np = 0;
    fill(isp + 2, isp + n + 1, true);
    p[0] = inf;
    for(int i = 2; i <= n; i++) {
        if(isp[i]) {
            p[++np] = i;
            mnp[i] = np;
        }
        for(int j = 1; j <= np && i * p[j] <= n && i % p[j - 1]; j++) {
            isp[p[j] * i] = false;
            mnp[p[j] * i] = j;
        }
    }
    int tot = 0;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
//a[i] = 1;
        tot += a[i];
    }
    for(int i = 1; i <= n; i++) {
        int x = i;
        
        while(x != 1) {
            int id = mnp[x];
            while(x != 1 && mnp[x] == id) {
                x /= p[mnp[x]];
            }
            fps[i].pb(id);
        }
        for(int msk = 0; msk < (1 << fps[i].size()); msk++) {
            int t = 1;
            for(int j = 0; j < (int)fps[i].size(); j++) {

                if((msk >> j) & 1) {
                    t *= p[fps[i][j]];
                }
            }
            fs[i].pb(t);
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = i; j <= n; j += i) {
            sumf[j] += a[i];
        }
    }
    for(int i = n; i >= 1; i--) {
        dp[i] = 0;
        double d = 0;
        for(int j = i + i; j <= n; j += i) {
            int sum = 0;
            for(int msk = 0; msk < (1 << fps[j].size()); msk++) {
                sum += (__builtin_popcount(msk) % 2 ? -1 : 1) * sumf[j / fs[j][msk]];
            }
            d += sum / (double)tot * dp[j];
        }
        //dp[i] = 1 + (sumf[i] / tot) * dp[i] + d
        //(1 - sumf[i] / tot) * dp[i] = (1 + d)
        dp[i] = (1 + d) * tot / (tot - sumf[i]);
//        printf("dp[%d] = %lf\n", i, dp[i]);
    }
    printf("%.12f\n", dp[1] - 1);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 2ms
memory: 9952kb

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: 8780kb

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'