QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#368884 | #8507. Clever Cell Choices | PetroTarnavskyi# | WA | 4ms | 12148kb | C++20 | 2.0kb | 2024-03-27 17:31:57 | 2024-03-27 17:31:58 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
const int N = 1 << 17;
VI fact[N];
unordered_map<int, db> f[N];
bool hasBit(int mask, int i)
{
return ((mask >> i) & 1);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(15);
int n;
cin >> n;
VI w(n + 1);
FOR(i, 1, n + 1)
cin >> w[i];
vector<db> p(n + 1);
db sumW = accumulate(ALL(w), 0);
FOR(i, 1, n + 1)
p[i] = w[i] / sumW;
VI lp(n + 1, -1);
FOR(i, 2, n + 1)
{
if (lp[i] != -1)
continue;
for (int j = i; j <= n; j += i)
{
if (lp[j] == -1)
lp[j] = i;
}
}
FOR(i, 1, n + 1)
{
int cur = i;
while (cur > 1)
{
int curPrime = lp[cur];
while (cur % curPrime == 0)
{
cur /= curPrime;
}
fact[i].PB(curPrime);
}
f[i].reserve(1 << SZ(fact[i]));
f[i][1] = p[i];
FOR(mask, 1, 1 << SZ(fact[i]))
{
int j = __builtin_ctz(mask);
assert(hasBit(mask, j));
int prodMask = 1;
FOR(k, 0, SZ(fact[i]))
if (hasBit(mask, k))
prodMask *= fact[i][k];
f[i][prodMask] = f[i][prodMask / fact[i][j]];
int ni = i / fact[i][j];
if (ni % fact[i][j] != 0)
prodMask /= fact[i][j];
f[i][prodMask] += f[ni][prodMask];
}
}
vector<db> dp(n + 1);
RFOR(i, n + 1, 1)
{
VI primes;
db s = 1;
for (int j = 2; j * i <= n; j++)
{
int k = j * i;
int prodMask = 1;
for (int curPrime : fact[i])
{
if (j % curPrime == 0)
{
prodMask *= curPrime;
}
}
s += f[k][prodMask] * dp[k];
}
int prodAll = 1;
for (int curPrime : fact[i])
{
prodAll *= curPrime;
}
dp[i] = s / (1 - f[i][prodAll]);
}
cout << dp[1] - 1 << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 4ms
memory: 12148kb
input:
3 3 #.# ... #.#
output:
inf
result:
wrong output format Expected integer, but "inf" found