QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#368884#8507. Clever Cell ChoicesPetroTarnavskyi#WA 4ms12148kbC++202.0kb2024-03-27 17:31:572024-03-27 17:31:58

Judging History

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

  • [2024-03-27 17:31:58]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:12148kb
  • [2024-03-27 17:31:57]
  • 提交

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