QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#442536#8747. 朔望MindevelopedTL 0ms0kbC++141.7kb2024-06-15 12:39:102024-06-15 12:39:10

Judging History

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

  • [2024-06-15 12:39:10]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-06-15 12:39:10]
  • 提交

answer

#include<bits/stdc++.h>
#define map unordered_map
#define F(i, x, y) for (int (i) = (x);(i) <= (y);(i)++)
#define R(i, x, y) for (int (i) = (x);(i) >= (y);(i)--)
using namespace std;

const int mod = 1e9 + 7;
int t[25], n, w[25];
map<int, int> sdc[25][25];
int qp (int x, int y) {
	int a = 1, u = x;
	while (y) {
		if (y % 2) a = 1LL * a * u % mod;
		u = 1LL * u * u % mod;
		y /= 2;
	}
	return a;
}
int get_contrib (int x) {
	if (x == (x & -x)) return 0;
	int ls = 0;
	bool first = true;
	map<int, int> lcm;
	F (i, 1, n) {
		if (x & (1 << (i - 1))) {
			if (ls) {
				if (!first) {
					for (pair<int, int> j: sdc[ls][i]) lcm[j.first] = max (lcm[j.first], j.second);
				}
				else lcm = sdc[ls][i];
				first = false;
			}
			ls = i;
		}
	}
	int ans = 1;
	for (pair<int, int> i: lcm) {
		ans = 1LL * ans * qp (i.first, (mod - 1 - i.second) % (mod - 1)) % mod; 
	}
	return ans;
}
void decomp (int x, map<int, int> &res, int d) {
	F (i, 2, sqrt (x)) {
		while (x % i == 0) {
			res[i] += d;
			x /= i;
		}
	}
	if (x > 1) res[x] += d;
}
int popc (int x) {
	return x ? (x & 1) + popc (x >> 1) : 0;
}
int main () {
	ios::sync_with_stdio (false);
	cin.tie (0);
	cin >> n;
	F (i, 1, n) {
		cin >> t[i];
	}
	F (i, 1, n) {
		F (j, i + 1, n) {
			decomp (t[i], sdc[i][j], 1);
			decomp (t[j], sdc[i][j], 1);
			decomp (abs (t[i] - t[j]), sdc[i][j], -1);
			sdc[i][j][2]--;
		}
	}
	F (i, 2, n) {
		cin >> w[i];
	}
	R (i, n, 2) {
		w[i] = (w[i] + 1LL * (mod - w[i - 1]) * i % mod) % mod;
	}
	int ans = 0;
	F (i, 0, (1 << n) - 1) {
		ans += 1LL * get_contrib (i) * w[popc (i)] % mod;
		ans %= mod;
	}
	cout << ans << "\n";
	return 0;
}

詳細信息

Test #1:

score: 0
Time Limit Exceeded

input:

20
73415948 190825288 205086969 242726140 280691039 291234110 341933576 379938879 399631744 420807939 421811250 486105558 605031352 645495854 714594262 775221445 793534057 818237037 926135349 940293639
108200337 125078426 163639475 261733041 280562529 287327830 310288774 415301468 419144734 46329977...

output:


result: