Untitled
unknown
plain_text
a month ago
2.3 kB
7
Indexable
Never
#include <bits/stdc++.h> #define sz(x) ((int)x.size()) #define int long long #define fi first #define se second #define pii pair<int, int> #define pb push_back #define vi vector<int> #define bit(i, x) ((x >> i) & 1) #define ALL(x) x.begin(), x.end() #define REP(i, n) for (int i = 1; i <= n; ++i) #define FOR(i, a, b) for (int i = a; i <= b; ++i) #define FORD(i, a, b) for (int i = a; i >= b; --i) #define Random(lf, rt) (lf + rand() % (rt - lf + 1)) #define Task "andsum" using namespace std; const int maxn = 1e6 + 7, N = 1e9 + 7, mod = 1e9 + 7; void ADD(int &x, int y) { x += y; if (x >= mod) x -= mod; if (x < 0) x += mod; } void MAXIMIZE(int &x, int y) { x = max(x, y); } void MINIMIZE(int &x, int y) { x = min(x, y); } int n; int a[maxn], f[maxn]; void sub1_1() { //for n^2 REP(i, n) { f[i] = 0; REP(j, n) if ((i & j) == j) f[i] += a[j]; } REP(i, n) cout << f[i] << " \n"[i == n]; } void sub1_2() { //n^2 cai tien REP(i, n) { f[i] = 0; for (int j = i; j; j = (j - 1) & i) f[i] += a[j]; } REP(i, n) cout << f[i] << " \n"[i == n]; } int dp[maxn][23]; void sub2_1() { //dp 2 chieu int LOG = log2(n) + 1; REP(i, n) { dp[i][0] = a[i]; REP(j, LOG) { if (bit(j - 1, i)) dp[i][j] = dp[i][j - 1] + dp[i ^ (1 << (j - 1))][j - 1]; else dp[i][j] = dp[i][j - 1]; } } REP(i, n) cout << dp[i][LOG] << " \n"[i == n]; } void sub2_2() { //dp 1 chieu int LOG = log2(n) + 1; REP(i, n) f[i] = a[i]; REP(j, LOG) REP(i, n) if (bit(j - 1, i)) f[i] += f[i ^ (1 << (j - 1))]; REP(i, n) cout << f[i] << " \n"[i == n]; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen(Task".inp", "r")) { freopen(Task".inp", "r", stdin); freopen(Task".out", "w", stdout); } cin >> n; REP(i, n) cin >> a[i]; // sub1_1(); // sub1_2(); // sub2_1(); sub2_2(); // mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); // cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n"; return 0; }
Leave a Comment