QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#363350 | #8511. Greek Casino | Days_of_Future_Past# | WA | 2ms | 10044kb | C++14 | 2.1kb | 2024-03-23 21:19:50 | 2024-03-23 21:19:51 |
Judging History
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'