DoIdo

原创 目录

模板——板子篇模板——OJ题版模板——默写篇题解——板子篇题解——刷题篇

原创 VS2022+QT5环境搭建

目录软件下载VisualStudio2022QT5.14.2软件下载VisualStudio2022VisualStudio2022下载链接打开链接，如下图点击。SetUp程序安装成功后，点击打开。按照如下图下载所需要的模块。QT5.14.2

原创 H . 真签到题

题目链接题目描述Fibonacci 数列，f(n)=f(n−1)+f(n−2)前n项为1 1 2 3 5 8 …给出n,m，需要你计算出满足条件的对数（i，j）的个数，且i<=j。条件是：1<=gcd(f(i)，f(j))<=ni,j<=m由于答案可能很大，所以对1e9+7取模输入描述:第一行为一个整数T，表示T组测试数据。接下来共T行，每行为两个整数n,m。1<=T<=1e51<=n<=1e181<=m<=1e

原创 前端考试习题

随堂测验1. 简述Web的工作原理正确答案：1.用户通过客户端浏览器访问Internet上网站或者其他网络资源时，通过在浏览器输入网站或者网页的（统一资源定位符）网址，或者通过超链接方式链接到另外的网页或者资源；2.通过域名服务器进行全球域名解析，并根据解析结果访问指定IP的网站或网页；3.获取网站IP地址后，客户端浏览器向指定IP地址的Web服务器发送一个HTTP（hypertext transfer protocol, 超文本传输协议）请求；4.Web服务器响应客户端请求，将用户所需的HT

原创 题解模板

题目链接题目描述输入描述:输出描述:示例1输入输出示例2输入输出说明解决思路：总结结论：已知条件：思路里程：实现过程：代码

原创 牛客 · 奇♂妙拆分

奇♂妙拆分题目描述在遥远的米♂奇♂妙♂妙♂屋里住着一群自然数，他们没事就喜欢拆♂开自己来探♂究。现在他们想知道自己最多能被拆分成多少个不同的自然数，使得这些自然数相乘的值等于被拆分的数。输入描述:第111行输入一个整数TTT，代表有TTT组数据。第2−T+12-T+12−T+1行，每行输入一个整数n，代表需要被拆分的数。数据保证：0<T≤100，0<n≤1090<T≤100，0<n≤10^90<T≤100，0<n≤109。输出描述:输出一共TT

原创 中国剩余定理 · Java版

