「LibreOJ」#6682. 梦中的数论 – 题解

主要思路

其实稍稍看一下,会发现 \([j|i][(j + k)|i]\) 满足的时候 \(k\) 并没有什么特别的限制,所以可以直接理解为选两个因数,然后就转化为了:

\[ \begin{aligned} & \sum_{i = 1}^n {\sigma_0(i) \choose 2} \\ =& \sum_{i = 1}^n \frac{\sigma_0^2(i) – \sigma_0(i)}{2}\end{aligned} \]

后面的那个 \(\sum \sigma_0(x)\) 可以直接数论分块,前面那个用 min_25 筛一下就好。有 \(f(p^k) = \prod (1 + c_i)^2\)。

Continue reading →

「QuestOJ」盛大的庆典 – 题解

主要思路

狗屎状压题。

看到度数不超过 \(10\) 就知道需要状压儿子的信息。考虑处理一个 neck 数组来表示子树内节点到当前子树根下面的节点编号,然后我们每一次往上跳的时候我们都可以对这个数组进行调整,然后 DP 的时候就会比较愉快了。

处理 \(m\) 个请求的时候,我们把对应的 neck 提取出来,然后做标记,按标号小的进行 DP。

Continue reading →

「Universal OJ」:#308「UNR #2」 UOJ 拯救计划 – 题解

主要思路

看到这个很小的模数就知道肯定是个 Trick 题,一定不会让你去跑一般图的(估计是 NPC)。

首先,我们可以设颜色未标号的、用了 \(i\) 种颜色的方案数为 \(f_i\),那么答案就是:

\[ ans = \sum_{i = 1}^k f_i k^{\underline{i}} \]

发现这个东西在 \(i > 2\) 时就直接被模成了 \(0\)。我们只需要算 \(f_1, f_2\) 即可。其中 \(f_1 = [m = 0]\)。\(f_2\) 的方案数等价于二分图的双部染色的方案数。所以,我们跑一边二分图然后算 \(2^b\) 即可,\(b\) 是连通块次数。

Continue reading →

「LibreOJ」#6060「2017 山东一轮集训 Day1 / SDWC2018 Day1」Set – 题解

主要思路

神仙题。

发现 \(x_1 \oplus x_2 = xorsum\),所以我们尽量把 \(xorsum\) 的位分给 \(x_2\)。如果 \(xorsum\) 的某位为 \(1\),那就直接给 \(x_2\) 就好;如果为 \(0\) ,那么有 \(0, 0\) 和 \(1, 1\) 两种情况。所以,我们构造线性基时,通过优先考虑为更高的 \(0\) 的位可以使得答案更大(我们考虑用线性基求最大异或和的过程,优先插入权更大的位置)。

Continue reading →

AtCoder Regular Contest 091 – 解题报告

这场代码都好短啊。

C – Flip,Flip, and Flip……

傻逼题,随便搞就行了。

// ARC091A.cpp
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, m;

int main()
{
    scanf("%d%d", &n, &m);
    if (n > m)
        swap(n, m);
    if (n == 1)
    {
        if (m == 1)
            puts("1");
        else
            printf("%d\n", max(0, m - 2));
        return 0;
    }
    printf("%lld\n", max(0LL, 1LL * (n - 2) * (m - 2)));
    return 0;
}
Continue reading →