?
№ | Отправитель | Задача | Язык | Вердикт | Время | Память | Отослано | Протест. | |
---|---|---|---|---|---|---|---|---|---|
101938179 |
Дорешивание: luogu_bot4 |
914G - 44 | GNU C++11 | Полное решение | 982 мс | 47528 КБ | 2020-12-21 10:18:42 | 2020-12-21 10:18:42 |
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 1e9 + 7; int n, s[1000005]; ll ans[18][1 << 17], zcr[18][1 << 17], cnt[1 << 17]; ll zsy[1 << 17]; int Count[1 << 17]; ll fib[1 << 17]; ll A[1 << 17], B[1 << 17], C[1 << 17], ANS; ll inv2; int m; void FMT_or(ll *f, ll op) { for (int i = 1; i < (1 << m); i <<= 1) { for (int j = 0; j < (1 << m); j++) { if (!(j & i)) { f[j | i] = (f[j | i] + f[j] * op + mod) % mod; } } } } void FMT_and(ll *f, ll op) { for (int i = 1; i < (1 << m); i <<= 1) { for (int j = 0; j < (1 << m); j++) { if (!(j & i)) { f[j] = (f[j] + f[j | i] * op + mod) % mod; } } } } void FWT(ll *f, ll op) { for (int i = 1; i < (1 << m); i <<= 1) { for (int j = 0; j < (1 << m); j++) { if (!(j & i)) { ll x = f[j], y = f[j | i]; f[j] = (x + y) % mod; f[j | i] = (x - y + mod) % mod; if (op == -1) f[j] = f[j] * inv2 % mod, f[j | i] = f[j | i] * inv2 % mod; } } } } int main() { inv2 = mod - mod / 2; scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &s[i]), m = max(m, s[i]); m = (int)(log(m) / log(2)) + 1; for (int i = 1; i <= n; i++) cnt[s[i]]++; for (int i = 0; i < (1 << m); i++) Count[i] = Count[i >> 1] + (i & 1); for (int i = 0; i < (1 << m); i++) ans[Count[i]][i] = cnt[i]; for (int i = 0; i <= m; i++) { FMT_or(ans[i], 1); for (int j = 0; j < (1 << m); j++) { for (int k = 0; k <= i; k++) { zcr[i][j] = (zcr[i][j] + ans[k][j] * ans[i - k][j] % mod) % mod; } } FMT_or(zcr[i], -1); } for (int i = 0; i < (1 << m); i++) zsy[i] = cnt[i]; FWT(zsy, 1); for (int i = 0; i < (1 << m); i++) zsy[i] = zsy[i] * zsy[i] % mod; FWT(zsy, -1); fib[1] = 1; for (int i = 2; i < (1 << m); i++) fib[i] = (fib[i - 1] + fib[i - 2]) % mod; for (int i = 0; i < (1 << m); i++) A[i] = zcr[Count[i]][i] * fib[i] % mod; for (int i = 0; i < (1 << m); i++) B[i] = zsy[i] * fib[i] % mod; for (int i = 0; i < (1 << m); i++) C[i] = cnt[i] * fib[i] % mod; FMT_and(A, 1); FMT_and(B, 1); FMT_and(C, 1); for (int i = 0; i < (1 << m); i++) A[i] = A[i] * B[i] % mod * C[i] % mod; FMT_and(A, -1); for (int i = 1; i < (1 << m); i <<= 1) ANS = (ANS + A[i]) % mod; printf("%lld\n", ANS); return 0; }
?
?
?
?