第１章　牌及びその種類、組み合わせ

御朱印帐一代目堂堂毕业！特此留念！翻开这本御朱印帐，满满的回忆铺面而来，上面除了蒐集每个神社的朱印作为参拜证明以外，更是记载了我在日本旅行的足迹。本文将跟随每个朱印的脚步，回忆和总结每个朱印背后的回忆。

序言

首先是这本御朱印帐！

题目来源: 2022 ICPC Asia EC 网络赛第一场: J. Gachapon

比赛链接: https://pintia.cn/market/item/1571156622976593920

题面

考虑抽卡操作: 若第 \(1\) 次操作至第 \(i-1\) 次操作都为操作失败, 则第 \(i\) 次操作成功的概率为 \(p_i\), 成功后停止操作, 否则进行第 \(i+1\) 次操作. 现给定正整数 \(X,Y\), 构造数列 \(\{p_i\}\) 满足下述条件:

1. 第 \(X\) 次操作一定成功. 即 \(p_X=1\).
2. 第 \(1\) 次至第 \(X-1\) 次操作都不能保证一定成功. 即 \(\forall i\in[1,X), p_i<1\).
3. 任何操作都不能不可能成功. 即 \(\forall i, p_i>0\).
4. 期望上是第 \(Y\) 次抽卡成功.

数据范围

\[ 1<Y<X\le100 \]

输出格式

\(\forall i\), \(p_i\) 需为 \([0,1]\) 中的有理数. 设 \(p_i=a_i/b_i\), 其中 \(a_i,b_i\) 为正整数且 \(\gcd(a_i,b_i)=1\), 则 \(a_i,b_i\) 需满足: \[ 0\le a_i,b_i\le10^4 \] 输出 \((a_i,b_i)\) 表示 \(p_i\).

题目来源: 2023 ICPC 陕西省赛: D. Function

题面

给定函数 \(f\) 满足: \[ f(x)=\begin{cases} \displaystyle 1+\sum_{k=2}^a f(kx)&x\le n\\ 0&x>n \end{cases} \] 输入 \(n\), 求 \(f(1)\bmod p\). 其中 \(a=20210926\), \(p=998244353\).

数据范围

\[ 1\le n\le10^9 \]

题面

现有 \((3k+1)\times(3k+2)\) 大小的网格, 需要在每个网格中填写 \(0,1,2\) 中的一个数字, 使得网格中任意一行数字之和、任意一列数字之和均为 \(3\) 的倍数. 求网格中 \(1\)​ 的数量的最大值.

原题目 \(k=668\), 我们可以扩展至任意 \(\newcommand{\mbb}{\mathbb}k\in\mbb N\).

题面

给定长度为 \(n\) 的序列 \(A\) 和 \(B\). 一次 \(k\)-区间轮换是指: 选择 \(A\) 中一个长度为 \(k\) 的子区间, 将区间内的数字进行轮换. 求最大的 \(k\le n\), 满足: 对 \(A\) 进行若干次 \(k\)-区间轮换后, 可以将 \(A\) 变为 \(B\). 若没有 \(k\) 满足条件, 输出 \(-1\).

数据范围

\[ 1\le n\le 2\times 10^5 \]

题目来源: 2022 ICPC 华为上海训练营 Day3: G. Matrices and Determinants

题面

一共 \(T\) 组数据.

