此号仅供收藏一些知识点，内网来的朋友别乱删改谢谢

———————————————————————本人1349，管理员您好😄❤️❤️❤️❤️❤️❤️❤️

KMP(过于沈秘i( •̀ ω •́ )y)

模板Ⅰ：

····1:pmt

void get_pmt(string s) 
{
	for(int i=1,j=0;i<s.length();++i) 
	{
		while(j&&s[i]!=s[j]) 
			j=pmt[j-1];
		if(s[i]==s[j]) 
			j++;
		pmt[i]=j;
	}
}

····2:kmp

void kmp(string s,string p) 
{
	for(int i=0,j=0;i<s.length();++i) 
	{
		while(j&&s[i]!=p[j]) 
			j=pmt[j-1];
		if(s[i]==p[j]) 
			j++;
		if(j==p.length()) 
		{
			cout<<i-j+2<<endl; 
			j=pmt[j-1];
		}
	}
}

树状数组

int
int a[N],c[N];
int lowbit(int x)
{
    return x&(-x);
}   
//};

void add(int x,int v)//单点修改
{
    while(x<=n)
    {
        c[x]+=v;
        x+=lowbit(x);
    }
}
int ask1(int x)//区间查询
{
    int t=0;
    while(x)
    {
        t+=c[x];
        x-=lowbit(x);
    }
    return t;
}
//另一方法：化简为繁"ovo"
int ask2(int x)
{
  if(!x)
      return 0;
  return c[x]+ask(x-lowbit(x));
}

沈秘组合数学

沈秘快速幂

int quick(int base,int power)
{
    int res=1;
    base%=mod;
    while(power)
    {
        if(power&1)
            res=res*base%mod;
        base=base*base%mod;
        power>>=1;
    }
    return res%mod;
}

沈秘逆元

Nvoid getni(int N)//int jie[],int ni[])
{
    jie[0]=1;
    for(int i=1;i<=N;i++)
       jie[i]=jie[i-1]*i%mod;
    ni[N]=quick(jie[N],mod-2);
    for(int i=N;i>=1;i--)
       ni[i-1]=ni[i]*i%mod;
}

沈秘组合数

int C(int n,int m)
{
    if(m==0)  return 1;
    if(n<m)   return 0;
    if(n<mod)
        return jie[n]* ni[m] %mod *ni[n-m]%mod;
    return C(n%mod,m%mod)*C(n/mod,m/mod)%mod;
}

数论Ⅱ

—————难

lowbit

int lowbit(ll x)
{
    return x&(-x);
}

popcount

int popcount(ll x)
{
    int sum=0;
    while(x)
    {
        sum++;
        x-=lowbit(x);
    }
    return sum;
}

gcd

ll gcd(ll a,ll b)
{
    return b?gcd(b,a%b):a;
}

qy 快速幂

ll quick(ll a,ll b)
{
    ll t=1;
    while(b)
    {
        if(b&1)  t=t\*a%mod;
        b=b/2;
        a=a\*a%mod;
    }
    return t;
}

phi

ll phi(ll x) 
{
     ll res=x;   
     for(int i=2;i<=x/i;i++)
         if(x%i==0)
         {
             res=res/i\*(i-1);
             while(x%i==0)
                  x=x/i;
         }
         if(x!=1)
             res=res/x\*(x-1);
         return res;
}

lucas定理

int lucas(int a,int b,int i) 
{
   if(a<b)
 		return 0;
   if(a<m[i]&&b<m[i])
 		return lx[i][a]\*inv[i][b]%m[i]\*inv[i][a-b]%m[i];
 	return lucas(a%m[i],b%m[i],i)\*lucas(a/m[i],b/m[i],i)%m[i];
}

沈秘二维差分

——————内含沈秘前缀和(二维)

沈秘区间加

void add(int x1,int x2,int y1,int y2,int c,int Dec[][])
{
    Dec[x1][y1]+=c;
    Dec[x1][y2+1]-=c;
    Dec[x2+1][y1]-=c;
    Dec[x2+1][y2+1]+=c;
}

对沈秘差分数组求沈秘二维前缀和

——————即沈秘二维前缀和

void inone(int Dec[][])
{
for(int i=1;i<=n;i++)
   for(int j=1;j<=m;j++)
      Dec[i][j]+=Dec[i-1][j]+Dec[i][j-1]-Dec[i-1][j-1];
}

输出沈秘修改后沈秘数组

void print(int Dec[][],int a[][],int n,int m)
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            cout<<Dec[i][j]+a[i][j]<<' ';
        cout<<'\n';
    }
}

沈秘深臣爱用的二分答案

——————————————————其实深臣不会

int mid;
while(l+1<r)
{
    mid=(l+r)/2;
    if(check(mid)) 
        r=mid;
    else
        l=mid;
}

沈秘ST表

————————经常遗忘

int f[ ][ ];//自己填;
for(int i=1;i<=n;i++)
    cin>>f[i][0];
