nagisa-kun-CSDN博客

原创上海理工大学第二届“联想杯”全国程序设计邀请赛 B-heith i ngra le 解题报告(组合数学)

题目大意：在一个mxn网格上，填充格子为黑色构成山形，定义每一列最高的黑色格子的高度为该列的高度h，需要满足以下要求：有一对l,r，满足1<=l<=r<=n在1<=i<=l范围内，hih_ihi不下降l<=i<=r范围内，hih_ihi保持不变在r<=i<=n内，hih_ihi不上升求填充格子的方案数。思路好似可以dp，但我理不清转移Orz。考虑从整体进行组合计算。考虑枚举l,r。若我们只是把l和r当作题目中的l和r，那么，不下降

2021-06-13 21:04:55 224

原创 Codeforces Round #548 (Div. 2) 1139 D+2021天梯赛l3-3 解题报告（负二项式分布+莫比乌斯容斥+杜教筛（天梯赛））

以下是我这道题的思考过程：（1）、若选到1，那直接就能结束了。（2）、若选到其他的数，则我们需要继续选下去，直到选到一个和前面的一个数互质的数。想到互质，可以想到和质数相关。思考极限情况，我们可以想象这一过程：不停地选数，在这个过程在，我们保持选到的数的都是某一个数x的倍数，直到选到一个数不为x的倍数就结束。这一过程其实就是概率论中的负二项式分布:实验包含一系列独立的实验。每个实验都有成功、失败两种结果。成功的概率p是恒定的。实验持续到r次失败，r可以为任意正数。则X~NB(r,p

2021-04-30 20:10:24 263

原创【补题】2020 CCPC 秦皇岛 I. Interstellar Hunter（exgcd，向量线性组合的等价转换）

题目链接：http://codeforces.com/gym/102769/problem/I一开始想到贝祖定理，但是只能分别判断x和y方向上的，没办法组合起来判断。思路分析这道题考的其实主要不是贝祖定理，而是exgcd。假设我现在我们有向量(a1,b1)，(a2,b2)(a_1,b_1)，(a_2,b_2)(a1,b1)，(a2,b2)。考虑x方向上，若某横坐标c可以到达，则表示存在x，y，使得a1x+a2y=ca_1x+a_2y=ca1x+a2y=c。由exgcd可知：该方程解的情

2021-04-03 12:16:19 596

原创 AtCoder Regular Contest 116（A思维B贡献统计C组合数学（a[i]为a[i-1]的倍数的序列数））

每次做arc都感觉虽然很难但很有意思A.Odd vs Even第一个想法是包含2的次数有关。很容易想到，若这个数是奇数，那它一定没有偶数因子。再通过打表后我们可以发现：若2的次数只有1次，那么，奇数因子数=偶数因子数。若2的次数更大，那偶数因子数>奇数因子数。signed main(){ #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif //clock_t c

2021-03-29 23:09:32 284

原创 P6046 纯粹容器解题报告（组合数学）

有一些思维难度的组合数学。题目链接：https://www.luogu.com.cn/problem/P6046我们可以把这道题想象成这样一个模型：一根绳子，上面有n个点，每次操作，可以把任意两个相邻的点，也就是一段间隔合并掉。考虑什么时候第i个容器会消失：也就是遇到一个比自己强的容器的时候。那么，显然考虑被左边或右边第一个比它大的容器打败（不一定是这个容器，因为这个容器可能在此之前就被更强大的容器打败。但是，由不等式的传递性，这个新上位的容器也能打败i）。记左边第一个比i强的位置为lil_ili,

2021-03-10 01:46:01 566

原创 P2634 [国家集训队]聪聪可可（树形dp）

这道题主要是要学习下这个树形dp的写法。我一开始的想法是全部转移完再来统计贡献。然而，这就造成一个麻烦。我们要统计的贡献是树中是权值和为3的倍数的路径个数。如果按照暴力思想，肯定是枚举两个点之后check这两点之间的距离是不是3的倍数。然而，2e4的数据量不允许我们这样做。因此，考虑到这道题是树上问题，再联想到树上求距离还有一个重要的对象就是lca。所以，我们的状态设计其实就是：dp[u][i]表示到点u的距离模3为i的点的个数，相当于枚举了lca。那么，考虑统计贡献：显然，贡献来自dp[u][0]

2021-03-09 00:40:07 111

原创拉格朗日插值法学习小结

基本定理我们中学就知道：两点确定一直线。对于这一点的拓展：n点可以确定n-1阶的多项式。关于证明，可以联想待定系数法：设多项式为f(x)=a0+a1xn+x2x2+……+an1xn−1f(x)=a_0+a_1x^n+x_2x^2+……+a_{n_1}x^{n-1}f(x)=a0+a1xn+x2x2+……+an1xn−1由此可知，我们只需要n个独立方程就能确定此多项式。那么，假设说我们要求这个多项式的某点的取值f(k)f(k)f(k)，最直接的想法是确定待定系数，再来求f(k)f(k)f(

2021-03-02 14:24:31 1349

原创 51nod 1742 开心的小Q 解题报告（莫比乌斯函数+线性筛+数论分块）

链接：http://www.51nod.com/Challenge/Problem.html#problemId=1742要点：1、这里的枚举变换和平时的不大一样？2、莫比乌斯函数和容斥根据莫比乌斯函数定义，我们得到要求的答案为：ans=∑i=1n∑d∣i(1−∣μ(d)∣)ans=\sum_{i=1}^{n}\sum_{d|i}(1-|\mu(d)|)ans=i=1∑nd∣i∑(1−∣μ(d)∣)这里我们这里我们令t=i/d，则：变换为：ans=∑t=1n∑d=1nt(1−∣μ(d)

2021-02-21 18:14:31 101

原创 ACM-五边形数定理 and 整数划分问题知识点总结

不是什么太重要或者常考的点，但是既然学了就记录下吧五边形数顾名思义，就是能组成五边形的数所组成的序列，具体看图。序列中的第n个数为f(n)=n(3∗n−1)2f(n)={n(3*n-1)\over 2}f(n)=2n(3∗n−1)转自维基百科广义五边形数就是将五边形数扩展到负数范围内。n01-12–2-3–3f(n)012571215五边形数定理下面是我们的正菜：五边形数定理我们定义欧拉函数（这个欧拉函数和数论里的应该没有关系？）：

2021-02-02 02:19:11 395

原创 P4111 [HEOI2015]小 Z 的房间解题报告（矩阵树定理+高斯消元求行列式）

关于矩阵树定理，不关心证明的话，可以直接看这个结论：https://www.cnblogs.com/yangsongyi/p/10697176.html这题的意图其实很明显，就是给一个图，问你有几个生成树。需要注意的是，柱子的点不能放进图内，不然就没有生成树了。注意建图。另外，对于这种整数的、用不了逆元的高斯消元，我们可以才用辗转相除的方法，复杂度多一个log，具体实现看代码。#include <bits/stdc++.h>using namespace std;typedef lon

2021-01-22 01:56:01 143

原创 AtCoder Regular Contest 111补题报告（A数学 B思维（匹配问题） C思维（贪心）D思维（保证有解时猜测）E数学（类欧几里得算法））

目录A - Simple Math 2B - Reversible CardsC - Too HeavyA - Simple Math 2推式子：⌊10NM⌋modM=⌊10NM⌋−kM=⌊10N−kM2M⌋⌊{10^N\over M}⌋modM=⌊{10^N\over M}⌋-kM=⌊{10^N-kM^2\over M}⌋⌊M10N⌋modM=⌊M10N⌋−kM=⌊M10N−kM2⌋所以，我们快速幂取模求10nmod m210^n \mod m^210nmodm2后再整除M即可。ll k

2021-01-13 21:47:58 230

原创 P3768 简单的数学题解题报告（莫比乌斯反演+杜教筛）

题目描述题面简单，我打下：∑i=1n∑j=1nijgcd⁡(i,j)mod p\sum_{i=1}^{n}\sum_{j=1}^{n}ij\gcd(i,j)\mod{p}i=1∑nj=1∑nijgcd(i,j)modpn最大1e10，p为质数思路分析拿到这种题，肯定是先推式子，暴力跑不过去的。 ∑i=1n∑j=1nijgcd⁡(i,j)mod p\sum_{i=1}^{n}\sum_{j=1}^{n}ij\gcd(i,j)\mod{p}∑i=1

2020-12-30 14:51:39 129

原创 kuangbin数学2 解题报告

这部分组合数学挺多的，记录下。LightOJ - 1005 Rooks多组样例：n*n的放个，要放k个棋子，棋子之间互不相同，要求不同行不同列，求方案数放一个棋子，相当于挑走一个行和一个列，所以考虑组合数。又由于棋子不互相同，所以乘上排列数AkkA^k_kAkk，就是答案。组合数可以用n^2递推。#include <bits/stdc++.h>using namespace std;#define rep(i,a,b) for(int (i)=(a);(i)<=(b);++i

2020-12-27 22:58:44 165

原创 ARC 107 解题报告 A.数学(多项式相乘的性质)B(枚举、计算贡献)C(思维、并查集)D(DP(非整数转化)E(打表找结论)F(网络流不会))

A - Simple Math题目：求∑a=1A∑b=1B∑c=1C\sum_{a=1}^{A}\sum_{b=1}^{B}\sum_{c=1}^{C}a=1∑Ab=1∑Bc=1∑C的值ll a,b,c;ll inv2;ll solve(){ ll res=((a+1)*a%mod*inv2%mod)%mod; res=((res*(b+1)%mod)*b%mod*inv2%mod)%mod; res=((res*(c+1)%mod)*c%mod*inv2%mod)%mod; re

2020-12-18 20:14:46 131

原创组合数学——卡特兰数知识点总结

定义好像没有找到具体的定义？而关于它的实际意义，我会放到后面模型来讲。前几项为1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452,

2020-11-28 23:45:49 312

原创 Educational Codeforces Round 98 (Rated for Div. 2) 解题报告(A.思维 B.二分 C.栈+思维 D.找规律 E.预处理)

官方题解：https://codeforces.com/blog/entry/84847A - Robot Program要到达终点的最短路径，一定是要么不用West，要么不用North，并且，其指令序列一定为E x E x E x……x E或者S x S x S x……x S交错排成，因此，我们可以得到结论答案为max(x,y)*2,并且当x==y的时候，S(E)与x数量相同，需要+1。t=input()t=int(t)while t>0: t-=1 x,y=input()

2020-11-25 19:01:43 111

原创 P3239 [HNOI2015]亚瑟王解题报告(概率期望dp)

原题链接第一篇题解挺好的思路根据期望的定义：E=∑f(i)∗d(i)E=\sum f(i)*d(i)E=∑f(i)∗d(i)，其中，f(i)为i牌的出牌概率。之后是如何求f(i)：读原题，有个点：当出了一张牌后，结束本轮游戏。那么，假设说，在r轮中，在i之前的i-1张牌中，有j张牌被打出，那么，而也就是说，会有r-j轮是会考虑到第i张牌的，因此，我们可以得到f(i)=∑dp[i−1][j]∗(1−(1−p(i)r−j))f(i)=\sum dp[i-1][j]*(1-(1-p(i)^{r-j})

2020-09-11 01:12:25 130

原创 Codeforces Round #535 (Div. 3) 解题报告(A.B.C.思维 D.dp E1.暴力+差分 E2.线段树 F.克鲁斯卡尔+思维)

A - Two distinct points直接循环就行了，因为根本跑不满n2n^2n2#include <iostream>#include <map>#include <ctime>#include <vector>#include <climits>#include <algorithm>#include <random>#include <cstring>#include <c

2020-09-07 21:45:59 114

原创 Croc Champ 2013 - Round 2 (Div. 2 Edition) 补题报告 A.B.(思维) C.(博弈论) D.(DFS+剪枝) E(待补)

目录A - Ksusha and ArrayB - Ksusha the SquirrelC - Weird GameD - Distinct PathsA - Ksusha and Array要找一个数能够整除数组内其他数，否则输出-1。很明显，要能整除其他数，这个数一定是最小的那一个。若最小的那个数能满足条件，则输出最小的，否则，输出-1。#include <iostream>#include <map>#include <ctime>#include &

2020-07-30 15:05:16 131

原创 CodeForces - 1058D Vasya and Triangle 解题报告

题意给三个数n,m,k,求是否存在0<x1,x2,x2<n,0<y1,y2,y3<m，使得三点(x1,y1),(x2,y2),(x3,y3)构成的三角形面积为n*m/k思路首先，一个三角形它一定有锐角，所以，我们考虑把一个顶点放在原点方便考虑。由条件可知，其实就是在矩形(0<x<=n,0<y<=m0<x<=n,0<y<=m0<x<=n,0<y<=m)内再找两点组成三角形。设另外两点为A(x1,y1),B(x

2020-07-23 01:21:53 107

原创 Codeforces Round #654 (Div. 2) 补题报告(A(思维)B(思维)C(思维，结论猜的)D(贪心)E1(贪心))

A - Magical Sticks题意：给一个数n，现有1、2、……、n这n个数，可以选择任意两个数求和，求最后最多能有几个数相等我们可以想：1+n-1=n,2+n-2=n,……,若n为奇数，则存在(n-1)/2+(n-1)/2+1=n，此时有(n+1)/2个数相等若n为偶数，则会有一个数凑不成n，所以，此时有(n-2)/2+1=n/2个数相等总结起来答案是n/2+(n%2)t=input()t=int(t)while t>0: t-=1 n=input()

2020-07-05 00:08:33 232

原创 [数论专题]容斥原理练习（持续更新）

参考大佬博客：https://www.cnblogs.com/linyujun/p/5210410.html目录HDU - 1465 不容易系列之一UVALive - 7040 ColorHDU - 1465 不容易系列之一这道应该第一反应是排错问题，可以用排错问题的公式。但是，也可以用容斥原理来想。总的方案数为n!。假设一定有1封信（指定的，非任意）放对，则有(n−1)!(n-1)!(n−1)!种方案。假设一定有2封信（指定的，非任意）放对，则有(n−2)!(n-2)!(n−2)!种方案。假

2020-06-20 23:04:17 489

原创 Educational Codeforces Round 89 (Rated for Div. 2) 补题报告A.数学/贪心 B.思维 C.思维 D.唯一分解定理+gcd性质

感冒了没写Orz，只补了一部分。A - Shovels and Swords（数学/好像贪心也行）虽然感觉贪心也行，但是写起来好像不是很容易。。。联想到动态规划应该还是可以的（高中的没忘的话）。设两个物品为A、B,分别制作了x件、y件，则满足不等式2x+y<=a2x+y<=a2x+y<=ax+2∗y<=bx+2*y<=bx+2∗y<=b目标函数z=x+y按照高中老师教的，画个图，带交点就能求出来了。但还要考虑下两条直线再第一象限没交点的情况，那就代端点。#

2020-06-13 15:10:30 347 1

原创 P1757 通天之分组背包解题报告(分组背包板子题)

链接：https://www.luogu.com.cn/problem/P1757分组背包的板子：for k in 所有的组{ for v in 背包容量{//反向，从最大到最小 for i in 所有物品{ if(i这件物品不在现在的分组) continue; 状态转移 } }}之前前面的两个for，可以理解，其实就是一个01背包，只是在两层之后，多了一层，枚举在一定背包容量下，取该组内哪一件物品使得价值最大。所以，其实他就是一个01背包，只是他把一整个组看作了01背包

2020-06-08 23:12:14 168

原创 P4071 排列计数解题报告(错排问题、组合数、逆元打表)

题目链接:https://www.luogu.com.cn/problem/P4071先是组合数部分，比较容易想到从n个中挑出m个对位的，剩下的我们都要让他们不对位。这时候，我们就想到了错排问题。错排问题的定义是：考虑一个有n个元素的排列，若一个排列中的所有元素都不在他们原来的位置上，那么这种情况就称为错排。n个元素的错排个数记为DnD_nDn。研究一个排列错排个数的问题叫作错排问题。关于这个问题，非常推荐一个大佬的博客：https://www.luogu.com.cn/blog/P6174/pos

2020-06-08 18:33:07 201

空空如也

空空如也