QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#442514 | #8747. 朔望 | Mindeveloped | TL | 0ms | 0kb | C++14 | 1.8kb | 2024-06-15 12:31:15 | 2024-06-15 12:31:17 |
answer
#include<bits/stdc++.h>
#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];
unordered_map<int, int> dc[25], 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;
unordered_map<int, int> lcm;
F (i, 1, n) {
if (x & (1 << (i - 1))) {
if (ls) {
unordered_map<int, int> cur;
cur[2]--;
for (pair<int, int> j: dc[ls]) cur[j.first] += j.second;
for (pair<int, int> j: dc[i]) cur[j.first] += j.second;
for (pair<int, int> j: sdc[ls][i]) cur[j.first] -= j.second;
if (!first) {
for (pair<int, int> j: cur) lcm[j.first] = max (lcm[j.first], j.second);
}
else lcm = cur;
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, unordered_map<int, int> &res) {
res.clear ();
F (i, 2, sqrt (x)) {
while (x % i == 0) {
res[i]++;
x /= i;
}
}
if (x > 1) res[x]++;
}
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) {
decomp (t[i], dc[i]);
F (j, i + 1, n) {
decomp (abs (t[i] - t[j]), sdc[i][j]);
}
}
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...