# T1 浏览器

#include <bits/stdc++.h>

#define NS (10000005)

using namespace std;

template <typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

int bc[1 << 16], n, x[NS], A, B, C, D, c1, c2;

int bitcnt(int a)
{
return bc[a >> 16] + bc[a - ((a >> 16) << 16)];
}

int main(int argc, char const* argv[])
{
for (int i = 1; i <= (1 << 16); i += 1) bc[i] = bc[i >> 1] + (i & 1);
IN(n), IN(A), IN(B), IN(C), IN(D), IN(x[0]);
A %= D, B %= D, C %= D, x[0] %= D;
for (int i = 1; i <= n; i += 1)
x[i] =
(1ll * A * x[i - 1] % D * x[i - 1] % D + 1ll * B * x[i - 1] % D + C) % D;
for (int i = 1; i <= n; i += 1)
if (bitcnt(x[i]) & 1) c1++;
else c2++;
printf("%lld\n", 1ll * c1 * c2);
return 0;
}


# T2 大师

$f[i][j]$表示以第 $i$个元素为结尾（一定包含第 $i$个元素）的、公差为 $j$的等差数列个数。

$$f[i][j] = \sum ^ {h[i] – h[k] = j} f[k][j] + 1$$

#include <bits/stdc++.h>

#define NS (1005)
#define VS (40005)
#define MOD (998244353)

using namespace std;

inline int pls(int a, int b) {return a + b >= MOD ? a + b - MOD : a + b;}

template <typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

int n, h[NS], f[NS][VS], ans;

int main(int argc, char const* argv[])
{
IN(n);
for (int i = 1; i <= n; i += 1) IN(h[i]);
for (int i = 1; i <= n; i += 1)
for (int j = 1; j < i; j += 1)
{
f[i][h[i] - h[j] + 20000] =
pls(f[i][h[i] - h[j] + 20000], pls(f[j][h[i] - h[j] + 20000], 1));
ans = pls(ans, pls(f[j][h[i] - h[j] + 20000], 1));
}
printf("%d\n", pls(ans, n));
return 0;
}


# T3 礼物

$a _ i \text { & } a _ j \geq \min(a _ i, a _ j)$等效于 $a _ i$与 $a _ j$中有一个是另一个的子集（二进制的每一位看成元素）

#include <bits/stdc++.h>

using namespace std;

template <typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

int n, k, f[1 << 20], ans;

bool book[1 << 20];

vector<int> g[20];

int main(int argc, char const* argv[])
{
IN(n), IN(k);
for (int i = 1, a; i <= n; i += 1) IN(a), book[a] = 1;
for (int i = 0; i < (1 << k); i += 1)
{
for (int j = 0; j < k; j += 1)
if ((i >> j) & 1) f[i] = max(f[i], f[i ^ (1 << j)]);
if (book[i]) f[i]++, g[f[i]].push_back(i), ans = max(ans, f[i]);
}
printf("1\n%d\n", ans);
for (int i = 1; i <= ans; i += 1)
{
printf("%lu", g[i].size());
for (int j = 0; j < g[i].size(); j += 1) printf(" %d", g[i][j]);
putchar(10);
}
return 0;
}


XZY 不会