Q779’s Blog

CF852B Neural Network country 题解 题目链接：CF852B Neural Network country 题意： 给定一个包含一个出发点 \(s\) ，终止点 \(t\) 以及 \(L\) 层 \(V_1,V_2,\dots,V_L\) ，每层都包含 \(N\) 个顶点的带边权有向分层图。从出发点 \(s\) 到第一层 \(V_1\) 中每个顶点都有一条带权边，从最后一层 \(V_L\) 到终止点 \(t\) 中每个顶点也都有一条带权边。对于所有 \(1\le i<L\) ，第 \(i\) 层的每个顶点到第 \(i+1\) 层中的每个顶点都会连有一条带权有向边，且第 \(i\) 层的每个顶点连出的边权完全相同，并且任意相邻两层之间所连边权完全相同。可以参照样例解释中链接内图示结合样例帮助理解。 现给出该分层图，你需要计算有多少种从 \(s\) 走到 \(t\) 的路径，使得路径上经过边权值和能被 \(M\) 整除？由于答案可能过大，你需要将答案对 \(10^9+7\) 取模后输出。 对于 \(100\%\) 的数据，\(1\le N\le 1...

CF691E Xor-sequences 题解 题目链接：CF691E Xor-sequences 题意：给定大小为 \(n\) 的集合 \(\{a_1,\dots,a_n\}\)，从集合中选择 \(k\) 个数组成一个序列 \(x_1 , \dots , x_k\) (可以重复选择)，使得序列满足 \(x_i\) 与 \(x_i +1\) 异或的二进制中 \(1\) 的个数是 \(3\) 的倍数 问长度为 \(k\) 的满足条件的序列的种数，答案对 \(10^9 + 7\)取模。 \(1\le n\le 100,~1\le k,a_i \le 10^{18}\) 设 \(f_{i,j}\) 表示序列长度为 \(i\) 且最后一个数为 \(a_j\) 时的方案数，则 \[ f_{0,j}=1 \\\\f_{i,j}=\sum_{1\le k \le n}f_{i-1,k}\times g_{k,j} \] 其中 \(g_{k,j}\) 表示 \(\left[3 \mid (a_k \oplus a_j)_{\texttt{ 2进制下1的数量}}\right]\) 可以发现这个...

Atcoder Educational DP Contest R Walk 题解 题目链接：Atcoder Educational DP Contest R Walk 题意： 给一张 \(N\) 个结点的有向简单图，给出邻接矩阵 \(A\) ，求长度为 \(K\) 的路径条数，答案对 \(10^9+7\) 取模。 \(1 \le N \le 50,1\le K \le 10^{18}\) ， \(a_{i,j}\) is 0 or 1 ，\(a_{i,i}=0\) 设 \(f_{k,i,j}\) 表示 \(i\) 到 \(j\) 路径长为 \(k\) 的方案数，则 \[ f_{k,i,j}=\sum_{(s,j) \in E} f_{k-1,i,s} \] 之所以不从 \(k-t\) 转移，而从 \(k-1\) 转移，是因为可能存在重复计数 比如这张图 就可能重复计数 上面的式子可以进一步化简 \[ f_{k,i,j} = \sum_{1\le s \le n} f_{k-1,i,s}\times A_{s,j} \] 这个形式是不是很熟悉？ \[ f^{0}_{i,j} ...

OI数学总结-基础公式&结论 施工中，咕咕咕… \(A(n) = 1 + \dfrac{1}{\sqrt{2}}+\dfrac{1}{\sqrt{3}}+\dots+\dfrac{1}{\sqrt{n}}\) ，积分逼近有 \(A(n) = \Theta(\sqrt{n})\) \(B(n) = 1+\sqrt{2}+\sqrt{3}+\dots\sqrt{n}\) ，积分逼近有 \(B(n) = \Theta(n\sqrt{n})\) 调和级数求和 \(C(n) = 1 + \dfrac{1}{2}+\dfrac{1}{3}+\dots+\dfrac{1}{n}\) ，积分逼近有 \(C(n) = \Theta(\ln n)\) 著名的巴塞尔问题，证明 \[ \displaystyle \zeta(2)= \sum_{n = 1}^{\infty} \frac{1}{n^2} =\lim_{n \to +\infty}\left( 1 + \frac{1}{4} + \frac{1}{9}+\cdots+\frac{1}{n^2}\right)=\frac{\pi^2...

线性代数-矩阵 施工中，咕咕咕…. 矩阵乘法 1. 矩阵乘法的定义 矩阵乘法的定义 \[ (AB)_{i,j}=\sum_{k=1}^{m}A_{i,k}B_{k,j}\quad i\in[1,n],j\in[1,p] \] 一个 \(n \times m\) 的矩阵和 \(m\times p\) 的矩阵相乘，答案为一个 \(n \times p\) 的矩阵 注意，矩阵乘法没有叉乘的定义，因为叉乘通常是指在向量空间中的一种运算 列向量可以右乘矩阵（左乘需要转置为行向量），且乘积不一定相等：\(Mv \not\Leftrightarrow v^{\top}M\) 2. 快速手算 矩阵乘法的计算方法有很多种，这里提供两种方法。 第一种是传统的逆时针旋转右侧矩阵，可以在这里看动画演示。 第二种是 Roundgod 老师告诉我们的方法，如下 例： \[ \begin{bmatrix}1&2\\3&4\\\end{bmatrix} \times \begin{bmatrix}5&6\\7&8\\\end{bmatrix} \] 第一行： \[ \begin{...

ABC156E Roaming 题解 题目链接：ABC156E Roaming 题意： 翻译来自我们模拟赛，可能和原题有区别 输入两个数字 \(n,k\) ，初始时有 \(n\) 个盒子，每个盒子中都装着一个小球，\(n\) 个小球之间不可区分。现在你要进行下列操作恰好 \(k\) 次 选择任意一个盒子中的一个小球，将它放到一个不同的盒子中 你需要算出在 \(k\) 次操作之后，小球的不同的摆放方式有多少种，答案对 \(10^9+7\) 取模。两种摆放小球的方式被认为是不同的，当且仅当存在某一个盒子在两种摆放方式中放了不同个数的小球。 \(3 \le n \le 10^5,~2 \le k \le 10^9\) Roundgod老师：这道题需要很好的观察能力 注意到 \(k \ge n-1\) 时方案数等于 \(n-1\) 的方案数 因为至多 \(n-1\) 步就可以摆出所有的情况，例如 5,0,0,0,0 只要 \(4\) 步 而步数是可以浪费的，比如本来要把 \(1\) 的一个球移到 \(2\) ， 可以先移到 \(3\) 再移到 \(2\) ，这样就浪费了一步，这样...

ABC167E Colorful Blocks 题解 题目链接：ABC167E Colorful Blocks 题意： 翻译从我们模拟赛搬过来的，稍微有些不一样。 有 \(n\) 个小球按照编号为 \(1−n\) 从左至右放成一排，你现在要给每个小球染上 \(1−m\) 中的颜色，并且满足至多存在 \(k\) 对相邻位置上小球的颜色相同。 你需要输出一共有多少种不同的给小球染色的方案，两种染色方案被认为是不同的当且仅当两种方案中存在一个小球被染上了不同的颜色。由于答案可能过大，你需要对 \(998244353\) 取模后输出。 \(1 \le n,m \le 2\times 10^5,~0\le 0 \le n-1\) 简单组合数学。考虑 \(k\) 对相邻的情况， 其实就是在前 \(n-1\) 个球中选 \(k\) 个和它右边的合并 因此答案就是 \[ \sum_{i=0}^{k} m \times(m-1)^{n-i-1}\times \dbinom{n-1}{i} \] 前面的 \(m \times(m-1)^{n-i-1}\) 可能比较难理解 其实就是一个经典模型： ...

模拟赛题讲解[9] 来自 Roundgod 2022-07-29 noi.ac #2693 原题来自 ABC172E NEQ 问题描述： 给定 \(n,m\)，你需要计算满足以下条件的数组对 \(A=[a_1,a_2,\dots,a_n]\) 和 \(B=[b_1,b_2,\dots,b_n]\) 的个数: 对于所有 \(1\leq i\leq n\) ，都有 \(1\leq a_i\leq m\) 以及 \(1\leq b_i\leq m\). 对于所有 \(1\leq i\leq n\) ，都有 \(a_i\neq b_i\). 对于所有的 \(1\leq i\lt j\leq n\) ，都有 \(a_i\neq a_j\) 且 \(b_i\neq b_j\). 由于答案可能过大，你需要输出答案对 \(10^9+7\)取模后的值。 输入格式： 输入第一行包含一个整数 \(t(1\leq t\leq 10)\) ，表示数据的组数。 对于每组测试数据，输入为一行，包含两个整数 \(n,m\)。 输出格式： 对于每组测试数据，在一行中输出一个整数，表示答案。 输入1： 2 2 ...

hdu4135 Co-prime 题解 题目链接：hdu4135 Co-prime 题意： \(T\) 组数据，每组给出 \(a,b,n\) ，求区间 \([a,b]\) 中有多少个数与 \(n\) 互质。 Given a number \(N\), you are asked to count the number of integers between \(A\) and \(B\) inclusive which are relatively prime to \(N\). Two integers are said to be co-prime or relatively prime if they have no common positive divisors other than \(1\) or, equivalently, if their greatest common divisor is \(1\). The number \(1\) is relatively prime to every integer. \(1 \le a\le b\le 10^{...

OI数学总结-组合数学 施工中，咕咕咕…. 排列组合 更多详见 小蓝书 16.1 下面两个指的是无重复的排列与组合 排列数 从 \(n\) 个不同元素中取 \(k(k\le n)\) 个不同元素，并按一定顺序排成一列的方案数 \[ \mathrm{A}_{n}^{k} = \frac{n!}{(n-k)!} \] 也可写作 \(\mathrm{P}_{n}^{k}\) 或直接用组合数写法 \(k! \times \binom{n}{k}\) 代码求解 \(O(n)\) 计算 例如求解 \(A_{n-m+1}^{m} \bmod p\) int res=1; for(int i=n-m+1; i>=n-2*m+2; i--) res=res*i%p; cout << res << '\n' 组合数 从 \(n\) 个不同元素中取 \(k(k \le n)\) 个不同元素的方案数 \[ \binom{n}{k} = \dfrac{n!}{k!(n-k)!} \] 高中一般记作 \(\mathrm{C}_n^{k}\) ，不是很推荐使用。 特别地，规定当...

CF1000D Yet Another Problem On a Subsequence 题解 题目链接：CF1000D Yet Another Problem On a Subsequence 题意： 如果一个数组 \([a_1,a_2,a_3,...,a_n]a_1=n-1\) 并且 \(a_1>0\) ，这个数组就被叫为好数组，如果一个序列能正好分为多个好数组，ta就被叫为好序列，现在给定一个序列，求这个序列有多少好子序列，答案对 \(998244353\) 取模。 The sequence of integers $ a_1, a_2, , a_k $ is called a good array if $ a_1 = k - 1 $ and $ a_1 > 0 $ . For example, the sequences $ [3, -1, 44, 0], [1, -99] $ are good arrays, and the sequences $ [3, 7, 8], [2, 5, 4, 1], [0] $ — are not. A sequence ...

ABC210E Ring MST 题解 题目链接：ABC210E Ring MST 题意：给定一张 \(n\) 个点的无向图，顶点的编号为 \(0,1,\dots,n−1\) 。同时给出两个长度为 \(m\) 的数组 \(a_1,a_2,\dots,a_m\) 和 \(b_1,b_2,\dots,b_m\) 。初始时图中并没有任何边，你可以按照以下操作加边: 选择一个 \(1\le i\le m\) 和一个 \(0<x<n\) ，并在顶点 \(x\) 和顶点 \((x+a_i) \bmod n\) 中添加一条长度为 \(b_i\) 的边。 你现在想要知道，你添加的边的长度总和至少为多少，才能使得整个图连通?如果无论如何都不能使整个图连通，输出 \(−1\) 。 数据范围： \(1 \le a_i < n \le 10^9,~1 \le m \le 10^5,1\le b_i \le 10^9\) 首先我们可以想到把 \((x,(x+a_i)\bmod n)\) 看作一条边 然后答案就是最小生成树，跑个 \(\text{kruskal}\) 不过这个是 \(O...