传送门 现场没推出来，找了个规律，发现是 (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⁡(k,n−1)+n−1lcm(i−k+1,n)k+1=∑i=1nlcm(i,n)k+1=1k+1∑i=1ningcd⁡(i,n)=1k+1⋅n⋅∑g∣n1g∑i=1n[gcd⁡(i,n)=g]i=nk+1⋅∑g∣n∑i=1ng[gcd⁡(i,ng)=1]i\begin{aligned} &...

出题人的题解实在是无法令人恭维，特此写一份自己的题解 【大意】 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 的矩形顶点摆放在整点后；所有不同摆放方案中，每个方案完全包含的 1×11\times 11×1 格子数量的和是多少？ 我们认为两个方案不同，当且仅当一个方案的矩形无法仅通过平移变换，得到另一个方案。 【分析】 我们将矩形 ABCDABCDABCD 的一个顶点放置在原点上，设 AB=n,AD=mAB=n, AD=mAB=n,AD=m ，则 BBB ...

【大意】 给定 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−1m−1​) ；故表达式是一个不超过 444 次的表达式，因此答案可以由拉格朗日插值法表达 考虑令 lk(x)=∏i≠kx−ki−k\displaystyle l_k(x)=\prod_{i\neq k}{x-k\over i-k}lk​(x)=i​=k∏​i−kx−k​ ，则 F(x)=∑i=0...

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

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

传送门 问题等价于从 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⋅a1​,⋯,259⋅a1​,20⋅a2​,⋯,259⋅an​ 共 60n60n60n 个物品中，扣除所有 2ci⋅abi2^{c_i}\cdot a_{b_i}2ci​⋅abi​​ 的 kkk 个物品后，查询体积不超过 mmm 的背包方案数 注意到每个 aia_iai​ 前面乘的系数都是 222 的整...

将 矩阵上下左右各拓宽 个单位。 统计每一个 字符周围的 是否为三个。 最后 字码不存在这样的 字符 字码存在一个 字码存在两个 #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pii; typedef double db; #define fi first #define se second int m[8][8]; inline int around(int x, int y){ return m[x-1][y]+m...

G题题面 本人的理解： 对于苏醒灵魂的点 ，其能在天亮时停留在点 处，当且仅当在三个次元空间，都存在从点 到点 的路径。 因此对于某个苏醒的点，其在天亮时醒来的方案数，等价于其在天亮时能停留的点数，等价于三个次元空间都连通的点数。 故本人考虑使用并查集，先对于输入的边，分别对三个次元空间使用并查集合并线段两端点；而后扫一遍所有线段的两端点，考虑是否该两端点在三个次元空间都分别同属于一个并查集；若满足分别同属于一个并查集，则用另一个并查集合并两点。 最后求出每个点所在的（最后那一个）并查集大小。 请问有什么问题吗？