Q779’s Blog

CF1451F Nullify The Matrix 题解 题目链接：Nullify The Matrix 题意： Ashish 和 Jeel 在玩游戏，有一个 \(n\times m\) 的棋盘，每个格子有一个非负整数的权值。 两个人轮流操作，每次操作先选择一个权值非 \(0\) 的格子作为起点，然后选择起点右下角的一个格子作为终点，然后选择它们之间的一条最短路径，然后给起点的权值减一个正整数、路径上每个点的权值随意加减（也可以不改变），但是都不能改成负数。 不能操作（全变成 \(0\)）就输了，Ashish 先手，问谁必胜。 这道题的思路和 CF1149E 挺像的。 记 \(f_i = \bigoplus_{x+y=p}a_{x,y}\) ，那么先手必败当且仅当 \(\forall i\) 有 \(f_i = 0\) ；否则先手必胜。 证明 记 \(\rm N\) 为先手必胜态，\(\rm P\) 为先手必败态。 考虑证明在此最优策略下原问题转化一个有向图游戏。 终止状态，显然为 \(\rm P\) 。 对于 \(\rm P\) 态，即 \(\forall i, f_...

HTML 排版表示证毕的小方块 如果直接用 $\square$ 的话，会出现这样的情况 证明 这是一些文本。\(\square\) 虽然能看懂，但是非常不好看。 然后写本文的时候的方法不是很好，现在给出一个非常简单的办法。 直接在你写的 markdown 文本后面加上 <span style="float: right;">$\square$</span>就好了 注意不要换行，直接跟在后面就行了。实际效果如下： 证明 因为所以，对对对。 然后呢，啊对对对，嗯。\(\square\) 题外话： 前端什么的，完全不会啊。

CF1149E Election Promises 题解 题目链接：Election Promises 题意： 给定一张 \(n\) 个点 \(m\) 条边的有向图（不一定连通），每个点有一个权值 \(a_i\) 。 两人轮流进行操作，每次操作可以选择任意一个节点 \(u\) 并将其点权减小为一个非负整数， 之后可以将所有节点 \(v \in\{v \mid (u,v) \in E\}\) 的权值更改为任意非负整数 最先不能操作者输（指减小 \(u\) 的操作），求先手有无必胜策略。 若有必胜策略则接下来输出第一次操作后能够确保获胜的每个节点的权值 数据范围： \(1 \leq n \leq 2 \times 10^5, 0 \leq m \leq 2 \times 10^5,~0 \le a_i \le 2\times 10^{18}\) 。 可以发现，如果这张图全是单点，即出度全为 \(0\) 时，这就是一个 Nim 游戏。 考虑对每个点进行如下分组： 出度为 \(0\) 的点标号为 \(0\) 。 对原图拓扑排序，每个点的标号是它后继节点的 \(\operatorna...

洛谷P5300 [GXOI/GZOI2019] 与或和 题解 题目链接：P5300 [GXOI/GZOI2019] 与或和 题意： Freda 学习了位运算和矩阵以后，决定对这种简洁而优美的运算，以及蕴含深邃空间的结构进行更加深入的研究。 对于一个由非负整数构成的矩阵，她定义矩阵的 \(\texttt{AND}\) 值为矩阵中所有数二进制 \(\texttt{AND(\&)}\) 的运算结果；定义矩阵的 \(\texttt{OR}\) 值为矩阵中所有数二进制 \(\texttt{OR(|)}\) 的运算结果。 给定一个 \(N \times N\) 的矩阵，她希望求出： 1. 该矩阵的所有子矩阵的 \(\texttt{AND}\) 值之和（所有子矩阵 \(\texttt{AND}\) 值相加的结果）。 2. 该矩阵的所有子矩阵的 \(\texttt{OR}\) 值之和（所有子矩阵 \(\texttt{OR}\) 值相加的结果）。 接下来的剧情你应该已经猜到——Freda 并不想花费时间解决如此简单的问题，所以这个问题就交给你了。 由于答案可能非常的大，你只需要输出答案对...

洛谷P8348 「Wdoi-6」未知之花魅知之旅 题解 题目链接：P8348 「Wdoi-6」未知之花魅知之旅 题意： 称一个长度为 \(n\) 的正整数数列是「\(k\) - 好」的，当且仅当它满足以下条件： 对于 \(1< i< n\)，满足 \(a_{i-1},a_i,a_{i+1}\) 中最大的一个等于其他两个之和。 所有元素都不小于 \(k\)。 \(T\) 组询问，每次询问给定 \((a_0,a_1,x,y,k)\)，问是否存在「\(k\) - 好」数列（长度不小于 \(2\)），前两项为 \(a_0,a_1\) 并且有相邻两项依次为 \(x,y\) 。 输入格式： 第一行输入一个正整数 \(T\)，表示数据组数，对于每一组数据： 每行输入 \(5\) 个正整数，以空格隔开，分别为 \(a_0,a_1,x,y,k\)，含义如题目所述。 输出格式： 对于每一组数据，输出一行 yes 或 no，即是否存在一种可以使得神社变得美观的方法。 数据范围： \(1 \leq \max(a_0,a_1,x,y,k) \leq 10^9,1 \leq T \...

K–Nim 游戏 K–Nim 游戏是 Nim 游戏的推广。 描述 有 \(n\) 堆石子，其中第 \(i\) 堆有 \(a_i\) 个，每次可以从 \(1\) 到 \(k~(k \le n)\) 堆石子中取走任意个石子，不能操作者失败。 结论 记 \(x\) 二进制下的第 \(i\) 位为 \((x)_i\) ，若对于任意 \(s\) 均有 \[ \sum_{i=1}^n\left(a_i\right)_s \equiv 0\pmod{k+1} \] 则先手必败；否则先手必胜。 换言之，只要 \(a_i\) 在二进制下某一位的和模 \(k+1\) 为不为 \(0\) ，先手必胜。 证明 考虑证明上述策略可以将 K–Nim 游戏转化为有向图游戏。 记先手必胜态为 \(\rm N\) ，必败态为 \(\rm P\) 。有向图游戏有如下性质： 终止状态为 \(\rm P\) 。 \(\rm P\) 的后继均为 \(\rm N\) 。 \(\rm N\) 的后继存在至少一个 \(\rm P\) 。 那么我们只需证明最优策略满足以上性质即可： 所有堆为 \(0\) 是终止状态，显然...

洛谷P2490 [SDOI2011] 黑白棋 题解 题目链接：P2490 [SDOI2011] 黑白棋 题意： 小 A 和小 B 又想到了一个新的游戏。 这个游戏是在一个 \(1 \times n\) 的棋盘上进行的，棋盘上有 \(k\) 个棋子，一半是黑色，一半是白色。 最左边是白色棋子，最右边是黑色棋子，相邻的棋子颜色不同。 小 A 可以移动白色棋子，小 B 可以移动黑色的棋子，其中白色不能往左，黑色不能往右。他们每次操作可以移动 \(1\) 到 \(d\) 个棋子。 每当移动某一个棋子时，这个棋子不能跨越两边的棋子，当然也不可以出界。当谁不可以操作时，谁就失败了。 小 A 和小 B 轮流操作，现在小 A 先移动，有多少种初始棋子的布局会使他胜利呢？ 输入格式： 输入三个数 \(n,k,d\)。 输出格式： 输出小 A 胜利的方案总数。答案对 \(10^9+7\) 取模。 数据范围： 保证 \(1 \leq d \leq k \leq n \leq 10^4\)，\(k\) 为偶数，\(k \leq 100\)。 由于终止状态一定是 “……黑白…黑白…黑白……” 的情况...

洛谷P3172 [CQOI2015] 选数 题解 题目链接：P3172 [CQOI2015] 选数 题意： 我们知道，从区间 \([L,H]\)（\(L\) 和 \(H\) 为整数）中选取 \(N\) 个整数，总共有 \((H-L+1)^N\) 种方案。小 z 很好奇这样选出的数的最大公约数的规律，他决定对每种方案选出的 \(N\) 个整数都求一次最大公约数，以便进一步研究。然而他很快发现工作量太大了，于是向你寻求帮助。你的任务很简单，小 z 会告诉你一个整数 \(K\)，你需要回答他最大公约数刚好为 \(K\) 的选取方案有多少个。 由于方案数较大，你只需要输出其除以 \(10^9+7\) 的余数即可。 输入格式： 输入一行，包含四个空格分开的正整数，依次为 \(N,K,L,H\)。 输出格式： 输出一个整数，为所求方案数除以 \(10^9 + 7\) 的余数。 数据范围： 对于 \(100\%\) 的数据，\(1\le N,K\le 10^9\)，\(1\le L\le H\le 10^9\)，\(H-L\le 10^5\)。 设 \(F(k)\) 表示从 \([L,R]...

洛谷P1829 [国家集训队] Crash的数字表格 / JZPTAB 题解 题目链接：P1829 [国家集训队] Crash的数字表格 / JZPTAB 题意： 给定 \(n,m\) 求 \[ \sum_{i=1}^n \sum_{j=1}^m \operatorname{lcm}(i, j) \] 模 \(20101009\) 的结果。 数据范围：\(1\le n,m \le 10^7\) 。 来讲一个杜教筛的解法吧。 首先先规定一下 \(n \le m\) ，然后开始推式子 \[ \begin{aligned} \mathrm{Ans} &= \sum_{i=1}^n \sum_{j=1}^m \frac{i \cdot j}{\gcd(i, j)} \\[6pt]&= \sum_{i=1}^n \sum_{j=1}^m \sum_{d|i, d| j}\left[\gcd\left(\frac{i}{d}, \frac{j}{d}\right)=1\right]\cdot \frac{i \cdot j}{d} \\[6pt]&= \sum_{...

洛谷P3768 简单的数学题 题解 题目链接：P3768 简单的数学题 题意： 输入一个整数 \(n\) 和一个整数 \(p\)，你需要求出： \[ \left(\sum_{i=1}^n\sum_{j=1}^n ij \gcd(i,j)\right) \bmod p \] 其中 \(\gcd(a,b)\) 表示 \(a\) 与 \(b\) 的最大公约数。 输入格式： 一行两个整数 \(p,n\)。 输出格式： 一行一个整数表示答案。 数据范围： \(1\le n \le 10^{10},~5 \times 10^8 \leq p \leq 1.1 \times 10^9\) 且 \(p\) 为质数。时限 4s。 考虑欧拉反演。 \[ \begin{aligned} \sum_{i=1}^n \sum_{j=1}^n i j \operatorname{gcd}(i, j) & =\sum_{i=1}^n \sum_{j=1}^n i j \sum_{k\mid i,\, k\mid j} \varphi(k) \\[4pt]& =\sum_{k=1}^n \v...

[AGC024E] Sequence Growing Hard 题解 题目链接：[AGC024E] Sequence Growing Hard 题意： 给定 \(n,m,P\) ，问有多少个序列组 \((A_0,A_1,\cdots,A_n)\) 满足： 序列 \(A_i\) 的元素个数为 \(i\) ； 所有元素都在 \([1,m]\) 内； \(\forall i\in[0,n)\) ，\(A_i\) 是 \(A_{i+1}\) 的子序列且 \(A_i\) 的字典序小于 \(A_{i+1}\) 。 输出在\(\bmod P\) 意义下的答案. 数据范围： \(1\le n, m \le 300,~2\le P \le 10^9\) 。 正着考虑看上去很麻烦，不妨反着来看这个序列组。 显然这个序列组就是从 \(A_n\) 删除某个元素得到 \(A_{n-1}\) ，再删除一个得到 \(A_{n-2}\) ，以此类推。 那么根据字典序的性质，如果我们删除 \(i\) 位置的元素，得到一个字典序更小的， 就要求 \(i\) 后面第一个不等于它的元素比它小，因为 \(a_{i...

洛谷P3673 小清新计数题 题解 题目链接：P3673 小清新计数题 题意： 小 A 正在电脑上玩一个叫做 Truth or Lie 的游戏。 游戏开始时电脑会给出 \(n\) 句话，每句话形如「第 \(x\) 句话为真」或「第 \(x\) 句话为假」， 其中 \(x\) 是一个 \(1\) 到 \(n\) 的整数，你只要选择 Good 或者 Bad，Good 表示可以决定每句话的真假使每句话的内容都成立，Bad 反之。 作为一个菜鸡，小 A 只会不停地点 Good，靠脸过关。 在无数次失败后，非洲人小 A 发现游戏每关中，每句话包含的是「真」还是「假」是固定的，但是每句话中的 \(x\) 是在 \(1\) 到 \(n\) 均匀随机的。 现在小 A 告诉了你某一关每句话的真假，用一个 \(01\) 序列表示。第 \(i\) 位为 \(0\) 表示第 \(i\) 句话包含「假」，否则表示包含「真」。现在他想要知道使得点击 Good 正确的方案数。 由于方案数可能比较大，你需要输出方案数对 \(998244353\) 取模的结果。 输入格式 一行一个 \(01\) 序列，它的长度...