QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#442536 | #8747. 朔望 | Mindeveloped | TL | 0ms | 0kb | C++14 | 1.7kb | 2024-06-15 12:39:10 | 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...