T1 浏览器

传送门=￣ω￣=

我真是太菜了

首先有一个 XZY 发现不了的性质：

当 $A$的二进制有奇数个 1，$B$的二进制有偶数个 1 时，$A \text{ xor } B$的二进制有奇数个 1，否则都是偶数个 1。

因此只要统计二进制下 1 的个数为奇数的有多少个，为偶数的有多少个，乘起来就是答案。

然后怎么统计呢？$\log _ 2 n$会超时。。。

当然是用 XZY 不会的方法啦，需要预处理出 $[0, 2 ^ {16}]$这个区间内的每个整数的二进制下 1 的个数。

然后每次询问一个数字 1 的个数就把它拆成二进制下的前 16 位和后 16 位，分别在预处理数组中找到 1 的个数加起来就行了。

这样总体就是 $O(n)$的了

代码：

#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 大师

传送门=￣ω￣=

我真是太菜了

就是一个 XZY 不会的、比较简单的 Dp

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

这样我们只需要枚举 $i$，然后枚举 $i$的前一个元素，这样公差 $j$也就确定了

状态转移：

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

复杂度其实是 $O(n ^ 2)$的。

代码：

#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 礼物

传送门=￣ω￣=

我真是太菜了

首先你需要发现一个 XZY 发现不了的性质：

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

可以考虑建一张 XZY 不会建的图：

若 $a _ i \subseteq a _ j$，则从第 $i$个点向第 $j$个点连一条有向边。

然后整个图的最长链就是 XZY 不知道的答案。

对于拓扑排序中处于同一层次的点都放到同一个箱子里即可，因为他们一定没有包含关系。

但这样建图复杂度是 $O(n ^ 2)$的，需要用上 XZY 不会的优化。

对于一个值 $k$，我们只从它向比它多一个 1 的点连边。

比如 $1010$只向 $1110$和 $1011$连有向边。

这样可以保证图的结构依然正确，但是最长链不再是答案，因为加入了一些输入中没有的数字。答案是链上最多的数据中出现过的点的个数。即你在拓扑排序的时候记录这个点之前经过有效点的最大个数。

分组方式依然一样，按拓扑序排，不存在包含关系的分到一组。

然后也可以不建图，可以用 XZY 不知道的 DP。。。这样代码会好写一点。

代码：

#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;
}

T4 口袋里的纸飞机

XZY 不会