标签:数学

题意略题解$\because a,b\geq 0 \ , \ \therefore y\geq x$ ,不妨设 $y=x+k(k\geq 0)$ ,原式化为:$$k^2+2kx=ax+b\tag{1}$$当 $a=2k,b=k^2$ ,即 $a^2=4b$ 时有无数组解,输出 inf 。否则 $(1)$ 式可以化为:$$(a-2k)x=k^2-b$$$$x=\dfrac{k^2-b}{a-2...
题解 数学
尚无评定
题意一个圆的方程为 $x^2+y^2=r^2$ ,给出 $r$ ,问圆上有多少个点的坐标都是整数。题解可以用勾股定理的通解:$$x=d\dfrac{v^2-u^2}{2} \ , \ y=duv \ , \ r=d\dfrac{v^2+u^2}2$$枚举 $d$ ,就可以得到 $u^2+v^2$ ,再枚举 $u$ 就可以统计答案了。不过这样算出来的是第一象限内的解,所以最后答案要 $\tim...
题解 数学
省选/NOI-
题意对 $\forall i\in [1,n]$ ,求下式对 $123456789$ 取模的值$$\sum_{j=1}^n a_{\lfloor \frac{i}{j} \rfloor}\times b_{i \ \mathrm{mod} \ j}$$$n\le 10^5 \ , \ a_i,b_i\le 10^9$题解A了这题再随便打了下T3的暴力就rk18了。中途还突然把时限放宽到 $2...
题解 数学 算法-分块
题意求$$\sum_{i=1}^n k \ \mathrm{mod} \ i$$$n,k\le 10^9$题解经典的数值分块问题。原式可以化为:$$n\times k - \sum_{i=1}^n i\times \lfloor \dfrac{k}{i} \rfloor$$问题就转化为求 $\sum_{i=1}^n i\times \lfloor \dfrac{k}{i} \rfloor$可...
题解 数学 算法-分块
提高+/省选-
题意给出 $N,A,B$ ,求 $N_0$ 的最值,使得 $\lfloor N^A+N^B \rfloor = \lfloor {N_0}^A+{N_0}^B \rfloor$ 。有 $T$ 组数据,答案为每组数据中 $\max N_0 - \min N_0$ 的和。输入方式请看原题。$4\le N\le 5 \ , \ 5\le A,B\le 10 \ , \ T\le 5\times 1...
题解 数学
提高+/省选-
题意求不包含子串 $A$ 的长度为 $N$ 的数字 $X$ 的个数。答案对 $K$ 取模。其中 $A$ 的长度 $M\le 20$,$N\le 10^9$,$K\le 1000$ 。题解矩阵乘法优化dp。用 $\text{f[i][j]}$ 表示在 $X$ 中做到第 $i$ 位,匹配到 $A$ 中第 $j$ 位的方案个数。最终的答案即为:$$\sum_{i=0}^{M-1} \text{f[...
题解 字符串 数学 数学-矩阵 字符串-kmp
省选/NOI-
题意解同余方程组:$$x\times ATK_i\equiv A_i\pmod {P_i}\tag{1}$$$ATK$ 还需要平衡树或者multiset推出来。其中方程个数 $N\le 10^{5}$ ,$A_i\le 10^{12}$ 。题解将原式化简:$$ATK_i\times x+P_i\times y=A_i$$可以用 $\text{exgcd}$ 求出 $x$ 的最小整数解 $S_...
题解 数学 数学-扩展中国剩余定理
省选/NOI-
LOJ最优解达成!题意求满足下列要求的长度为 $2n$ 的序列 $S$ 的个数,对 $p$ 取模:是 $2n$ 的全排列奇数项、偶数项分别递增$\forall i\in [1,n] \ , \ S_{2i-1} < S_{2i}$题解对于性质 $2$ ,可以考虑将 $1...2n$ 的数字按照从小到大的顺序依次放入序列。每个数字可以放在最前的奇数或偶数位。分析性质 $3$ ,显然偶数位...
题解 数学 数学-扩展卢卡斯定理 数学-卡特兰数
省选/NOI-
概述卢卡斯定理主要用于求解组合数取模问题。公式原命题见: https://zh.wikipedia.org/wiki/%E5%8D%A2%E5%8D%A1%E6%96%AF%E5%AE%9A%E7%90%86原命题等价于:$$\binom{m}{n}=\binom{\lfloor \dfrac{m}{p}\rfloor}{\lfloor \dfrac{n}{p}\rfloor}\times ...
题意把 $n$ 个不同的礼物分给 $m$ 个人,每个人 $w_i$ 个,求方案数 $\mod p$ 的值。其中 $n,p\le 10^{9}$ ,$m\le 5$ 。题解答案显然为:$$\prod _{i=1}^m C(n-\sum_{i=1}^m w_i,w_i)\mod p$$因为 $p$ 不一定是质数,所以直接上 $\text{exLucas}$ 就行了。#include<bit...
题解 数学 数学-扩展卢卡斯定理
NOI/NOI+/CTSC
反向最优解 $rk3$ 达成。题意求$$\sum_{i=0}^k C_n^i\mod 2333$$其中 $t\le 10^{5} \ , \ n,k\le 10^{18}$题解令 $ha=2333$ ,先用 $\text{Lucas}$ 定理化简$$\sum_{i=0}^k C_{n\div ha}^{i\div ha}\times C_{n\ mod \ ha}^{i\ mod \ ha}...
题解 数学 数学-组合数 数学-卢卡斯定理
省选/NOI-
题意求长度在 $1\sim N$ 之间,由 $[L,R]$ 之间的数构成的单调不降序列的个数。$N,L,R\le 10^{9}$ 。多组数据,组数 $t\le 100$ 。题解令 $M=R-L+1$ ,即可以使用的数的个数。先考虑固定长度为 $n$ 的情况。因为是单调不降,所以数字可以重复使用,而只要选出一部分数就能构成一个且仅有一个满足要求的序列。答案就等价于从 $M+n$ 个数中选出 $...
题意求由 $N\times M$ 的网络上三点构成的三角形个数。$N,M\le 1000$ 。题解图片来源于 https://www.luogu.org/blog/suwakow/solution-p3166每个三角形都可以确定一个最小的包含它的矩形,称这种情况为完全覆盖。那么可以把原矩形化为多个子矩形并只计算完全覆盖的情况。显然对于每个长宽相同的子矩形,它们对答案的贡献都是相同的,所以只用...
题解 数学
省选/NOI-
题意定义$$P=\sum_{i-1}^n i|n\ C_n^i$$求$$G^P\mod 999911659$$其中 $N,P\le 10^{9}$ 。题解由拓展欧拉定理得$$G^P\equiv G^{P\mod \varphi(999911659)} \pmod {999911659}$$因为 $999911659$ 是质数,所以$$\varphi(999911659)=999911658$...
题意求一个位数 $\geq 2$ 的 $2^{k}$ 进制数 $r$ ,满足:化为二进制后位数 $\le w$每一位上的数依次递增其中 $k\le 9 \ , \ k\le w\le 30000$ ,保证 $r$ 化为 $10$ 进制的位数 $\le 200$ 。题解对于条件 $1$ ,显然 $r$ 的位数 $L \le \lceil \dfrac{w}{k}\rceil $ 。当 $L\l...
题解 算法-高精度 数学 数学-组合数
提高+/省选-
标签
其它-Firefox1 其它-pbds1 其它-pjax1 其它-Ubuntu1 其它-VSCode1 其它-网易云音乐1 动态规划50 动态规划-区间DP9 动态规划-单调队列优化DP5 动态规划-图上DP1 动态规划-斜率优化DP5 动态规划-树形DP14 动态规划-状压DP16 动态规划-线性DP10 动态规划-背包DP2 图论4 图论-LCA4 图论-Tarjan9 图论-二分图1 图论-割点3 图论-基环树1 图论-差分约束3 图论-强连通分量1 图论-最小环1 图论-最小生成树6 图论-最短/最长路17 图论-树上差分2 图论-树的直径4 图论-桥1 图论-缩点4 图论-负环3 字符串3 字符串-kmp2 思维题3 数学26 数学-bsgs2 数学-exgcd4 数学-gcd2 数学-中国剩余定理2 数学-卡特兰数1 数学-卢卡斯定理4 数学-快速幂4 数学-扩展中国剩余定理1 数学-扩展卢卡斯定理3 数学-矩阵5 数学-约数1 数学-组合数3 数学-质数1 数据结构-动态开点线段树1 数据结构-单调栈1 数据结构-单调队列2 数据结构-可持久化字典树2 数据结构-堆4 数据结构-字典树2 数据结构-并查集1 数据结构-栈1 数据结构-树状数组3 数据结构-树链剖分10 数据结构-线段树3 数据结构-队列1 比赛-Codeforces19 比赛-JX Round1 比赛-NOIp/CSP4 算法-KM算法1 算法-二分/三分11 算法-位运算1 算法-倍增4 算法-分块2 算法-分治3 算法-哈希2 算法-多叉树转二叉树2 算法-差分4 算法-悬线法1 算法-拓扑排序1 算法-排序3 算法-搜索20 算法-模拟5 算法-状态压缩4 算法-贪心8 算法-高精度3 问题-逆序对2 题目-一本通5 题目-网络流24题2