T1
Atcoder ABC217F Make Pair
考虑区间 dp，\(dp[l][r]\) 表示消完区间 \([l, r]\) 中所有人的方案数，转移枚举分界点，如果 \(l\) 和 \(r\) 有朋友关系则再从 \(dp[l + 1][r - 1]\) 转移。但是这样会算重，所以再加一维 \(0 / 1\) 表示这个区间是否封闭（不是由两个区间拼起来），这样就可以转移了。
代码
#include <iostream>
#define int long long
using namespace std;
const int P = 998244353;
int g[405][405];
int dp[405][405][2];
int n, m;
void Madd(int& x, int y) { (x += y) >= P ? (x -= P) : 0; }
int C[405][405];
signed main() {
cin >> n >> m;
C[0][0] = 1;
for (int i = 1; i <= 400; i++) {
for (int j = 0; j <= i; j++)
C[i][j] = (C[i - 1][j] + (j ? C[i - 1][j - 1] : 0)) % P;
}
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
g[u][v] = g[v][u] = 1;
}
for (int i = 1; i < n * 2; i++) dp[i][i + 1][1] = g[i][i + 1];
for (int d = 4; d <= n * 2; d += 2) {
for (int l = 1; l + d - 1 <= n * 2; l++) {
int r = l + d - 1;
for (int k = l + 1; k < r; k += 2)
Madd(dp[l][r][0], (dp[l][k][0] + dp[l][k][1]) % P * dp[k + 1][r][1] % P * C[d / 2][(r - k) / 2] % P);
if (g[l][r])
Madd(dp[l][r][1], dp[l + 1][r - 1][0] + dp[l + 1][r - 1][1]);
}
}
cout << (dp[1][n << 1][0] + dp[1][n << 1][1]) % P << "\n";
return 0;
}
T2
洛谷 P3607 Subsequence Reversal P
考虑转化一下子序列翻转，把它变成第一个与最后一个换，第二个与倒数第二个换。这样就拆成了一些数对的交换，对应的位置构成的区间互相严格包含。于是可以考虑类似于区间 dp 的东西。设 \(dp[l][r][a][b]\) 表示整个序列的前 \(l\) 个元素中的 LIS 和最后 \(r\) 个元素中的 LIS 加起来的长度，其中前面的 LIS 的最后一个元素在 \(a\)，后面 LIS 的最后一个元素在 \(b\)。转移考虑每次把右边或左边往里推一个，不接就不管，如果能往左往右接就接一下，如果要翻转就拿右边的往左接，拿左边的往右接，转移到 \([l + 1][r - 1]\) 的位置。
代码
#include <iostream>
using namespace std;
int n;
int A[55];
int dp[55][55][55][55];
void Cmax(int& x, int y) { x = max(x, y); }
int main() {
// freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++) cin >> A[i];
dp[0][n + 1][0][0] = 0;
A[n + 1] = 2147483647;
for (int d = n + 2; d > 2; d--) {
for (int l = 0; l + d - 1 <= n + 1; l++) {
int r = l + d - 1;
for (int a = 0; a <= n + 1; a++) {
if (a == l + 1)
a = r;
for (int b = 0; b <= n + 1; b++) {
if (b == l + 1)
b = r;
Cmax(dp[l + 1][r][a][b], dp[l][r][a][b]);
Cmax(dp[l][r - 1][a][b], dp[l][r][a][b]);
if (A[l + 1] >= A[a])
Cmax(dp[l + 1][r][l + 1][b], dp[l][r][a][b] + 1);
if (A[r - 1] <= A[b])
Cmax(dp[l][r - 1][a][r - 1], dp[l][r][a][b] + 1);
if (A[l + 1] <= A[b])
Cmax(dp[l + 1][r - 1][a][l + 1], dp[l][r][a][b] + 1);
if (A[r - 1] >= A[a])
Cmax(dp[l + 1][r - 1][r - 1][b], dp[l][r][a][b] + 1);
if (A[r - 1] >= A[a] && A[l + 1] <= A[b])
Cmax(dp[l + 1][r - 1][r - 1][l + 1], dp[l][r][a][b] + 2 - (l + 1 == r - 1));
}
}
}
}
int ans = 0;
for (int a = 0; a <= n; a++) {
for (int b = 0; b <= n; b++) {
for (int c = 1; c <= n; c++) {
if (A[a] <= A[b]) {
Cmax(ans, dp[c][c][a][b]);
Cmax(ans, dp[c][c + 1][a][b]);
}
}
}
}
cout << ans << "\n";
return 0;
}
T3
Atcoder ABC219H Candles
考虑最基础的区间 dp，\(dp[l][r]\) 表示处理完区间 \([l, r]\) 的蜡烛之后这区间内剩余的最大长度。然后由于处理完之后位置要么在左端点要么在右端点，就再加一维 \(0 / 1\) 记录一下当前位置。先考虑蜡烛能被减成负数的情况。此时我们的转移就是每次往左往右扩，看是从哪个端点走到哪个端点。但是这样不能知道时间，所以考虑进行费用提前计算，每次走向下一支蜡烛时把这一次行走花费的时间给所有区间之外的（尚未处理的）蜡烛造成的减少量先算进当前的 dp 值里面，然后走到一支蜡烛之后直接把它的长度加进 dp 值。但是实际上蜡烛不能被减成负数。
由于负数的蜡烛不被算进答案，我们走到这个蜡烛时就不把它算进答案了。由于不把它算进答案，消耗时间也就不会给它的贡献带来减少量。所以走向一个蜡烛并且提前计算费用时，还需要知道这个区间之外有多少个蜡烛到最后剩下正数长度。我们考虑直接把这玩意也扔进状态里，于是状态变成 \(dp[l][r][0 / 1][k]\) 表示已经处理完了区间 \([l, r]\) 的蜡烛，当前在左 / 右端点，\([l, r]\) 之外有多少蜡烛我们要求它剩下正数。转移的时候考虑走向的这个蜡烛最后要不要留成正数，然后就可以转移了。
代码
#include <iostream>
#include <algorithm>
#include <string.h>
#include <map>
#define int long long
using namespace std;
const int inf = 448509071590753727;
int n;
int a[305];
map<int, int> mp, cnt, id;
struct Pos {
int p, len, cnt;
} p[305];
int dp[305][305][305][2];
void Cmax(int& x, int y) { x = max(x, y); }
signed main() {
memset(dp, -63, sizeof dp);
cin >> n;
int S = 0;
for (int i = 1; i <= n; i++) {
cin >> p[i].p >> p[i].len;
p[i].cnt = 1;
if (p[i].p == 0)
S += p[i].len;
}
p[++n] = (Pos) { 0, 0, 1 };
sort(p + 1, p + n + 1, [](Pos a, Pos b) { return a.p < b.p; });
int pos = 0;
for (int i = 1; i <= n; i++) {
if (p[i].p == 0 && p[i].len == 0)
pos = i;
}
for (int i = 1; i <= n; i++) id[p[i].p] = i;
for (int i = 1; i <= n; i++)
dp[pos][pos][i][0] = dp[pos][pos][i][1] = 0;
for (int d = 1; d <= n; d++) {
for (int l = 1; l + d - 1 <= n; l++) {
int r = l + d - 1;
for (int k = 0; k <= n; k++) {
int t;
if (l != 1) {
t = p[l].p - p[l - 1].p;
if (k >= p[l - 1].cnt)
Cmax(dp[l - 1][r][k - p[l - 1].cnt][0], dp[l][r][k][0] + p[l - 1].len - k * t);
Cmax(dp[l - 1][r][k][0], dp[l][r][k][0] - k * t);
t = p[r].p - p[l - 1].p;
if (k >= p[l - 1].cnt)
Cmax(dp[l - 1][r][k - p[l - 1].cnt][0], dp[l][r][k][1] + p[l - 1].len - k * t);
Cmax(dp[l - 1][r][k][0], dp[l][r][k][1] - k * t);
}
if (r != n) {
t = p[r + 1].p - p[l].p;
if (k >= p[r + 1].cnt)
Cmax(dp[l][r + 1][k - p[r + 1].cnt][1], dp[l][r][k][0] + p[r + 1].len - k * t);
Cmax(dp[l][r + 1][k][1], dp[l][r][k][0] - k * t);
t = p[r + 1].p - p[r].p;
if (k >= p[r + 1].cnt)
Cmax(dp[l][r + 1][k - p[r + 1].cnt][1], dp[l][r][k][1] + p[r + 1].len - k * t);
Cmax(dp[l][r + 1][k][1], dp[l][r][k][1] - k * t);
}
}
}
}
int ans = 0;
for (int i = 0; i <= n; i++) Cmax(ans, max(dp[1][n][i][0], dp[1][n][i][1]));
cout << ans << "\n";
return 0;
}
T4
CF1922F Replace on Segment
首先容易想到 \(f[l][r][k]\) 表示将 \([l, r]\) 变为 \(k\) 的最小代价。然后由于需要知道一个区间能不能被 \(k\) 赋值，需要知道 \(g[l][r][k]\) 表示 \([l, r]\) 区间内变得没有 \(k\) 的最小代价。首先 \(f\) 和 \(g\) 都有显然的枚举分界点转移。另外有 \(f[l][r][k] = g[l][r][k] + 1\)，这是好理解的。对于 \(g\) 有 \(g[l][r][a] = g[l][r][b] + 1(a \neq b)\)，这表示将 \([l, r]\) 变成 \(b\)，这样区间中也是没有 \(a\)，符合条件。复杂度 \(\mathcal{O}(n^4)\)，\(n = 100\) 随便跑。
代码
#include <iostream>
#include <string.h>
using namespace std;
int f[105][105][105];
int g[105][105][105];
int n, M;
int a[105];
void Cmin(int& x, int y) { x = min(x, y); }
int main() {
// freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
int tc;
cin >> tc;
while (tc--) {
memset(f, 63, sizeof f);
memset(g, 63, sizeof g);
cin >> n >> M;
for (int i = 1; i <= n; i++) {
cin >> a[i];
for (int j = 1; j <= M; j++) {
if (a[i] != j) {
f[i][i][j] = 1;
g[i][i][j] = 0;
} else {
f[i][i][j] = 0;
g[i][i][j] = 1;
}
}
}
for (int d = 2; d <= n; d++) {
for (int l = 1; l + d - 1 <= n; l++) {
int r = l + d - 1;
for (int k = 1; k <= M; k++) {
for (int m = l; m < r; m++) {
Cmin(f[l][r][k], f[l][m][k] + f[m + 1][r][k]);
Cmin(g[l][r][k], g[l][m][k] + g[m + 1][r][k]);
}
}
for (int k = 1; k <= M; k++) {
for (int x = 1; x <= M; x++) {
if (k != x)
Cmin(g[l][r][k], g[l][r][x] + 1);
}
}
for (int k = 1; k <= M; k++) Cmin(f[l][r][k], g[l][r][k] + 1);
}
}
int ans = 2147483647;
for (int i = 1; i <= M; i++) Cmin(ans, f[1][n][i]);
cout << ans << "\n";
}
return 0;
}
T5
Atcoder ABC223G Vertex Deletion
由于树是二分图，而二分图最大匹配等于最小点覆盖，我们转化为最小点覆盖来做。\(dp[x][0 / 1]\) 表示 \(x\) 子树内 \(x\) 不选 / 选的最小点覆盖。整棵树的答案是 \(\min\{dp[1][0], dp[1][1]\}\)。接下来考虑换根，递归时 \(x\) 向子树 \(y\) 传入两个参数表示 \(x\) 选 / 不选时 \(y\) 子树外的最小点覆盖。这样就相当于以 \(y\) 为根，做 \(x\) 子树的 dp。考虑对 \(x\) 的子树做前后缀 dp 值的合并，然后结合父亲传下来的 dp 值就可以很容易地求出 \(y\) 为根时 \(x\) 的 dp 值。然后去掉 \(x\) 这个点相当于以 \(x\) 为根并且强制选 \(x\) 这个点时整棵树的最小点覆盖减 \(1\)（减去 \(x\)）。于是答案就很好求了。
代码
#include <iostream>
using namespace std;
int n;
int head[200005], nxt[400005], to[400005], ecnt;
void add(int u, int v) { to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt; }
int dp[200005][2];
int dp2[200005][2];
int ps[200005], ns[200005];
int pre[200005][2], suf[200005][2];
void dfs1(int x, int fa) {
dp[x][1] = 1;
int tmp = 0;
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
if (v != fa) {
dfs1(v, x);
dp[x][1] += min(dp[v][0], dp[v][1]);
dp[x][0] += dp[v][1];
ns[ps[v] = tmp] = v;
pre[v][0] = min(dp[v][0], dp[v][1]) + pre[ps[v]][0];
pre[v][1] = dp[v][1] + pre[ps[v]][1];
tmp = v;
}
}
while (tmp) {
suf[tmp][0] = min(dp[tmp][0], dp[tmp][1]) + suf[ns[tmp]][0];
suf[tmp][1] = dp[tmp][1] + suf[ns[tmp]][1];
tmp = ps[tmp];
}
}
void dfs2(int x, int fa, int up0, int up1) {
dp2[x][0] = dp[x][0];
dp2[x][1] = dp[x][1];
if (fa) {
dp2[x][0] += up1;
dp2[x][1] += min(up0, up1);
}
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
if (v != fa) {
int t1 = up1 + pre[ps[v]][1] + suf[ns[v]][1];
int t2 = min(up0, up1) + pre[ps[v]][0] + suf[ns[v]][0] + 1;
dfs2(v, x, t1, t2);
}
}
}
int main() {
// freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
add(u, v);
add(v, u);
}
int ans = 0;
dfs1(1, 0);
ans = min(dp[1][0], dp[1][1]);
dfs2(1, 0, 0, 0);
int cnt = 0;
for (int i = 1; i <= n; i++) cnt += (dp2[i][1] - 1 == ans);
cout << cnt << "\n";
return 0;
}
T6
Atcoder ABC115F Perils in Parallel
先对原数组异或差分一下，这样区间异或转化为两次单点异或。考虑把每个开关操作的两个点连起来，构成一张图。我们的操作是选中一条边，将其两个端点的状态取反，我们的目标是将所有点点权变成 \(0\)。我们考虑一棵 dfs 树和其上的一条返祖边。这条返祖边构成了一个环。注意到我们把整个环上所有边操作一遍等于没操作，所以操作这条返祖边相当于操作一遍这条返祖边连接的两个点在 dfs 树上的路径上的所有边。于是返祖边无用，全部删掉。这样就变成了一棵树（森林），而这种情况是好处理的，只需要从叶子往上考虑，如果叶子为 \(1\) 就操作叶子上面的边，然后依次向上推，如果最后根是 \(0\) 则合法，否则不可能达成。
代码
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
int n, m;
struct Lamp {
int p, s;
} a[100005];
struct Switch {
int l, r, id;
} b[1000005];
int head[1000005], nxt[2000005], to[2000005], ew[2000005], ecnt;
void add(int u, int v, int ww) { to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt, ew[ecnt] = ww; }
int ans[1000005], acnt;
bool vis[1000005];
void dfs(int x) {
vis[x] = 1;
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
if (!vis[v]) {
dfs(v);
if (a[v].s) {
ans[++acnt] = ew[i];
a[x].s ^= 1;
a[v].s = 0;
}
}
}
}
signed main() {
// freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i].p >> a[i].s;
sort(a + 1, a + n + 1, [](Lamp a, Lamp b) { return a.p < b.p; });
for (int i = n + 1; i; i--) a[i].s ^= a[i - 1].s;
for (int i = 1; i <= m; i++) cin >> b[i].l >> b[i].r, b[i].id = i;
sort(b + 1, b + m + 1, [](Switch a, Switch b) { return a.l < b.l; });
for (int i = 1, j = 1; i <= m; i++) {
while (j <= n && a[j].p < b[i].l) ++j;
b[i].l = j;
}
sort(b + 1, b + m + 1, [](Switch a, Switch b) { return a.r > b.r; });
for (int i = 1, j = n; i <= m; i++) {
while (j && a[j].p > b[i].r) --j;
b[i].r = j;
}
for (int i = 1; i <= m; i++) {
if (b[i].r >= b[i].l) {
add(b[i].l, b[i].r + 1, b[i].id);
add(b[i].r + 1, b[i].l, b[i].id);
}
}
for (int i = 1; i <= n + 1; i++) {
if (!vis[i]) {
dfs(i);
if (a[i].s) {
cout << -1 << "\n";
return 0;
}
}
}
cout << acnt << "\n";
sort(ans + 1, ans + acnt + 1);
for (int i = 1; i <= acnt; i++) cout << ans[i] << " ";
cout << "\n";
return 0;
}
T7
Atcoder ABC293Ex Optimal Path Decomposition
先二分答案 \(k\)。考虑 \(f[x][0 / 1 / 2]\) 表示 \(x\) 周围有不超过 \(0 / 1 / 2\) 个点与其颜色相同时 \(x\) 子树内最优情况下 \(x\) 向下走经过的最多颜色数（不包含 \(x\) 的颜色）。转移考虑在保证合法的情况下以尽量优的情况更新 \(x\) 的 dp 值。如果不合法了就赋成 \(inf\)，最后在根的地方判一下是否合法即可。
代码
#include <iostream>
#define int long long
using namespace std;
const int inf = 1000000005;
int n, K;
int head[200005], nxt[400005], to[400005], ecnt;
void add(int u, int v) { to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt; }
int f[200005][3];
void dfs(int x, int fa) {
f[x][0] = f[x][1] = f[x][2] = 0;
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
if (v != fa) {
dfs(v, x);
int g0 = inf, g1 = inf, g2 = inf;
if (f[x][0] + f[v][1] < K)
g1 = min(g1, max(f[x][0], f[v][1]));
if (f[x][0] + f[v][2] + 1 < K)
g0 = min(g0, max(f[x][0], f[v][2] + 1));
if (f[x][1] + f[v][1] < K)
g2 = min(g2, max(f[x][1], f[v][1]));
if (f[x][1] + f[v][2] + 1 < K)
g1 = min(g1, max(f[x][1], f[v][2] + 1));
if (f[x][2] + f[v][2] + 1 < K)
g2 = min(g2, max(f[x][2], f[v][2] + 1));
f[x][0] = g0, f[x][1] = min(f[x][0], g1), f[x][2] = min(f[x][1], g2);
}
}
}
signed main() {
// freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
add(u, v);
add(v, u);
}
int l = 1, r = n, ans = -1;
while (l <= r) {
K = (l + r) >> 1;
dfs(1, 0);
if (f[1][2] < inf)
r = K - 1, ans = K;
else
l = K + 1;
}
cout << ans << "\n";
return 0;
}
T8
Atcoder ABC328G Cut and Reorder
容易发现一定是一次 \(1\) 操作之后一堆 \(2\) 操作。于是钦定 \(b\) 数组顺序，把 \(a\) 数组一段一段接着往上拼。考虑 \(f[S]\) 表示 \(a\) 数组已经有 \(S\) 集合的数拿来拼 \(b\) 数组的最小代价。接下来枚举把哪个区间拼到 \(b\) 上去。这段区间必须是全 \(0\) 的，否则不合法。拼上去之后操作 \(2\) 带来的代价可以暴力枚举预处理出来，总复杂度 \(\mathcal{O}(2^nn^2)\)，但是远远跑不满，可以通过。
代码
#include <iostream>
#include <string.h>
#define abs(x) (((x) > 0) ? (x) : (-(x)))
#define lowbit(x) ((x) & (-(x)))
#define int long long
using namespace std;
int n, c;
int a[25], b[25];
int dif[25][25][25];
int pcnt[5000005];
int dp[5000005];
void Cmin(int& x, int y) { x = min(x, y); }
signed main() {
// freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
cin >> n >> c;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> b[i];
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n - k + 1; i++) {
for (int j = 1; j <= n - k + 1; j++) {
int ca = i, cb = j;
for (; ca <= i + k - 1; ca++, cb++)
dif[i][j][k] += abs(a[ca] - b[cb]);
}
}
}
memset(dp, 63, sizeof dp);
dp[0] = -c;
pcnt[0] = -1;
for (int S = 0; S < (1 << n); S++) {
pcnt[S] = pcnt[S - lowbit(S)] + 1;
for (int i = 1; i <= n; i++) {
if (S & (1 << (i - 1)))
continue;
int to = S;
for (int j = i; j <= n && (!(S & (1 << (j - 1)))); j++) {
to |= (1 << (j - 1));
Cmin(dp[to], dp[S] + c + dif[i][pcnt[S] + 1][j - i + 1]);
}
}
}
cout << dp[(1 << n) - 1] << "\n";
return 0;
}
T9
Atcoder ABC295Ex E or m
容易发现一个位置可以是 \(1\) 当且仅当其上全 \(1\) 或其左全 \(1\)。于是容易想到进行按格转移的轮廓线dp，状态 \(f[i][j][S][0 / 1]\) 表示处理到第 \(i\) 行第 \(j\) 列，每一列目前是否是全 \(1\)，当前行前面是否是全 \(1\)。然后转移就是平凡的，只需要考虑当前列是否全 \(1\) 和当前行是否全 \(1\) 即可。转移到行末之后要记得换行，无论当前行是否全 \(1\) 到了下一行都是全 \(1\)。
代码
#include <iostream>
// #define int long long
using namespace std;
const int P = 998244353;
int n, m;
string str[20];
int dp[20][20][262200][2];
void Madd(int& x, int y) { ((x += y) >= P) ? (x -= P) : 0; }
signed main() {
// freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> str[i], str[i] = ' ' + str[i];
dp[1][0][(1 << m) - 1][1] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
for (int k = 0; k < (1 << m); k++) {
if (str[i][j] != '1') {
int x = (k ^ (k & (1 << (j - 1))));
Madd(dp[i][j][x][0], (dp[i][j - 1][k][0] + dp[i][j - 1][k][1]) % P);
}
if (str[i][j] != '0') {
Madd(dp[i][j][k][1], dp[i][j - 1][k][1] % P);
if (k & (1 << (j - 1)))
Madd(dp[i][j][k][0], dp[i][j - 1][k][0] % P);
}
}
}
for (int k = 0; k < (1 << m); k++) Madd(dp[i + 1][0][k][1], (dp[i][m][k][0] + dp[i][m][k][1]) % P);
}
int ans = 0;
for (int i = 0; i < (1 << m); i++) Madd(ans, dp[n + 1][0][i][1]);
cout << ans << "\n";
return 0;
}
T10
CF383E Vowels
正难则反，考虑求出有多少字符串完全属于某个字符集。注意到这实际上是一个高维前缀和的问题，于是直接高维前缀和即可。这个高维前缀和的基本思想就是从低维向高维扩展，要求一个体的和，先求所有面的和，再把面的求和分成线的求和，最后把这些和一步步加起来得到答案。
代码
#include <iostream>
using namespace std;
int n;
string str;
int dp[16777220];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> str;
int a = str[0] - 'a';
int b = str[1] - 'a';
int c = str[2] - 'a';
dp[(1 << a) | (1 << b) | (1 << c)]++;
}
for (int i = 0; i < 24; i++) {
for (int j = 0; j < (1 << 24); j++) {
if (j & (1 << i))
dp[j] += dp[j ^ (1 << i)];
}
}
int ans = 0;
int S = (1 << 24) - 1;
for (int i = 0; i <= S; i++) ans ^= (n - dp[i]) * (n - dp[i]);
cout << ans << "\n";
return 0;
}