for(int j=1;(1<<j)<=n;j++)
    for(int i=1;i<=n;i++)
    {
        f[i][j]=f[i][j-1];
        if(n>=(i+(1<<(j-1))))
            f[i][j]=min(f[i][j],f[i+(1<<(j-1))][j-1];
    }

*前缀和的一些题目👎 *

·1:逆天巨人

—————————(恶心的死:该网站要用O2优化因此这里为不会开O2的朋友提供两种)

无O2:)

思路：

//如果 a,b,c在之前出现过,那么不妨设上次出现为Al,Bl,Cl; //则a-Alb-Blc-Cl //该式==>a-Alb-Bl且b-Blc-Cl(且a-Alc-Cl)(很好理解,左边和 右边) //即<=>a-bAl-Bl①且b-cBl-Cl②(且a-c==Al-Cl③)(嗯。对) //即当a-b与a-c的值再次出现,a、b、c就又出现一次(不好理解) //因此只需要记录a-b与a-c即可(不用记录③:确定①②时,③也确定了) //我们可以用pairint,int来记录a-b,b-c的出现(a-b为第一个,b-c第二个), //作为“map”的第一个关键字(可理解为索引或命名,左边那个) //第二个关键字(右边那个)用来记录值(出现次数) //👇👇👇为代码(ans的记录在里面注释有写)

