QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#367951#8511. Greek Casinoucup-team1196#WA 2ms4104kbC++231.3kb2024-03-26 17:39:302024-03-26 17:39:31

Judging History

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

  • [2024-03-26 17:39:31]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:4104kb
  • [2024-03-26 17:39:30]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define double long double

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    vector<int>a(n+1);
    vector<double>f(n+1);
    vector<int>self(n+1),st(n+1),p;
    vector<vector<int>>fac(n+1);
    int tot=0;
    for(int i=1;i<=n;++i) cin>>a[i],tot+=a[i];
    st[1]=1;
    for(int i=1;i<=n;++i){
        for(int j=i;j<=n;j+=i) self[j]+=a[i];
        if(!st[i]){
            p.push_back(i);
            for(int j=2*i;j<=n;j+=i) st[i]=1;
        }
        for(int j=1;j*j<=n;++j){
            if(i%j) continue;
            fac[i].push_back(j);
            if(i/j!=j) fac[i].push_back(i/j);
        }
    }
    vector<vector<int>>sum(n+1);
    for(int i=1;i<=n;++i){
        for(int j=i+i;j<=n;j+=i){
            int ans=0;
            for(auto v:fac[i]){
                if(__gcd(i/v,j/i)==1) ans+=a[j/i*v];
            }
            sum[i].push_back(ans);
        }
    }
    for(int i=n;i;--i){
        double p=self[i]*1.0l/tot;
        f[i]=0;
        double ans=p;
        int cnt=0;
        for(int j=i+i;j<=n;j+=i){
            ans+=(f[j]+1)*(sum[i][cnt++]*1.0l/tot);
        }
        f[i]=1./(1-p)*ans;
    }
    cout<<setprecision(20)<<f[1]<<endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
1 1 1

output:

3.5000000000000000004

result:

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

Test #2:

score: 0
Accepted
time: 0ms
memory: 3888kb

input:

3
1 1 2

output:

3.6666666666666666667

result:

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

Test #3:

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

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

result:

wrong answer 1st numbers differ - expected: '1.0183368', found: '1.0258819', error = '0.0074092'