QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#382163#8511. Greek Casinokevinshan#WA 2ms10172kbC++172.5kb2024-04-08 04:19:332024-04-08 04:19:34

Judging History

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

  • [2024-04-08 04:19:34]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:10172kb
  • [2024-04-08 04:19:33]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define ll long double
#define all(x) x.begin(), x.end()
#define pb push_back
#define f first
#define s second

long long GCD(long long x, long long y)
{
    if (y == 0) return x;
    return GCD(y, x%y);
}
long long LCM(long long x, long long y)
{
    return (x * y) / GCD(x, y);
}

const int MAXN = 1e5 + 5;
ll dp[MAXN];
vector<int> fac[MAXN];
vector<long long> lcms[MAXN];

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    if (fopen("input.in", "r")) {
        freopen("input.in", "r", stdin);
        freopen("output.out", "w", stdout);
    }
    int n; cin>>n;
    long long ar[n+1];
    int tot = 0;
    for(int i=1; i<=n; i++) cin>>ar[i];
    for(int i=1; i<=n; i++){
        for(int j=1; j*j<=i; j++){
            if(i%j == 0) {
                fac[i].pb(j);
                if(i/j != j) fac[i].pb(i/j);
            }
        }
    }

    for(int i=1; i<=n; i++){
        for(int j:fac[i]) lcms[i].pb(LCM((long long)i,(long long)j));
    }

    int denom = 0;
    for(int i=1; i<=n; i++) denom += ar[i];

    ll res = 0;

    for(int i=n; i>=1; i--){


        // if(i > 1) dp[i] += 1;

        int stay_same = 0;
        for(int j:fac[i]) stay_same += ar[j];

        // cout<<i<<"|"<<stay_same<<"/"<<denom<<"\n";
        // cout<<i<<"|"<<stay_same<<"<"<<((ll)stay_same * (ll)(denom - stay_same)) / ((ll)stay_same * (ll)stay_same)<<"\n";
        
        dp[i] += (ll)(stay_same) / ((ll)(denom-stay_same));

        for(int j=2; j*i<=n; j++){
            int prob = 0;
            // cout<<i<<"*"<<j<<"="<<i*j<<" ";
            for(int l=0; l<fac[i].size(); l++){
                if(((long long)j*i)%(lcms[i][l]) == 0) {
                    int oth = (j*i) / (lcms[i][l]) * fac[i][l];
                    prob += ar[oth];

                }
            }
            // for(int fc:fac[i]){
            //     if(fc % pw == 0) {
            //         // cout<<fc<<":"<<fc*j<<" ";
            //         int oth = fc * j;
            //         prob += ar[oth];
            //     }
            // }
            // cout<<"\n";
            // cout<<i<<"<<"<<prob<<"|"<<denom<<"\n";
            dp[i] += ((ll) prob / (ll) (denom - stay_same)) * (dp[j*i] + 1);
        }

        // dp[i] += (ll) denom / (ll) (denom - stay_same);
    }
    // cout<<"\n";
    // cout<<"DP: ";
    // for(int i=1; i<=n; i++) cout<<dp[i]<<" ";
    // cout<<"\n";
    cout<<fixed<<setprecision(20)<<dp[1];


    
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 9080kb

input:

3
1 1 1

output:

3.50000000000000000000

result:

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

Test #2:

score: 0
Accepted
time: 2ms
memory: 9080kb

input:

3
1 1 2

output:

3.66666666666666666674

result:

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

Test #3:

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

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.02426396154343988284

result:

wrong answer 1st numbers differ - expected: '1.0183368', found: '1.0242640', error = '0.0058204'