Believe it

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 题意给你一个集合s让你把这个集合划分为两个集合在集合A中若x存在则a-x也存在在集合B中若x存在则b-x也存在 数据范围|s|<1e5 a<1e9 b<1e9 注意集合中不包含相同的数 题解使用并查集维护，容易证明若x和a-x存在，则他们必定在同一个集合中x和b-x同理 代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include<bits/stdc++.h>using namespace std;map<int,int>fa;int find(int x){ if(fa.find(x)==fa.end()) fa[x]=x; return x==fa[x]?x:fa[x]=find(fa[x]);&# ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 多项式多项式在计算机中一般以数组方式储存，假设有一个多项式$f(x)$，并且$x^i$前面的系数为$a_i$，那么显然我们恰好可以用一个数组$a$来描述这个多项式， 多项式的系数$a_i$恰好存在数组$a$的第$i$项$a[i]$ 多项式dft在一般的多项式中，如果模数允许，乘法采取ntt来做，因为速度较快，多项式乘法是整个多项式体系的基石，他的常数如果太大，将影响到后面的所 有的多项式操作 多项式前期预处理我们需要设置多项式最大长度，模数，原根，多项式最大长度的log，以及关键点reduce函数，传入一个-mod到mod之间的数x，返回x%mod,他比取模更快，然后是快速幂，在往后是复数i在模意义下的值，2i在模意义下的逆元,以及后面的逆元数组和他的初始化函数 12345678910111213141516171819202122const int maxn=100005<< ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 1234567891011// a^x === b x=lg(a,b)int bsgs_lg(int a,int b,int mod){ map<int,int>mp; int sqr=sqrt(mod-1)+1; for(int i=0;i<sqr;i++) mp[qpow(a,i,mod)]=i; // baby step for(int i=0;i<mod-1;i+=sqr){ // giant step int tp=1ll*b*qpow(a,mod-1-i,mod)%mod; // a^(-i) if(mp.find(tp)!=mp.end()) return i+mp[tp]; } return -1;// error }

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 积性函数对于一个离散函数$f(x), x\in Z^+$ , 如果$\forall \gcd(a,b)=1$都有$f(a\cdot b)=f(a)\cdot f(b)$, 则称函数$f(x)$为积性函数。 完全积性函数对于一个离散函数$f(x), x\in Z^+$ , 如果$\forall a,b\in Z^+$都有$f(a\cdot b)=f(a)\cdot f(b)$, 则称函数$f(x)$为完全积性函数。 积性函数分析我们根据积性函数的定义，其实只要我们计算出了所有素数的幂的函数值，则任何其他$f(x)$都可以快速获取。 对此笔者准备了一个模版，我们只需要修改其中的56到63行即可 欧拉函数$\phi(n)$就是小于等于n，且与n互质的数的个数。 123456789101112//O(lgn)适用于少求int euler(int n){ i ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 很早就想写这个了，觉得好厉害，结果分析停留在理论上，其实时间复杂度贼高 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081#include<bits/stdc++.h>using namespace std;struct big0{//最大999999， int o,h,l;// 溢出6位 高3位 低3位 big0(){} big0(int rhs):o(0),h(0),l(rhs){} big0(int h,int l):o(0),h(h),l(l)
...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 强联通123456789101112131415161718192021222324252627282930313233343536373839404142434445464748struct Tarjan:Graph{//强连通分量缩点 int low[maxn],dfn[maxn],belong[maxn],stk[maxn],instk[maxn],block[maxn]; int step,color; void tarjan(){ step=color=0; for(int i=0;i<=n;i++) dfn[i]=0; for(int i=1;i<=n;i++) if(dfn[i]==0) tarjan(i,0);//多个联通快 } void tarjan(int ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748struct Graph{ static const int maxn=1e5+5, maxm=3e5+5; struct star{int v,nex;}edge[maxm<<1]; int head[maxn],cnt; void ini(int n){ for(int i=0;i<=n;i++) head[i]=-1; cnt=-1; } void add_edge(int u,int v){ edge[++cnt]=star{v,head[u]&# ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 程序跑起来都是跟地址相关的，可以试想，如果多个程序一起跑，难道不相互影响吗？又或者说 为什么我们写代码，从不去关心我们的程序在哪里运行？大家都用一个Memory，为什么没有相互破坏？好神奇！！ 为了让多个程序在同一台计算机上更好的运行，而不发生相互破坏性影响，虚拟内存的概念被提了出来，从此多个程序都有了独立的地址空间。 虚拟内存，是与物理内存相对应的，可以设想，我们程序a运行起来，写地址Mx1，程序b运行起来 也写Mx1，结果是，他们没有相互影响，为什么？因为这个地址Mx1是虚拟内存，是假的，程序a的mx1 和程序b的mx1不是同一个地址，程序a写Mx1，结果写到哪去了呢？我们不知道，这件事是操作系统 完成的，他把程序a的Mx1映射到了一个地方，又把程序b的Mx1映射到了另一个地方，这两个程序就能 独立的跑起来了。 解决上述问题的方法很简单，是有一个叫做页表的东西来完成的。 内存分页为了更 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 我们用数学方式来重新定义计算机里面的运算，因为内存是有限的，所以我们在计算机当中 存储数据的时候，这些数据都是有范围的数，所以所有的运算都是建立在模数上的，例如加法成了 模加。a+b成了（a+b）%mod。 为了让减法跑的更快，我们把减法丢掉了，于是这个世界只有加法了。减法成了加一个负数。 负数又是怎么定义的呢？如果x=-1，我们可以这样来存储（0-1+mod）%mod=mod-1 于是我们把负数也映射到了新的正数上。 由于模加也满足加法的交换率结合律等等优良性质。很明显，对于负数-x和-y我们存的是mod-x 和mod-y，于是经历模加（-x+-y）%mod=（mod-x+mod-y)%mod这显然是正确的。

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial # Cache的基本理论指导 ​ 由于计算机内部memery与 processor之间的速度差距过大，导致计算机整体速度降低，memery拖慢了速度。于是人们想出 了一个办法来解决他。缓存Cache诞生了。​ Cache相对于Memery来说，速度快了很多，速度快意味着造价高，容量小，这是代价，我们没有那么多钱来用Cache来当作 Memery，于是我们尝试，让他作为Processor与Memery的中介。​ 为什么要Cache，因为Memery太慢了，用Cache的话，容量问题很显然，Cache很小，没有Memery那么大。但是我们的初衷 是什么，用Cache去代替Memery，但是，Cache这个家伙小啊，我们不可能把一个大的东西放进一个小的盒子里面。 这是缓存 面临的最大问题。​ 重新思考计算机的运转，指令是一条一条执行的，当计算机运转的时候，CPU关心的 ...