给定 \(n\times n\) 矩阵 \(\newcommand{\mathbs}[1]{\boldsymbol{ #1 }}\newcommand{\mbs}{\mathbs}\newcommand{\mbb}{\mathbb}\mbs A\in M_n(\mbb Z)\), 其所有元素均为整数. 请求出矩阵 \(\mbs B,\mbs C\in M_n(\mbb Z)\), 所有元素均为整数, 满足: \(\mbs B\mbs C=\mbs A\) 且 \(\newcommand{\abs}[1]{\left| #1 \right|}\abs{\mbs B}=\abs{\mbs C}\ne0\). 如无解, 输出 No. 如有多组满足题意的解, 请输出任意一种.

数据范围

\(1\le T\le 10000\).

\(1\le n\le 4\), \(\mbs A\) 中的所有元素均为整数,且元素 \(A_{ij}\) 满足 \(-10\le A_{ij}\le10\).

题目来源: 2019 ICPC Asia EC Final: H. King

题目来源: XJTUOJ-1223 zxh的一气通贯

题目链接: https://oj.xjtuicpc.com/problem/1223

题面

一共 \(T\) 组数据.

给定素数 \(p\), 以及长度为 \(n\) 的序列 \(a_1,a_2,\cdots, a_n\).

需要找出满足下列条件的子序列 \(b_1,b_2,\cdots,b_m\) 的最大长度:

1. 子序列长度 \(m\ge n/2\).
2. \(\forall i\in[1,m)\cap\mathbb N\), \(\exists q\in\mathbb N\), s.t. \(qb_i\equiv b_{i+1}\pmod p\). 即子序列在模 \(p\) 意义下是等比子序列.

若不存在这种子序列, 输出 -1.

数据范围

\[ 1\le T<1000 \]

\[ 1\le n\le2\times10^5 \]

\[ 2\le p\le10^9+7 \]

\[ 1\le a_1,a_2,\cdots,a_n<p \]

保证输入的 \(p\) 是素数. 数据组中 \(n\) 的总和不超过 \(2\times10^5\).

简介

GB/T 12345-1990（也称 GB/T 12345 或 GB/T 12345-90）标准全称《信息交换用汉字编码字符集　辅助集》，简称 GB1，俗称 GB12345，是 GB/T 2312-1980 的繁体版本。该标准于1990年发布，共有6866个汉字，其中6763个汉字（B0A1-F7FE）与 GB/T 2312-1980 对应，103个汉字（F8A1-F9A9）是一简对多繁而产生的增补字。

该标准广泛用于字体的“伪繁体”版本。

但互联网上目前只有 GB/T 2312-1980 的字符表，没有 GB/T 12345-1990 的电子版字符表。几经辗转，在编码转化库 libiconv 中找到了 GB/T 12345-1990 的 Unicode 编码表。本文以此为凭据，列出 GB/T 12345-1990 的电子字符表。

题目来源: 2020 CCPC Wannafly 冬令营 Day5: H. Geometry PTSD

题面

在以 \(O\) 为球心的单位球面上寻找三个点 \(A, B, C\), s.t.: \[ \min(|AB|,|BC|,|CA|)\geq1.7 \]

\[ 0<d(O,ABC)\leq10^{-18} \]

输出格式

每行输出三个整数 \(x,y,z\in[-10^{6},10^6]\cap\mathbb Z\), 表示选取了点 \[ \left(\frac{x}{\sqrt{x^2+y^2+z^2}},\frac{y}{\sqrt{x^2+y^2+z^2}},\frac{z}{\sqrt{x^2+y^2+z^2}}\right) \]

题目来源: 2023 ICPC 陕西省赛: J. Teleport

题面

在 \(n\times n\) 的网格中, 有些格点可以通过 (用.表示), 有些格点不可通过 (用*表示). 你需要从 \((1,1)\) 移动到 \((n,n)\). 保证 \((1,1)\) 和 \((n,n)\) 两个点是可以通过的.

当你在 \((x,y)\) 时, 你可以在一个单位时间内移动到以下点中的一个:

1. \((x+1,y)\) 或 \((x-1,y)\) 或 \((x,y+1)\) 或 \((x,y-1)\);

2. \(f^i(x,y)\), 其中 \(i\) 是任意的整数 \(i\le k\).

不能移动到不可通过的点或者地图外的点. \(f^i(x,y)\) 的定义为: \[ f^i(x,y)=\begin{cases}(x,y)&i=0\\f^{i-1}(y+1,x)&i>0\end{cases} \] 求从 \((1,1)\) 移动到 \((n,n)\) 的最短时间, 无解输出 -1.

数据范围

\[ 1\le n,k\le5000 \]

A. 多态练习一工资系统

实现课本例9-3题目要求。根据4类不同员工类型分别进行工资的计算。

抽象基类Employee表示员工，这个类派生出SalariedEmployee、HourlyEmplyee和CommissionEmployee类，CommissionEmployee类派生出BasePlusCommissionEmployee类。（课本例9-3图）

1.固定工：每周工资一样，与工作时间长短无关，由SalariedEmployee类实现；

2.计时工：按时计酬，超过40小时算加班工资，由HourlyEmplyee类实现；

3.雇佣员工：按销售百分比例计算，由CommissionEmployee类实现；

4.底薪雇佣员工：在底薪之上增加销售百分比。在本期内，公司准备对底薪雇佣员工升薪10%，由BasePlusCommissionEmployee类实现。

在主函数中

创建4个派生类的对象，调用Earning(）方法输出。

多态的使用，创建含有4个派生类元素的Employee数组，调用Earning(）方法输出。

【注：】此题编译通过即可

A. Circle类的继承

定义圆类Circle，包含半径r，属性R能判断半径r的合理性（r>0），计算圆面积的方法double Area()。

从Circle类派生出圆柱体类Cylinder类。该类新增圆柱体的高h，属性H能判断高h的合理性（h>0），新增计算圆柱体体积的方法double Volume()。

如果半径、高不合法，就设置其值为0。

在Main方法中，创建一个Cylinder对象，输入半径和高（两行输入），并输出该对象的底面半径，高，底面积以及体积（面积和体积用double Math.round(doulbe b, int digit) digit取1。

（要求：不使用构造方法，并且类中的字段为私有，方法为公有）

A. 重载方法的练习

在Main函数所在的类，实现两个方法用于计算成绩的平均值，小数点后1位。

public static double AvgGrade(int[] gra) //数值型成绩的平均值。得分1~5之间。课程数无限制。

public static double AvgGrade(string[] sgra) //成绩分为“good”和“ok”两个等级。good等价于4分，ok等价于1分。

在Main方法中，分别调用两种方法，均能输出平均成绩。输入用空格分开。

【注:】

1. 四舍五入的区别请大家了解https://www.cnblogs.com/fanyong/archive/2013/05/30/chinese_round.html 大家选取“传统意义上的四舍五入”的定义方法。
2. 保留*位小数的方法请参考 https://blog.csdn.net/qq_40985921/article/details/85414484

A. 属性的使用

定义Rectangle类，类中的两个属性Length和Width（其对应的私有字段为length和width，默认值为均为1）。

Length属性的set方法中验证其值必须在0~20（开区间）之间的浮点数。如果不满足保持其默认值。

方法：

计算长方形的周长public double Perimeter()

计算长方形的面积public double Area()

输入长方形的长和宽的值，输出长方形的周长、面积。

A. 孪生素数查找程序

所谓孪生素数指的是间隔为2 的相邻素数，就像孪生兄弟。最小的孪生素数是(3, 5)，在100 以内的孪生素数还有(3,5), (5,7), (11,13),(17,19),(29,31),(41,43),(59,61),(71,73) 总计有 8 组。(备注：每组孪生素数之间用英文逗号,分隔）

输入正整数，输出小于等于number的孪生素数的组数。

A. 输入输出练习

在一行内输入5个整数，空格分隔。输出5个整数，逗号分隔。英文符号。（输入的接收请参考课本例题1-5,注意Split()的用法）

A. 计算两个数的和、差、商、积。

从键盘分别输入两个不为0的整数（前2行输入），分别输出这两个整数的和 差 积 商。

题目来源: 2019-2020 XX Opencup GP of Tokyo: E. Count Modulo 2

题目链接: http://codeforces.com/gym/102586/problem/E

题面

一共 \(T\) 组数据.

现有 \(k\) 个 两两不同 的数字 \(A_1,A_2,\cdots,A_k\). 给定正整数 \(N,S\), 构造数列 \(a_1,a_2,\cdots,a_N\), 满足下列条件:

1. \(\displaystyle\sum_{i=1}^Na_i=S\).
2. \(\forall i\in[1,N]\), \(a_i\in\{A_1,A_2,\cdots,A_k\}\).

求构造的方案数在模 \(\mathbf 2\) 意义下的结果.

数据范围

\[ 1\le T\le 5 \]

\[ 1\le N\le10^{18} \]

\[ 0\le S\le 10^{18} \]

\[ 1\le k\le 200 \]

\[ 0\le A_1<A_2<\cdots<A_k\le10^5 \]

题目来源: Educational Codeforces Round 85: E. Divisor Paths

题目链接: https://codeforces.com/contest/1334/problem/E

题目来源: XJTUOJ-1167 zxh的高考幸运法阵

题目链接: https://oj.xjtuicpc.com/problem/1167

题面

给定一个正整数 \(D\), 根据如下规则构造一个图 \(\mathfrak D\):

1. \(\mathfrak D\) 的每一个节点都是 \(D\) 的一个正因数.
2. \(\mathfrak D\) 的两个节点 \(x,y\) 如果满足: \(x>y\), \(y\mid x\) 且 \(x/y\) 是素数, 那么 \(\mathfrak D\) 上就会有一个 \(x,y\) 之间的无向边, 边权为 \(d(x)-d(y)\). 其中 \(d\) 是除数函数, 表示因子个数.

现在有 \(q\) 次询问, 每次询问 \(\mathfrak D\) 中两个节点 \(u,v\) 之间的最短路的个数 \(N(u,v)\), 输出对 \(p\) 取模后的结果.

备注

在 Codeforces 中的题目 \(p=998244353\).

在 XJTUOJ 中的题目 \(p=919260817\). 注意, \(919260817\) 是一个质数.

数据范围

\[ 1\le D\le 10^{15} \]

\[ 1\le q\le3\cdot10^5 \]

\[ 1\le u,v\le D \]

题目来源: XJTUOJ-1168 zxh的后宫管理系统

题目链接: https://oj.xjtuicpc.com/problem/1168

题面

一共 \(T\) 组数据.

现有一个未知的整数 \(k\), 满足 \(1\le k\le n\).

现在你被宣称 \(k\) 的值等于 \(x\), 但是你不知道真假. 你现在可以提交一个任意大的正整数 \(y\), 之后获得返回值 \(\gcd(k,y)\).

你需要寻找一个合适的 \(y\), 使得你可以通过返回值来查验 \(x\) 和 \(k\) 是否相等. 如果有很多满足条件的值, 选阿泽最小的那个. 如果没有合适的 \(y\), 输出 \(-1\).

由于 \(y\) 很大, 输出对 \(920011128\) 取模后的结果.

简要描述

给定 \(n, x\), 试给出一个最小的 \(y\), 使得 \(\forall 1\le a\le n\), 若 \(a\ne x\), 则 \(\gcd(a,y)\ne \gcd(x,y)\). 由于 \(y\) 很大, 输出对 \(920011128\) 取模后的结果.

数据范围

\[ 1\le T<10 \]

\[ 1\le k\le n\le10^7 \]

题目来源: 2020 CCPC Wannafly 冬令营 Day1: H. 最大公约数

题面

一共 \(T\) 组数据.

现有一个未知的整数 \(k\), 满足 \(1\le k\le n\).

现在你被宣称 \(k\) 的值等于 \(x\), 但是你不知道真假. 你现在可以提交一个任意大的正整数 \(y\), 之后获得返回值 \(\gcd(k,y)\).

你需要输出一个合适的 \(y\), 使得你可以通过返回值来查验 \(x\) 和 \(k\) 是否相等. 如果有很多满足条件的值, 输出最小的那个. 如果没有合适的 \(y\), 输出 \(-1\).

简要描述

给定 \(n, x\), 试给出一个最小 \(y\), 使得 \(\forall 1\le a\le n\), 若 \(a\ne x\), 则 \(\gcd(a,y)\ne \gcd(x,y)\).

数据范围

\[ 1\le T\le 50 \]

\[ 1\le k\le n\le500 \]

题目来源: XJTUOJ-1143 ddd和万马奔腾

题目链接: https://oj.xjtuicpc.com/problem/1143

题面

数论描述

给定 \(n\) 个正整数 \(m_1,m_2,\cdots,m_n\), 判断每个 \(m\) 是不是模 \(p\) 意义下的 \(k\) 次剩余。多个 \(m\) 符合条件按从小到大顺序输出.

通俗描述

给定 \(n\) 个正整数 \(m_1,m_2,\cdots,m_n\), 判断每个 \(m\) 是否满足:

1. \(\gcd(m,p)=1\).
2. 存在一个整数 \(a\), 使得 \(a^k\equiv m\pmod p\).

如果一个数 \(m\) 满足上述两个条件, 则称 \(m\) 是模 \(p\) 意义下的 \(k\) 次剩余。多个 \(m\) 符合条件按从小到大顺序输出.

\(x\equiv y\pmod p\) 的定义是 \(p\mid(x-y)\), 等价描述是存在整数 \(b\) 使得 \(x-bp=y\).

数据范围

\[ 1<k\le10^5 \]

\[ 1<p\le10^5 \]

\[ 1\le n,m<p \]

该模板为作者原创.

问题引入

请输出对 \(p\) 取模后的结果.

请输出模 \(p\) 意义下的结果.

最终答案可以表示为 \(a/b\), 请输出 \(a\cdot b^{-1}\bmod p\), 其中 \(b^{-1}\) 是 \(b\) 对模 \(p\) 的乘法逆元.

在我们做题的时候, 经常会遇到输出在模 \(p\) 意义下的结果的题目. 上面三种是经典的这种要求的说法.

\[ \newcommand{\isum}[2]{\sum\limits_{ #2 = #1 }^{\infty}} \newcommand{\iprod}[2]{\prod\limits_{ #2 = #1 }^{\infty}} \newcommand{\lsum}[3]{\sum\limits_{ #2 = #1 }^{ #3 }} \newcommand{\lprod}[3]{\prod\limits_{ #2 = #1 }^{ #3 }} \newcommand{\llim}[2]{\lim\limits_{ #1 \rightarrow #2 }} \newcommand{\brac}[1]{\left( #1 \right)} \newcommand{\lrac}[1]{\left\{ #1 \right\}} \newcommand{\flor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\ceil}[1]{\left\lceil #1 \right\rceil} \newcommand{\agle}[1]{\left\langle #1 \right\rangle} \newcommand{\abs}[1]{\left| #1 \right|} \newcommand{\abss}[1]{\left\| #1 \right\|} \newcommand{\id}[1]{\text{( #1 ) }} \newcommand{\mathbs}[1]{\boldsymbol{ #1 }} \newcommand{\mvec}[1]{\overrightarrow{ #1 }} \newcommand{\mbar}[1]{\overline{ #1 }} \newcommand{\bigf}{\displaystyle} \newcommand{\dif}{\mathrm{d}} \newcommand{\ddif}[1]{\frac{\dif}{\dif #1 }} \newcommand{\cddif}[1]{\cfrac{\dif}{\dif #1 }} \newcommand{\eset}{\varnothing} \newcommand{\sh}{\mathrm{sh\ }} \newcommand{\ch}{\mathrm{ch\ }} \newcommand{\Imm}{\mathrm{Im\ }} \newcommand{\Ker}{\mathrm{Ker\ }} \newcommand{\rank}{\mathrm{rank\ }} \newcommand{\diag}{\mathrm{diag\ }} \newcommand{\sgn}{\mathrm{sgn\ }} \newcommand{\simeqq}{\cong} \newcommand{\tdeg}{^\circ} \newcommand{\roku}{\partial} \newcommand{\bksl}{\backslash} \newcommand{\mrm}{\mathrm} \newcommand{\mbb}{\mathbb} \newcommand{\mbf}{\mathbf} \newcommand{\mscr}{\mathscr} \newcommand{\mbs}[1]{\boldsymbol{ #1 }} \newcommand{\kaz}[1]{\begin{cases} #1 \end{cases}} \newcommand{\pmat}[1]{\begin{pmatrix} #1 \end{pmatrix}} \text{数学分析读书报告(2020年春)} \]

在第一学期的数学分析课程中, 我们定义了一整套实数系统. 当时我们先用皮亚诺公理和集合论两种方式定义了自然数集, 然后再用自然数对的商集定义了整数集, 用整数对的集定义了有理数集, 最后又用戴德金分割定义了实数. 然而最近读到了卓里奇的《数学分析》, 在这本书里, 作者用了另一种方式定义了这一套系统: 先给出实数集的公理系统, 之后在逐步导出自然数集, 整数集和有理数集.