package com.company;public class Main { public static long exgcd(long a, long b, long[] u) { if (b == 0) { u[0] = 1; u[1] = 0; return a; } long g = exgcd(b, a % b, u); long t = u[0];

原创 数据结构模板

链接

原创 牛客——子序列（组合数学）

子序列题目描述给定一个小写字母字符串TTT求有多少长度为mmm的小写字母字符串SSS满足，TTT是SSS的一个子序列(不需要连续)输入描述:第一行一个字符串TTT第二行一个正整数mmm输出描述:输出答案对109+710^9+7109+7取模的值示例1输入aaa2输出51说明长度为2的里面有aaa的串有51种备注:1<=∣T∣,m<=1051<=|T|,m<=10^51<=∣T∣,m<=105解决思路：

原创 欢欢的签到题（数论）

欢欢的签到题题目描述欢欢会给你一个素数ppp，由于欢欢的数论非常菜，所以他想请你帮他计算一下aaa在模ppp下的逆元。输入描述:输入aaa和ppp，用空格隔开输出描述:输出逆元样例1输入3 5输出2提示:1≤a≤p≤1e181≤a≤p≤1e181≤a≤p≤1e18解决思路：提示：数据范围出锅，ppp其实是小于2312^{31}231的，虽然101810^{18}1018也可以做（用龟速乘处理一下会溢出的乘法就行，或者用万能的__int128）。已知

原创 牛客——数字权重（组合数学）

数字权重题目描述小a有一个n位的数字，但是它忘了各个位上的数是什么，现在请你来确定各个位上的数字，满足以下条件：设第iii位的数为aia_iai​，其中a1a_1a1​为最高位，ana_nan​为最低位，KKK为给定的数字1.不含前导02.(∑i=2n(ai−ai−1))=K( \sum_{i = 2}^n (a_i- a_{i - 1})) = K(∑i=2n​(ai​−ai−1​))=K请你求出满足条件的方案数输入描述:两个整数NNN，KKK若存在无解的情况，请输出0输出描

原创 牛客——华华给月月出题（快速幂，欧拉筛）

华华给月月出题题目描述华华刚刚帮月月完成了作业。为了展示自己的学习水平之高超，华华还给月月出了一道类似的题：Ans=⊕i=1N(iNmod  (109+7))Ans=\oplus_{i=1}^N(i^N\mod(10^9+7))Ans=⊕i=1N​(iNmod(109+7))⊕\oplus⊕符号表示异或和，详见样例解释。虽然月月写了个程序暴力的算出了答案，但是为了确保自己的答案没有错，希望你写个程序帮她验证一下。输入描述:输入一个正整数NNN。输出描述:输出答案AnsAnsAn

原创 牛客——Diff-prime Pairs（数论，组合数学）

Diff-prime Pairs题目描述Eddy has solved lots of problem involving calculating the number of coprime pairs within some range. This problem can be solved with inclusion-exclusion method. Eddy has implemented it lots of times. Someday, when he encounters anot

原创 牛客——小w的禁忌与小G的长诗（容斥原理）

小w的禁忌与小G的长诗题目描述自从上次小w被奶牛踹了之后，就一直对此耿耿于怀。于是"cow"成为了小w的禁忌，而长得和"cow"很像的"owc"…凡是同时含有"c",“w”,"o"的都进入了他的禁忌名单。小G想给他送一幅幅长为n个字符的长诗，但是又怕触犯他的禁忌。所以他决定要是诗中出现了他的禁忌就宁可不送，可是…他一写起诗来就忘了一切。小G想知道他有多少种的诗可能不触犯他的禁忌注：小G只会用小写字母写诗输入描述:一行一个整数n表示诗的长度输出描述:一行一个整数表示小G有多少种

原创 赛后题解——真假亚瑟王（数论）

注释：多组测试数据卡超时不多的话可以试试这题能否用数组记录，这样有的数据就可以O(1)\small O(1)O(1)时间算出C. 真假亚瑟王题目描述魔术师梅林在水晶球中预见了莫德雷德的叛逆，她决定在在莫德雷德叛逆之前采取一个有效的策略保护亚瑟王。具体做法如下：使用魔法将亚瑟王复制成N份，当然，其中只有一个使真的。她认为这样就能有效的保护亚瑟王不被杀死。为了自己能最终找到亚瑟王，她将所有的亚瑟王按1-N编号，并设定了一个密码数字X。真亚瑟王的编号是最接近N的且不能被2−X中任何一个数整除的数。（即

原创 manim学习之路

打印Hello World！# import packagefrom manimlib.imports import *class Hello_World(Scene): def construct(self): # making object # word color : red helloworld = TexMobject("Hello World！", color=RED) # showing object

原创 算法学习指南

算法学习笔记（目录）平台：知乎作者：Pecco

原创 开心的涂鸦（容斥）

链接：https://ac.nowcoder.com/acm/problem/14718来源：牛客网题目描述有m种颜色和n个格子，需要计算两个相邻格子相同颜色的方案数题解首先发现直接求的话不好算，所以考虑容斥总的方案数：mnm^nmn考虑第一个位置有mmm种放法，第二个位置为了保持相邻格子颜色不同，只有m−1m-1m−1种放法，以此类推第nnn个位置也只有m−1m-1m−1种放法任意相邻的格子颜色不同的方案数：m×(m−1)(n−1)m\times(m-1)^{(n-1)}m×(m−1)(n

原创 子序列（组合数学）

链接：https://www.nowcoder.com/acm/contest/181/F来源：牛客网题目描述#include<iostream>#include<algorithm>using namespace std;#define mod 1000000007typedef long long ll;const int N = 1e3 + 10;ll u[N];ll c[N][N];ll qpow(ll a, ll b, ll p) { ll

原创 辗转相除法证明

原创 模板——单调栈

#include<iostream>using namespace std;typedef long long ll;const int N = 1e6 + 10;int n;int st[N], tt;int main() { cin >> n; for (int i = 1; i <= n; i++) { int x; cin >> x; //为了保证栈顶元素小于输入的值，只需要写程序时将<取反为>=就行 wh

原创 数论证明——No.1

原创 模板——exLucas（大组合数取模）

```cpp#include<iostream>#include<algorithm>using namespace std;typedef long long ll;const int N = 20;ll B[N], u[N];inline ll qmul(ll a, ll b, ll p) { ll res = 0; a %= p; b %= p; while (b) { if (b & 1LL) { res = (res + a) %

原创 赛后题解——问题 C: A^X mod P

问题 C: A^X mod P题目描述It’s easy for ACMer to calculate A^X mod P. Now given seven integers n, A, K, a, b, m, P, and a function f(x) which defined as following.f(x) = K, x = 1f(x) = (a*f(x-1) + b)%m , x > 1Now, Your task is to calculate( A^(f(1)) + A

原创 模板——高斯消元

#include<cmath>#include<stdio.h>#include<iostream>#include<algorithm>using namespace std;const int N = 110;const double eps = 1e-6;int n;double u[N][N];int gauss() { int x, y; for (y = 1, x = 1; y <= n; y++) { int

原创 算法——数位dp

注释：数位dp解决的问题：求出给定区间[L,R]\small [L,R][L,R]，符合条件f(x)\small f(x)f(x)的xxx的数量。例：条件：不降数——这种数字必须满足从左到右各位数字成小于等于的关系。如 123\small 123123，446\small446446L\small LL：1\small 11R\small RR：19\small 1919答案：18\small 1818解释：只有10\small 1010不是不降数，其余的数都是不降数，故答案为18\sma..

原创 算法——判断二分图

注释：算法核心：若一个图是二分图，则它的充要条件是所有回路都是偶数，即每个回路可以用两种颜色染色，即该图可以用两种颜色染色，可以直接用dfs\small dfsdfs染色判断是否可以用两种颜色染色。演示图解：代码...

原创 模板——exCRT

#include<iostream>using namespace std;typedef long long ll;const int N = 1e6 + 10;int n;ll b[N], p[N];ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b); }ll exgcd(ll a, ll b, ll& x, ll& y) { if (b == 0) { x = 1, y = 0; return

原创 题解——板子篇

题面题意：AC代码

原创 板书——数论篇

第一章——整数的唯一分解定理

原创 集合中的质数（容斥原理和dfs）

注释：当然这道题也可以二进制枚举，只是不用0\small 00这个二进制。题面题意：见题面。解决思路：容斥原理：总结：容斥原理就是奇加偶减。有了公式就直接dfs\small dfsdfs求解就可。为了方便dfs\small dfsdfs，先将输入的数组排序，这样就可以实现神剪枝操作。从左往右遍历每个数，对于这个数来说，可以被取，也可以不取。不取：除了遍历的位置加一，其余不变。取：遍历的位置加一，由容斥原理的奇加偶减的性质可以得到，多取一个数，它肯定变号，所以opt\small op..

原创 模板——CRT（中国剩余定理）

讲解#include<iostream>using namespace std;typedef long long ll;const int maxn = 100;int n;//b[i]为余数 p[i]为模数ll b[maxn], p[maxn];//扩欧模板ll exgcd(ll a, ll b, ll& x, ll& y) { if (b == 0) { x = 1, y = 0; return a; } ll g = exgcd.

原创 读入输出挂

//读入挂inline ll read() { ll c = getchar(), Nig = 1, x = 0; while (!isdigit(c) && c != '-')c = getchar(); if (c == '-')Nig = -1, c = getchar(); while (isdigit(c))x = ((x << 1) + (x << 3)) + (c ^ '0'), c = getchar(); return Nig * x;

原创 赛后题解——问题 D: 游戏jienzi（记忆化）

//优化#pragma GCC optimize(2)//C#include<string.h>#include<stdio.h>#include<stdlib.h>#include<math.h>//C++#include<unordered_map>#include<algorithm>#include<iostream>#include<istream>#include<iom

原创 模板——特殊数列的前缀最小公倍数

形如：{ f(0)=0 f(1)=1 f(n)=af(n−2)+bf(n−1)            (a,b)=1\small \begin{cases}\ f(0)=0\\\ f(1)=1\\\ f(n)=af(n-2)+bf(n-1)~~~~~~~~~~~~(a,b)=1\\\end{cases}⎩⎨⎧​ f(0)=0 f(1

原创 小a的旅行计划（组合数学与逆元）

注释：题面题意：见题面。解决思路：由题意不难看出集合A,B\small A,BA,B的个数都不能为1\small 11(1\small (1(1的时候肯定相互包含)\small ))AC代码//优化#pragma GCC optimize(2)//C#include<string.h>#include<stdio.h>#include<stdlib.h>#include<math.h>//C++#include<unord..

原创 Utawarerumono（裴蜀定理）

注释：题面题意：见题面。解决思路：首先判断ax+by=c\small ax+by=cax+by=c是否有解，由裴蜀定理可知，(a,b)∣c\small (a,b)\mid c(a,b)∣c时有解。此时计算p2x2+p1x+q2y2+q1y\small p_2x^2+p_1x+q_2y^2+q_1yp2​x2+p1​x+q2​y2+q1​y最小值，发现有两个未知数，不好判断，所以将ax+by=c\small ax+by=cax+by=c转换为y=c−axb\small y=\large \frac..

原创 序列求和（gcd与逆元）

注释：Cii+Ci+1i+...+Cni=Cn+1i+1\small C_i^i+C_{i+1}^i+...+C_n^i=C_{n+1}^{i+1}Cii​+Ci+1i​+...+Cni​=Cn+1i+1​题面题意：见题面。解决思路：结论：12+22+32+...+n2=n(n+1)(2n+1)6\small 1^2+2^2+3^2+...+n^2=\frac{n(n+1)(2n+1)}{6}12+22+32+...+n2=6n(n+1)(2n+1)​证明∵i2=i2+i−i=i(i−1)+i..

原创 模板——OJ题版

文章目录数论排序高精度字符串数据结构组合数学复数数论gcdBSGSexgcdexBSGS整除分块线性筛欧拉函数线性筛莫比乌斯函数排序堆排序归并排序快速排序高精度高精度加法高精度减法高精度乘法字符串KMP搜索ManacherKMP（Next数组的初始化（版本一））KMP（Next数组的初始化（版本二））数据结构ST表之最大值问题一维树状数组之求和（区间修改，区间查询）二维树状数组之求和（区间修改，区间查询）线段树之最大值问题（单点修改，区间

原创 模板——exgcd

#include<iostream>using namespace std;typedef long long ll;ll exgcd(ll a, ll b, ll& x, ll& y) { if (b == 0) { x = 1, y = 0; return a; } ll g = exgcd(b, a % b, y, x); y -= a / b * x; //返回值是最大公约数 return g;}int main() { ll a,