JustinRochester

题解

/ 注册

全部文章 / 题解（共8篇）

题解 | #gcds#

传送门 VP 的时候失误推错太多次了，写个博客总结一下由于牛客限定了单份题解的字数上限，本文删去了一些公式的中间推导过程，仅留下了开头与结果。若无法推导出一致结果的，可以参考本人的博客园博客【大意】求所有长度为 mmm 且和为 nnn 的正整数序列 aaa 的贡献和。其中，每个数列的贡献为...

数论莫比乌斯反演组合数学欧拉筛

2022-11-25

1 399

题解 | #NTT#

传送门现场没推出来，找了个规律，发现是 (n+1)n−1(n+1)^{n-1}(n+1)n−1 就直接冲过了【分析】考虑 0≤k<n0\leq k<n0≤k<n ，所以 min⁡(k,n−1)=k\min(k, n-1)=kmin(k,n−1)=k 因此有： ∑i=kmin...

数论莫比乌斯反演第二类斯特林数

2022-10-26

5 328

题解 | #The Pool#

出题人的题解实在是无法令人恭维，特此写一份自己的题解【大意】 TTT 次询问，每次询问给定 n,m(1≤n,m≤1018)n, m(1\leq n,m\leq 10^{18})n,m(1≤n,m≤1018) ，问长宽分别为 n,mn, mn,m 的矩形顶点摆放在整点后；所有不同摆放方案中，每个方...

数学高斯质数皮克定理 Pollard_Rho

2022-08-10

4 430

题解 | #Floor Tiles in a Park#

【大意】给定 W×HW\times HW×H 的矩形，要恰好划分为 kkk 个小矩形的方案数。【分析】考虑极限情况是 k=5k=5k=5 ，此时会有贡献 (n−1k−1)\dbinom {n-1} {k-1}(k−1n−1) 和 (m−1k−1)\dbinom {m-1} {k-1}(k−...

深度优先搜索数学

2022-08-08

6 524

题解 | #I. Three Body#

【大意】给定 KKK 维数组 S,TS,TS,T ，其中每个元素都是不超过 KKK 的正整数。求有多少个位置，使得 TTT 的 T0,0T_{0, 0}T0,0 元素对齐该位置后，整个 TTT 数组的值都不超过 SSS 数组对应位置的值【分析】我们令 gv,x1,x2,⋯ ,xK=[Tx1...

数学 FFT 高维FFT

2022-08-03

0 448

题解 | #Ice Drinking#

传送门【分析】先推一波公式：答案 resresres 显然有公式：（其中 DnD_nDn 表示 nnn 个元素全部错排的方案数） res=1n!∑x=0n(nx)xkDn−x=∑x=0nxkx!⋅Dn−x(n−x)!\begin{aligned}res&={1\over n!}\s...

数学计数组合数学线性递推中国剩余定理

2022-07-26

3 521

题解 | #Fly#

传送门问题等价于从 20⋅a1,21⋅a1,⋯ ,259⋅a1,20⋅a2,⋯ ,259⋅an2^0\cdot a_1, 2^1\cdot a_1, \cdots, 2^{59}\cdot a_1, 2^0\cdot a_2, \cdots, 2^{59}\cdot a_n20⋅a1,21⋅a...

数学动态规划

2022-07-22

2 516

题解 | #科学家的模型#

将矩阵上下左右各拓宽个单位。统计每一个字符周围的是否为三个。最后字码不存在这样的字符字码存在一个字码存在两个 #include<bits/stdc++.h> using namespace std; typedef long long ll; type...

2021-06-26

0 502