#include<bits/stdc++.h>//不是<bits\stdc++.h>
#define N 1000010 //定义符号常量N为a,b,c最大值
using namespace std;
map<pair<int,int>,int>x;//定义map
int main()
{
freopen("lintaojuren.in","r",stdin);      防 COPY
freopen("lintaojuren.out","w",stdout);    标签OvO
x[{0,0}]=1;//该情况第一次出现即可计入总数
string s;
cin>>s;
int m=s.size(),n=0,a=0,b=0,c=0;
for(int i=0;i<m;i++)
{                     从花逝爆零人那copy的代码,本人写法:
if(s[i]=='A')          switch(s[i]){
a++;                      case 'A':{
if(s[i]=='B')                 a++,break;}
b++;                      case 'B':{
if(s[i]=='C')                 b++,break;}
c++;                      case 'C':{
int d=a-b,e=a-c;              c++,break}

气死了出bug了

//	if(d<2*N&&e<2*N) //实测没用,因为按数据来说,a-b不可
//	{ 				//能超过2*N,甚至<N,所以完全没必要
		n+=x[{d,e}];//它新增的一个abc...其实就是能作为
		x[{d,e}]++;//右端点与之前的每一个abc..配对成为
//	}			    //一个时间段，因此总方案加上之前出 
	}    		   //现过的次数总和。
	cout<<n; 
	return 0; 
}

好吧骗你的其实第一个是无O2会炸 哈哈ヾ(≧▽≦*)o ψ(｀∇´)ψ

如果真不会O2优化：

//map不行的原因是因为它的调用比较man.....
   //因此可以使用unordered_map这玩意
   //这玩意的调用仅为O(1)的复杂度
   //但是它的调用可能需要调用一个Hash函数(个人见解)
   //关于Hash表，
   //它不是SPFA (´▽`ʃ♡ƪ)
   //但我不会ovo
   //自己查去。。。。
   //因此在编译界面或者递交那里选"C++14(O2)"或"C++17(O2)"即可

阴 :Cantor数(本入的生涯第一道题)

先打个神秘表格：

WAY1:沈秘打表

先呈现一个似乎整个世界就我在用的办法(好吧是这个办法最低级的一种优化形式)

即模拟每一个序号对应的点的表中的值(暂且称之为对应的有理数)吧,最开始从各个细节讨论,

比如(第一个的特殊情况,最后一个的特殊,换行(斜列)的特殊性)等等,就出来了一坨大便🥔:

#include<bits/stdc++.h>
#define int long long
const int N=1e7+10;
using namespace std;
int read() {int n;scanf("%lld",&n);return n;}
//long long int read() {long long int n;scanf("%lld",&n);return n;}
//struct 
//{

//};

//int main()
signed main()
{
    int n=read();
    //freopen(" .in","r",stdin);
    //freopen(" .out","w",stdout);
    vector<pair<int,int>>a(N,{0,0});
    for(int i=1,zhengshu=1,j=1,jiou=1;i<=n;i++,j++)
    {
        if(j>zhengshu)//初
        {
            j=1;
            zhengshu++;
            jiou*=-1;
            if(jiou==1)
                a[i]={zhengshu,1};
            else
                a[i]={1,zhengshu};
            continue;
        }
        if(j==zhengshu)//末
        {
            if(jiou==1)
                a[i]={1,zhengshu};
            else
                a[i]={zhengshu,1};
            continue;
        }
        if(jiou==1)
            a[i]={zhengshu+1-j,j};
        else
            a[i]={j,zhengshu+1-j};
    }
    cout<<a[n].first<<"/"<<a[n].second;
    return 0;
}

大概就长这样。。。丑死了......

虽然说是过了(似乎是全交流电AC)，但依旧不影响他是依托石。额(～﹃～)~zZ..........

women我们似乎不难发现有许多重复的地方，因此将他们整合到一起，就将便便扩大了

代码优化了。。。

似乎是这样:

#include<bits/stdc++.h>
#define int long long
const int N=1e7+10;
using namespace std;
int read() {int n;scanf("%lld",&n);return n;}
signed main()
{
    int n=read();
    vector<pair<int,int> >a(N,{0,0});
    for(int i=1,zhengshu=1,j=1,jiou=1;i<=N;i++,j++)
    {
        if(j>zhengshu)
            j=1,zhengshu++,jiou*=-1;
        a[i]={zhengshu+1-j,j};
		if(jiou<0)
            swap(a[i].first,a[i].second);
    }
    cout<<a[n].first<<"/"<<a[n].second;
    return 0;
}

这个办法也是非常有优化，成功的让我在我使用的OJ上使用O(n)的复杂度得到了排行榜倒数第一的成绩(反正能AC,适合刚学一维数组的友人们做)(千万别点)

差点就满足了，所以准备再优化一下这坨 便 编码

<bits\stdc++.h>

————————————————————又名"花逝爆零人Ⅱ"

花逝爆零人还有三分钟寻到钻石，4106的条子们已经将孜然撒的沸沸扬扬

是番茄还是香辣，我们无从得吃，众人抢食，花逝爆零人只是独自一人寻找着 钻石。 世界无穷，y=11无限宽广，花逝爆零人从一无所有空手而来，自当逝于小 白之手。最让他永远难忘的是，那一次次看见的bits\stdc++.h，矿洞不大， 但填满了对头文件的牵挂，在2025年的那个11月1号上午八点，花逝爆零人与

<bits\stdc++.h> 初次遇见，经历了三个半小时的无微不至的陪伴，<bits\std c++.h>在花逝爆零人的每行代码上都发挥了至关重要的CE作用，看到分数的那 一晚，激动的泪水从眼中流出，花逝爆零人恨不得早一点发现<bits\stdc++.h> -------花逝爆零人最难忘的羁绊。 在矿洞中无限寻找，并没有发现钻石，只有无尽的神秘绿色史蒂夫、白皮 射箭手与黑皮肤的“失败的(spider)”.....以及那来自 <bits\stdc++.h>的乐 趣。花逝爆零人突然想到了什么，在深臣爆零，不对是开门之时，打开了c++， 可他无意间敲下的那行"bits/stdc++.h",却似乎背叛了那影响他整个c++生涯的 头文件。 他的行为引来了<bits\stdc++.h>的报应，深臣莫名奇妙走到了他的桌前，

打开了花逝爆零人的浏览器，却没有输入那串花逝爆零人差点无数次输入的“ http::std::include<bits\stdc++.h>”，而是点开了花逝爆零人寻找钻石的 踪迹，大概是早有预料吧，他紧的尝试回到座位------输入那久违的“bits stdc++.h>。 可这背叛之事，怎是那么容易一笔勾销的......花逝爆零人终究还是没赶 得上深臣的鼠标速度，深臣在无数行的stdc++\h中，找到了那串stdc--\h，花 逝爆零人被代表着忠与义的深臣给带走了，他即将受到与他长相厮守的、却遭 到心系之人背叛的<bits\stdc++.h> 的制裁。 正义的象征---深臣，将那不守纪律与情分的花逝爆零人带走了，教室内的 老式爆零人们感到十分困惑。那是因为没有人愿意相信，我们的花逝爆零大佬 、第一个与<bits\stdc++.h>这一至关重要的头文件搭上姻缘的花逝爆零人，会 背弃他一生的执念。。。 我们的花逝爆零人，孤独的站在墙边，脑海中似乎在一遍又一遍的谴责自己 -----为何不在矿坑中用圆石摆上那一句<bits\stdc++.h>------又为何要寻找钻 石，而不是老老实实的写c++。每当有其他爆零人路过，他就想向他们怒吼：“ 我是一个花逝爆零人，我会写<bits\stdc++.h>我并没有背叛 <bits\stdc++.h>!

可一切已经晚了。。。又或者说他早已背叛了<bits\stdc++.h>。在2025年 11月1日的那个上午，他就对那位<bits\stdc++.h>产生了一些埋怨。他似乎一直 在尝试背叛<bits\stdc++.h>这次被深臣制裁，只是长久的报应罢了(据禄沁烟爆 料) 哈哈哈，这就是所谓的花逝爆零人吗？到头来只是背弃 <bits\stdc++.h>的一 位负心汉罢了。只是此刻，众多的爆零人都想争抢着写着那句珍贵的、重要的、 花逝的又被破坏的-----

<BITS\\STDC++.H>!!!