11D_Beyonder's Blog

题目描述 对于一个 nnn 个定点的凸多边形，他的任何三条对角线都不会交于一点。请求图形中对角线交点的个数。 例如，六边形： 输入格式 第一行一个 nnn，代表边数。 输出格式 第一行输出交点数量 输入输出样例 输入1 3 输出1 0 输入2 6 输出2 15 说明/提示 $50\%$ 的测试数据 $3\leqslant n\leqslant100$; $100\%$ 的测试数据 $3\leqslant n\leqslant 100000$。 分析 由于任何三条对角线不会交于一点，故对于每一个交点，只有两条对角线经过，所以一个交点与四个顶点相关联，即四个顶点确定一个交点，答案为Cn4=n(n−1)(n−2)(n−3)24C_n^4=\frac {n(n-1)(n-2)(n-3)}{24}Cn4​=24n(n−1)(n−2)(n−3)​。直接这样算用```unsigned long long``也会爆，所以可以将式子改写为$\frac{{\frac{{\frac{{n(n - 1)}}{2} \times (n - 2)}}{3} \times (n - 3)} ...

A. Contest for Robots Polycarp is preparing the first programming contest for robots. There are nnn problems in it, and a lot of robots are going to participate in it. Each robot solving the problem$ i$ gets$ p_i$ points, and the score of each robot in the competition is calculated as the sum of pip_ipi​ over all problems$ i$ solved by it. For each problem, pip_ipi​ is an integer not less than$ 1$. Two corporations specializing in problem-solving robot manufacturing, “Robo-Coder Inc.” and “B ...

题目描述 石头剪刀布是常见的猜拳游戏:石头胜剪刀,剪刀胜布,布胜石头。如果两个人出拳一 样，则不分胜 负。在《生活大爆炸》第二季第8集中出现了一种石头剪刀布的升级版游戏。 升级版游戏在传统的石头剪刀布游戏的基础上,增加了两个新手势: 斯波克:《星际迷航》主角之一。 蜥蜴人:《星际迷航》中的反面角色。 这五种手势的胜负关系如表一所示,表中列出的是甲对乙的游戏结果。 现在,小 A和小 B尝试玩这种升级版的猜拳游戏。已知他们的出拳都是有周期性规律的，但周期长度不一定相等。例如：如果小A以“石头-布-石头-剪刀-蜥蜴人-斯波克”长度为 666 的周期出拳,那么他的出拳序列就是“石头-布-石头-剪刀-蜥蜴人-斯波克-石头-布-石头-剪刀-蜥蜴人-斯波克-…”,而如果小B以“剪刀-石头-布-斯波克-蜥蜴人”长度为 555 的周期出拳,那么他出拳的序列就是“剪刀-石头-布-斯波克-蜥蜴人-剪刀-石头-布-斯波克-蜥蜴人-…” 已知小 A和小 B 一共进行 $N $次猜拳。每一次赢的人得 111分，输的得 000 分；平局两人都得 000 分。现请你统计 NNN 次猜拳结束之后两人的得分。 ...

A-细胞分裂 题目描述 CB不光是ACM大佬，同时也是生物领域的知名专家。现在，他正在为一个细胞实验做准备工作：培养细胞样本。 CB博士手里现在有N种细胞，编号从1~N，一个第i种细胞经过1秒钟可以分裂为Si个同种细胞（Si为正整数）。现在他需要选取某种细胞的一个放进培养皿，让其自由分裂，进行培养。一段时间以后，再把培养皿中的所有细胞平均分入MMM个试管，形成MMM份样本，用于实验。CB博士的试管数MMM很大，普通的计算机的基本数据类型无法存储这样大的MMM值，但万幸的是，MMM总可以表示为m1m_1m1​的m2m_2m2​次方，即M=m1m2M=m_1^{m_2}M=m1m2​​ ，其中m1,m2m_1,m_2m1​,m2​ 均为基本数据类型可以存储的正整数。 注意，整个实验过程中不允许分割单个细胞，比如某个时刻若培养皿中有4个细胞，Hanks博士可以把它们分入2个试管，每试管内2个，然后开始实验。但如果培养皿中有5个细胞，博士就无法将它们均分入2个试管。此时，博士就只能等待一段时间，让细胞们继续分裂，使得其个数可以均分，或是干脆改换另一种细胞培养。 为了能让实验尽早开始，CB博士在 ...

算法描述 扩展欧几里得算法可直接计算不定方程方程 ax+by=gcd(a,b),(a,b∈Z)ax+by=gcd(a,b),(a,b\in Z)ax+by=gcd(a,b),(a,b∈Z) 的一组整数解，并返回 gcd⁡(a,b)\gcd(a,b)gcd(a,b)。 理论基础 裴蜀定理(Bézout’s lemma) 定理描述 对任何整数 aaa、b{\displaystyle b}b 和 c{\displaystyle c}c，关于未知数 x{\displaystyle x}x 和 y{\displaystyle y}y 的线性丢番图方程：ax+by=c{\displaystyle ax+by=c}ax+by=c 当且仅当 gcd⁡(a,b)∣c\gcd(a,b)|cgcd(a,b)∣c 时有整数解。 证明 先证： 对于任意整数 a,ba,ba,b ，存在一对整数 x,yx,yx,y ，满足 ax+by=gcd(a,b)ax+by=gcd(a,b)ax+by=gcd(a,b)。 在欧几里得算法(Euclidean algorithm)的最后一步，即 b=0 时，显然有一对整数 x= ...

高精度算法模板 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200 ...

题目描述 上课的时候总会有一些同学和前后左右的人交头接耳，这是令小学班主任十分头疼的一件事情。不过，班主任小雪发现了一些有趣的现象，当同学们的座次确定下来之后，只有有限的 DD 对同学上课时会交头接耳。 同学们在教室中坐成了 MMM 行NNN 列，坐在第 iii 行第$ j$ 列的同学的位置是$ (i,j)，为了方便同学们进出，在教室中设置了，为了方便同学们进出，在教室中设置了，为了方便同学们进出，在教室中设置了 K$ 条横向的通道，LLL 条纵向的通道。 于是，聪明的小雪想到了一个办法，或许可以减少上课时学生交头接耳的问题：她打算重新摆放桌椅，改变同学们桌椅间通道的位置，因为如果一条通道隔开了 222个会交头接耳的同学，那么他们就不会交头接耳了。 请你帮忙给小雪编写一个程序，给出最好的通道划分方案。在该方案下，上课时交头接耳的学生的对数最少。 输入格式 第一行，有 555 个用空格隔开的整数，分别是 M,N,K,L,D(2≤N,M≤1000,0≤K<M,0≤L<N,D≤2000)M,N,K,L,D(2 \le N,M \le 1000,0 \le K<M, ...

C-最大模数 题目描述 一次周六新生训练后，一个师妹来找JAJA_Xin。 师妹：“师兄，为什么今天我对面那个师兄那么冷漠。” JAJA_Xin：“噢你居然还不认识大名鼎鼎的魏队，正常啦，魏队很傲的，因为你们太菜，所以你懂的。” 师妹：“那怎么才能让那个师兄觉得我不菜，你可以帮我去问问吗？” 乐于助人的JAJA_Xin怎么可能拒绝师妹呢，跑去问魏队。 魏队：“简单啊，我出一道题，能做出来就不算很菜了，就出一道数学题吧，简单一点，让他们可以做。” Ra=[(a−1)n+(a+1)n]R_a = [ (a−1)^n + (a+1)^n ]Ra​=[(a−1)n+(a+1)n](((modmodmod $ a^2$$)$$ ,(n>0)例如当 例如当例如当a=4, n=2时，时，时，Ra=32 +52 =34$，而34mod16=234mod16 =234mod16=2,故Ra=2R_a=2Ra​=2。由于n可以是任意大于0的正整数，所以存在很多RaRaRa的解，找到任意一个Ra就算做出来这道题。例如，当a=4a=4a=4的时候，RaRaRa的取值可以是222或者是888。 “你怎 ...

A. Add Odd or Subtract Even You are given two positive integers a and b. In one move, you can change a in the following way: Choose any positive odd integer x (x>0) and replace a with a+x; choose any positive even integer y (y>0) and replace a with a−y. You can perform as many such operations as you want. You can choose the same numbers x and y in different moves. Your task is to find the minimum number of moves required to obtain b from a. It is guaranteed that you can always obtain b ...

A-操作序列 题目描述 给出一个长度无限的数列，初始全部为零，有三种操作： 增加操作：给下标为 ttt 的数加 ccc 。特别注意，如果在下标 [t−30,t+30][t-30,t+30][t−30,t+30] 内有不为零的数，增加操作无效。 削减操作：让数列中下标最小的不为零数变为零。 查询操作：查询数列中下标为 ttt 的数字是多少。 输入描述 第一行包含一个整数 N,1≤N≤106N,1 \le N \le 10^6N,1≤N≤106，表示操作总数。 随后 N 行，每行由两个数字或一个数字组成。 若一行中有两个数字，分别代表增加操作的$ t,c$ 。 若一行中只有数字−1-1−1，执行削减操作。 若一行中只有一个不为 −1-1−1的数字，则代表查询操作的数字 ttt。 保证t，ct，ct，c均为非负整数且在整形范围内。 输出描述 削减操作时，先输出该数字，再变为零。 若序列元素全为零，则削减操作无效，此时输出 “skipped”。 查询时，输出该位置上的数。 示例1 输入 7 140 1 120 2 100 3 120 100 −1-1−1 100 输出 0 3 3 0 ...