公式杂项

Fluorine Wang

2024-05-02

ACM

Algorithm, Cpp, Math

RT,这里放一些奇奇怪怪的公式.

常见质数常用质数

1
2
3

99844353
1000000007 1e9+7
100000000000000003 1e17+3

判定奇数判定偶数

1 2	n&1 //奇数 n&1^1 //偶数,再也不用 !(n&1)

三角形

正弦定理, $R$ 是外接圆半径

$\frac{a}{\sin A}=\frac{b}{\sin B}=\frac{c}{\sin C}=2R$

余弦定理

$c^{2}=a^{2}+b^{2}-2ab\cos (C)$

数位DP

// 计算在 [0, M] 范围内，第 pos 位数字为 digit 的数有多少个
ll count_digit_at_pos(ll M, int pos, int digit) {
    ll p10 = 1;
    for (int i = 0; i < pos; ++i) p10 *= 10;
    
    ll high = M / (p10 * 10);
    ll cur = (M / p10) % 10;
    ll low = M % p10;
    
    ll count = high * p10;
    if (cur > digit) {
        count += p10;
    } else if (cur == digit) {
        count += (low + 1);
    }
    // 特殊处理：如果 M 本身位数不够，且 digit 为 0，高位补零的情况
    // 但题目定义 x_i 是 [0, M]，通常认为 0 填充是合法的
    return count;
}

自适应辛普森积分

double a,b,c,d,l,r;
inline double f(double x){//f(x)被积分函数
    return (c*x+d)/(a*x+b);       
}
inline double simpson(double l,double r){//Simpson公式
    double mid=(l+r)/2;
    return (f(l)+4*f(mid)+f(r))*(r-l)/6;
}
double asr(double l,double r,double eps,double ans){
    double mid=(l+r)/2;
    double l_=simpson(l,mid),r_=simpson(mid,r);
    if(fabs(l_+r_-ans)<=15*eps) return l_+r_+(l_+r_-ans)/15;//确认精度
    return asr(l,mid,eps/2,l_)+asr(mid,r,eps/2,r_);//精度不够则递归调用
}
inline double asr(double l,double r,double eps){
    return asr(l,r,eps,simpson(l,r));
}

快速阶乘算法

能够快速求出1e9范围内的n! mod p,复杂度 $O(\sqrt n\log n)$ ,模数是质数.

const long double Pi=acos(-1.0);
using poly=vector<long long>;
long long mod,tot,rev[1<<20];
struct Complex {
    long double x,y;
    Complex operator +(Complex o)const { return {x+o.x,y+o.y}; }
    Complex operator -(Complex o)const { return {x-o.x,y-o.y}; }
    Complex operator *(Complex o)const { return {x*o.x-y*o.y,x*o.y+y*o.x}; }
}A[1<<20],B[1<<20],C[1<<20],D[1<<20];
long long power(long long a,long long b=mod-2){
    long long res=1;
    while (b) {
        if (b&1) res=res*a%mod;
        a=a*a%mod,b>>=1;
    }
    return res;
}
void FFT(Complex *a){
    for (long long i=0;i<tot;i++)
    if (i<rev[i]) swap(a[i],a[rev[i] ]);
    for (long long len=1;len<tot;len<<=1)
    {
        Complex w={cos(Pi/len),sin(Pi/len)};
        for (long long i=0;i<tot;i+=len<<1) {
            Complex wk={1,0},x,y; for (long long j=0;j<len;j++,wk=wk*w)
            x=a[i|j],y=a[i|len|j]*wk,a[i|j]=x+y,a[i|len|j]=x-y;
        }
    }
}
void IFFT(Complex *a){
    FFT(a),reverse(a+1,a+tot);
    for (long long i=0;i<tot;i++) a[i].x/=tot,a[i].y/=tot;
}
poly mul(poly a,poly b){
    long long n=a.size()+b.size()-1; tot=1;
    long long l=-1; while (tot<n) tot<<=1,l++;
    for (long long i=0;i<tot;i++) A[i]=B[i]={0,0};
    for (long long i=0;i<tot;i++) rev[i]=rev[i>>1]>>1|(i&1)<<l;
    for (long long i=0;i<a.size();i++) A[i]={a[i]>>16,a[i]&65535};
    for (long long i=0;i<b.size();i++) B[i]={b[i]>>16,b[i]&65535};
    FFT(A); for (long long i=0;i<tot;i++) C[i]=A[(tot-i)%tot],C[i].y*=-1;
    FFT(B); for (long long i=0;i<tot;i++) D[i]=B[(tot-i)%tot],D[i].y*=-1;
    for (long long i=0;i<tot;i++) {
        auto x=A[i],y=B[i],p=C[i],q=D[i];
        A[i]=(p+x)*(q+y)*(Complex){0.25,0}+(p+x)*(q-y)*(Complex){-0.25,0};
        B[i]=(p-x)*(q+y)*(Complex){0,0.25}+(p-x)*(q-y)*(Complex){0,-0.25};
    }
    IFFT(A),IFFT(B),a.resize(n);
    for (long long i=0;i<n;i++) {
        long long x=round(A[i].x),y=round(A[i].y+B[i].x),z=round(B[i].y);
        a[i]=( (x%mod<<32)+(y%mod<<16)+z)%mod;
    }
    return a;
}
poly Lagrange(poly a,long long l,long long r){
    long long m=a.size(); poly b;
    poly fact(r-l+m+1),ifact(r-l+m+1);
    if (l<m) {
        b.resize(r-l+1);
        for (long long i=0;l+i<m&&l+i<=r;i++) b[i]=a[l+i];
        if (r<m) return b; poly c=Lagrange(a,m,r);
        for (long long i=m;i<=r;i++) b[i-l]=c[i-m]; return b;
    }
    b.resize(r-l+m),fact[0]=ifact[0]=ifact[1]=1;
    for (long long i=2;i<m;i++) ifact[i]=ifact[mod%i]*(mod-mod/i)%mod;
    for (long long i=1;i<m;i++) ifact[i]=ifact[i-1]*ifact[i]%mod;
    for (long long i=0;i<m;i++) {
        a[i]=a[i]*ifact[i]%mod*ifact[m-i-1]%mod;
        if ( (m-i-1)&1) a[i]=(mod-a[i])%mod;
    }
    for (long long i=1;i<=r-l+m;i++) fact[i]=fact[i-1]*(i+l-m)%mod;
    ifact[r-l+m]=power(fact[r-l+m]);
    for (long long i=r-l+m;i;i--) ifact[i-1]=ifact[i]*(i+l-m)%mod;
    for (long long i=0;i<r-l+m;i++) b[i]=ifact[i+1]*fact[i]%mod;
    a=mul(a,b),b.resize(r-l+1); for (long long i=0;i<=r-l;i++)
    b[i]=a[i+m-1]*fact[i+m]%mod*ifact[i]%mod; return b;
}
long long fac(long long n,long long mod){
    long long m=sqrt(n),res=1;
    poly a(2); a[0]=1,a[1]=(m+1)%mod;
    for (long long i=__lg(m)-1,n=1;~i;i--){
        long long tmp=n*power(m)%mod; n<<=1;
        poly b=Lagrange(a,0,n),c=Lagrange(a,tmp,min(tmp+n,mod-1) );
        if (tmp+n>=mod) { poly d=Lagrange(a,0,(tmp+n)%mod); for (long long x:d) c.push_back(x); }
        a.resize(n+1); for (long long i=0;i<=n;i++) a[i]=b[i]*c[i]%mod;
        if (m>>i&1) {
            long long val=1; n++;
            for (long long i=0;i<n;i++)
            a[i]=a[i]*(i*m+n)%mod,
            val=val*(n*m+i+1)%mod;
            a.push_back(val);
        }
    }
    for (long long i=0;i<m;i++) res=res*a[i]%mod;
    for (long long i=m*m+1;i<=n;i++) res=res*i%mod;
    return res;
}

距离

int dis(int x,int y,int xx,int yy){//切比雪夫距离
    return max(abs(x-xx),abs(y-yy));
}
int dis(int x,int y,int xx,int yy){//曼哈顿距离
    return abs(x-xx)+abs(y-yy);
}

曼哈顿距离转切比雪夫距离

曼哈顿距离:只能横着走竖着走.
切比雪夫距离:象棋中”帅”的走法,横竖,或斜着走一格.
(推公式:把曼哈顿距离中等高的线斜过来)

$(x,y)\to(x-y,x+y)$

切比雪夫转曼哈顿

$(x,y)\to(\frac{x+y}2,\frac{x-y}2)$

“注意到”…

x^y >= x-y 仅在二进制下成立(广义抑或按不进位加法处理)

MEX

定义是最小的没出现在数列中的非负整数.

int mex(int* dat,int n){//[1,n]
    unordered_map<int,int>mp;
    for(int i=1;i<=n;++i){
        mp[dat[i]]=1;
    }
    for(int i=0;i<n;++i){
        if(mp[i]!=1)return i;
    }
    return n;
}
//以下是求第k大mex,也就是第k个没出现的非负整数
template<typename T>
T mex(T* p,T n,T k){//[1,n]
    unordered_map<int,int>mp;
    for(int i=1;i<=n;++i){
        mp[p[i]]=1;
    }
    int res=n+k-1;
    for(int i=0;i<=res;++i){
        if(mp[i]==0)k--;
        if(k<=0)return i;
    }
    return res;
}

卡特兰数

$Catalan_n=\frac{(2n)!}{n!(n+1)!}$ $f[n]=f[0]*f[n-1]+f[1]*f[n-2]+...+f[n-1]*f[0](n\ge2)$ $1,1,2,5,14,42,132,429$

__int128 Catalan(int n){
    __int128 f[n+1]{};
    f[0]=1;
    for(int i=1;i<=n;++i){
        for(int j=0;j<i;++j){
            f[i]+=f[j]*f[i-j-1];
        }
    }
    return f[n];
}

随机数生成

使用MT19937作为随机数引擎.

std::mt19937 r32(chrono::system_clock::now().time_since_epoch().count());
unsigned int rand32(unsigned int l,unsigned int r){//[l,r]
    return r32()%(r-l+1)+l;
}
std::mt19937_64 r64(chrono::system_clock::now().time_since_epoch().count());
unsigned long long rand64(unsigned long long l,unsigned long long r){//[l,r]
    return r64()%(r-l+1)+l;
}

斐波那契数列(广义斐波那契数列)

$a_n=pa_{n-1}+qa_{n-2}$

可以转换成矩阵乘法的形式:

$\begin{bmatrix}a_{n-1}&a_{n-2}\end{bmatrix}\begin{bmatrix}p&1\\q&0\end{bmatrix}=\begin{bmatrix}a_n&a_{n-1}\end{bmatrix}$

所以有(假设 $a_0$ 是1)

$\begin{bmatrix}1&1\end{bmatrix}\begin{bmatrix}1&1\\1&0\end{bmatrix}^n=\begin{bmatrix}a_n&a_{n-1}\end{bmatrix}$

函数只填第几项就是传统斐波那契数列了.

long long Fibonacci(int num,long long a1=1,long long a2=1,int p=1,int q=1,long long mod=1000000007){
    //第几项，第一项第二项，系数1和2，取模 
    //an=p*an-1+qan-2
    if(num<3){
        if(num==1)return a1;
        else return a2;
    }
    num-=3;
    long long tmp[4]={p,1,q,0},res[4]={p,1,q,0};
    while(num>0){
        if(num&1)
            tie(res[0],res[1],res[2],res[3])=make_tuple((res[0]*tmp[0]+res[1]*tmp[2])%mod,(res[0]*tmp[1]+res[1]*tmp[3])%mod,(res[2]*tmp[0]+res[3]*tmp[2])%mod,(res[2]*tmp[1]+res[3]*tmp[3])%mod);
        tie(tmp[0],tmp[1],tmp[2],tmp[3])=make_tuple((tmp[0]*tmp[0]+tmp[1]*tmp[2])%mod,(tmp[0]*tmp[1]+tmp[1]*tmp[3])%mod,(tmp[0]*tmp[2]+tmp[2]*tmp[3])%mod,(tmp[1]*tmp[2]+tmp[3]*tmp[3])%mod);
        num>>=1;
    }
    return (res[0]*a2+res[2]*a1)%mod;
}

日期计算

基姆拉尔森公式,输入几几年几月几日返回一个数n表示周几.

int CalculateWeekDay(int y,int m,int d){
    if(m==1||m==2)m+=12,y--;
    return ((1LL*d+(m<<1)+3*(m+1)/5+y+y/4-y/100+y/400)%7)+1;
}

错排(单点计算)

解决n种元素的排列满足每一个都不在原先自己的位置上.公式:

$D(n)=n!\sum_{k=0}^n\frac{(-1)^k}{k!}$

__int128 Derangement(int num){
    __int128 rres=0,tmp=1;
    for(int i=1;i<num;++i){
        rres=(rres+(num-i)&1?tmp:-tmp)%mod;
        tmp=tmp*(num+1-i)%mod;
    }
    return rres;
}

错排(预处理递推)

$D_n=(n-1)(D_{n-1}+D_{n-2})$

long long D[1000010];
void init(int n){
    D[0]=1;D[1]=0,D[2]=1;
    for(int i=3;i<=n;++i){
        D[i]=(i-1)*(D[i-1]+D[i-2])%mod;
    }
}

最大不覆盖数

给两个数,求出最大的不能被两个数表示的数.结论: $ab-a-b$ (如果gcd不等于1就是正无穷,返回-1)

如何证明:考虑以一个数为模,另一个数在数表上挂,能证明出来.

i128 maxdec(i128 a,i128 b){
    if(__gcd(a,b)!=1)return -1;
    return a*b-a-b;
}

康托展开

解决n个元素的一种排列按顺序排列的名次.

#define mod 998244353
#define lowbit(x) (x&-x)
struct fenwick{
    int dat[1000010];
    void aadd(int pos,int val){
        for(;pos<=n;pos+=lowbit(pos)){
            dat[pos]+=val;
        }
    }
    long long qquery(int pos){
        long long res=0;
        for(;pos;pos-=lowbit(pos)){
            res+=dat[pos];
        }
        return res;
    }
};
long long fact[1000010];
fenwick cantor;
void ffact(int num){
    fact[0]=1;
    for(int i=1;i<=num;++i){
        fact[i]=fact[i-1]*i%mod;
    }
}
long long Cantor(int* tar,int num){//[1,n]
    ffact(num);
    long long k;
    long long res=0;
    for(int i=num;i>=1;--i){
        k=cantor.qquery(tar[i]);
        cantor.aadd(tar[i],1);
        res=(res+fact[num-i]*k)%mod;
    }
    return (res+1)%mod;
}

康托逆展开

RT,这是给一个排名求排列的过程,逆着来的.

#define mxxn 1000
struct segtree{//这个是权值线段树,由于区间加和,假如要求严格小于的有多少个就-1+1来弥补. 
    struct node{
        int l,r,val;
    };
    node* dat;
    segtree(){
        dat=new node[mxxn]{};
    }
    int top=0;
    int bbuild(int l,int r){//建空树,返回根节点 
        if(l>=r){
            ++top;
            dat[top].val=1;
            return top;
        }
        int mid=(l+r)>>1,tmp=++top;
        dat[tmp].l=bbuild(l,mid);
        dat[tmp].r=bbuild(mid+1,r);
        dat[tmp].val=dat[dat[tmp].l].val+dat[dat[tmp].r].val;
        return tmp;
    }
    void aadd(int mod,int l,int r,int pos,int val){//某点加多少 
        if(l>=r){
            dat[mod].val+=val;
            return;
        }
        dat[mod].val+=val;
        int mid=(l+r)>>1;
        if(pos<=mid)aadd(dat[mod].l,l,mid,pos,val);
        else aadd(dat[mod].r,mid+1,r,pos,val);
    }
    int qquery(int mod,int l,int r,int k){//查询第k小的元素坐标
        if(l>=r)return l;
        int mid=(l+r)>>1;
        if(dat[dat[mod].l].val>=k){return qquery(dat[mod].l,l,mid,k);}
        return qquery(dat[mod].r,mid+1,r,k-dat[dat[mod].l].val);
    }
};
void deCantor(int* res,__int128* fac,__int128 permu,int n){
    permu--;
    segtree ko;
    ko.bbuild(1,n);
    for(int i=1;i<=n;++i){
        int tmp=permu/fac[n-i]+1;
        permu%=fac[n-i];
        int rres=ko.qquery(1,1,n,tmp);
        ko.aadd(1,1,n,rres,-1);
        res[i]=rres;
    }
}

逆序对

公式是

$\sum_{i=1}^{n}\sum_{j=i+1}^n[a_i>a_j]$

该函数同时还是归并排序板子(参数是dat序列ddat辅助空数组res接受结果lr排序范围,写1-n或者0-(n-1)都可以)

void ssort(int* dat,int* ddat,long long& res,int l,int mid,int r){
    int hi=l,ho=mid+1,top=l;
    while(hi<=mid&&ho<=r){
        if(dat[hi]>dat[ho]){
            res+=mid-hi+1;
            ddat[top++]=dat[ho++];
        }
        else{
            ddat[top++]=dat[hi++];
        }
    }
    while(hi<=mid){
        ddat[top++]=dat[hi++];
    }
    while(ho<=r){
        ddat[top++]=dat[ho++];
    }
    return;
}
void msort(int* dat,int* ddat,long long& res,int l,int r){
    if(l>=r)return;
    int mid=(l+r)>>1;
    msort(dat,ddat,res,l,mid);
    msort(dat,ddat,res,mid+1,r);
    ssort(dat,ddat,res,l,mid,r);
    for(int o=l;o<=r;++o){
        dat[o]=ddat[o];
    }
    return;
}

欧拉函数(单点)

template<typename T>
T phi(T n){
    T res=n;
    for(T i=2;i*i<=n;i++){
        if(n%i==0)res=res/i*(i-1);
        while(n%i==0)n/=i;
    }
    return (n!=1)?(res/n*(n-1)):(res);
}

狄利克雷卷积(Dirichlet Convolution)

给定数论函数f和积性函数g,在 $O(n\log\log n)$ 时间内求出 $h=\sum_{i=1}^nf*g$ .

template<typename T1,typename T2>
void Dirichlet(T1* f,T2* g,int* prime,int n){
    for(int i=1;i<=primetop;++i){
        for(int j=n/prime[i];j>=1;--j){
            int t=prime[i];
            for(long long k=j*prime[i];k<=n;k*=prime[i]){
                f[k]=f[k]+f[j]*g[t];
                t*=prime[i];
            }
        }
    }
}//计算f*g的卷积，f是结果，要求g是积性函数 

template<typename T>
void Dirichlet(T* f,int* prime,int n){
    for(int i=1;i<=primetop;++i){
        int tmp=n/prime[i];
        for(int j=1;j<=tmp;++j){
            f[j*prime[i]]=(f[j*prime[i]]+f[j]);
        }
    }
}//计算一个积性函数前缀和（f*1） 

template<typename T>
void Dirichletde(T* f,int* prime,int n){
    for(int i=1;i<=primetop;++i){
        for(int j=n/prime[i];j;--j){
            f[j]=f[j]+f[j*prime[i]];
        }
    }
}//计算一个积性函数自身后缀和（f*1），也就是f(n)=sum(f(kn)),(kn<n)

D函数(数字每位和)

就是字面意思,把十进制每位数都加一起.

template<typename T>
int DFunction(T num){
    int res=0;
    while(num){
        res+=num%10;
        num/=10;
    }
    return res;
}

求[1,num]的所有数中0-9数码出现多少次(数位DP)

long long dp[21][10][10];
/*当前数字长度i,最高位为j,k这个数字有多少个*/
/*dp[2][1][1]表示[0,19]中1有多少个*/
void init(int num=20){
    for(int i=0;i<=9;++i){
        dp[1][i][i]=1;
    }
    for(int len=2;len<=num;++len){
        for(int i=0;i<=9;++i){
            for(int j=0;j<=9;++j){
                for(int k=0;k<=9;++k){
                    dp[len][i][k]+=dp[len-1][j][k];
                }
            }
            dp[len][i][i]+=pow(10,len-1);
        }
    }
}
vector<long long> getDigit(long long num){/*[0,num]中所有数出现次数*/
    num++;
    vector<long long>res(10,0);
    int dat[21]{},len=0;
    while(num>0){dat[++len]=num%10;num/=10;}
    for(int i=1;i<len;++i){/*位数不足len,不含前导零*/
        for(int j=1;j<=9;++j){
            for(int k=0;k<=9;++k){
                res[k]+=dp[i][j][k];
            }
        }
    }
    for(int i=1;i<dat[len];++i){/*原位一样,高位较小,无前导零*/
        for(int j=0;j<=9;++j){
            res[j]+=dp[len][i][j];
        }
    }
    for(int i=len-1;i>=1;--i){/*剩下的情况*/
        for(int j=0;j<dat[i];++j){
            for(int k=0;k<=9;++k){
                res[k]+=dp[i][j][k];
            }
        }
        for(int j=len;j>i;--j){
            res[dat[j]]+=dat[i]*pow(10,i-1);
        }
    }
    return res;
}

每次可以直线加上gcd,求最小极差

template<typename T>
int addgcd(T* dat,int n,T ggcd){
    for(int i=1;i<=n;++i){
        dat[i]%=ggcd;
    }
    sort(dat+1,dat+1+n);
    T res=dat[n]-dat[1];
    for(int i=1;i<n;++i){
        res=min(res,ggcd+dat[i]-dat[i+1]);
    }
}

求解 $\sum_{i=1}^n\lfloor\frac im\rfloor$

1
2
3

long long f(long long n,long long m){
    return (n/m-1)*(n/m*m)/2+(n/m)*(n%m+1);
}

PELL方程

求解形如 $x^2-dy^2=1$ 的方程,d是给出的,求最小解.
显然, $\begin{cases}x=\pm1\\y=0\end{cases}$ 一定是解,然后就是求正整数解.

两个性质:

$\begin{bmatrix}x_n\\ y_n\end{bmatrix}=\begin{bmatrix}x_1&dy_1\\y_1&x_1\end{bmatrix}^{n-1}\begin{bmatrix}x_1\\y_1\end{bmatrix}$ 这个是求第k个正整数解的(无解就是无解,有解就有无数个解)
当m是奇数时, $x=p,y=q$ 是方程 $x^2-dy^2=-1$ 的最小正整数解,m是偶数时这个方程无解.

pair<__int128,__int128> pell(__int128* dat,__int128 d,__int128 k=1){/* x^2 -d y^2 =1 求解 */
    long double sq=sqrt(d);/*    辅助内存     求解d     答案k次方*/
    __int128 ss=sq,m=-1,upper=1,lower=0;
    if(ss*ss==d)return {-1,-1};/*无解*/
    dat[++m]=sq;
    __int128 a=ss,b=1;
    do{
        b=(d-a*a)/b;
        dat[++m]=(sq+a)/b;
        a=dat[m]*b-a;
    }while((dat[0]<<1)!=dat[m]);
    for(int i=m-1;i>=0;--i){
        swap(upper,lower);
        upper+=dat[i]*lower;
    }
    pair<__int128,__int128> res;
    if(m&1)res={upper*upper<<1|1,upper*lower<<1};
    //求 x^2+dy^2=-1把if else改成res={upper,lower};
    else res={upper,lower};
    k--;
    __int128 base[5]={0,res.first,d*res.second,res.second,res.first},rres[5]{0,1,0,0,1};
    while(k){
        if(k&1)tie(rres[1],rres[2],rres[3],rres[4])=make_tuple(rres[1]*base[1]+rres[2]*base[3],rres[1]*base[2]+rres[2]*base[4],rres[3]*base[1]+rres[4]*base[3],rres[3]*base[2]+rres[4]*base[4]);
               tie(base[1],base[2],base[3],base[4])=make_tuple(base[1]*base[1]+base[2]*base[3],base[1]*base[2]+base[2]*base[4],base[3]*base[1]+base[4]*base[3],base[3]*base[2]+base[4]*base[4]);
        k>>=1;
    }
    return {rres[1]*res.first+rres[2]*res.second,rres[3]*res.first+rres[4]*res.second};
}

dat=[0]*200000
def pell(d):
    sq=math.sqrt(d)
    ss=int(sq);m=-1;upper=1;lower=0
    if ss*ss==d:
        return -1,-1
    m+=1;dat[m]=ss;
    a=ss;b=1;
    while True:
        b=int((d-a*a)//b)
        m+=1;
        dat[m]=int((sq+a)//b)
        a=dat[m]*b-a
        if dat[0]*2==dat[m]:
            break;
    for i in range(m-1,-1,-1):
        upper,lower=lower,upper
        upper+=dat[i]*lower
    if(m&1):
        return (upper*upper*2+1),upper*lower*2
    else:
        return upper,lower

绕线

给一堆散点和一个区间上下界,每次可以选个点进行反转(绕线),求最小极差.由于无论在哪里想进区间必定只有一种绕法,状态确定,就可以直接遍历检查.

template<typename T>
T mirrgcd(T* dat,int n,T a,T b){
    if(n==1)return 0;
    if(a>b)swap(a,b);
    T mxx=0,mnn;
    memset(&mnn,0x7f,sizeof(mnn));
    for(int i=1;i<=n;++i){
        T tmp=((dat[i]/a)&1)?(dat[i]%b):(b-(dat[i]%b));
        mxx=max(mxx,tmp);
        mnn=min(mnn,tmp);
    }
    return mxx-mnn;
}

镜面对称(上翻下翻)

形象理解为一个点绕着一条线坐标变换的过程.公式是 $2a-i$ .

template<typename T>
T mmirror(T i,T a){
    return 2*a-i;
}

阶乘取模,阶乘忽略模数的取模

int facmod(int* table,int n,int p){
    if(n<=p)return table[n];
    int res=((n/p)&1^1)?1:-1;
    res=(res*facmod(table,n/p,p))%p;
    res=(res*facmod(table,n%p,p))%p;
    return res;
}

阶乘中有多少个因数

$v_p(n!)$

int faccnt(int n,int p){
    int res=0;
    while(n){
        n/=p;
        res+=n;
    }
    return res;
}

摩尔投票

求一个数组中的绝对众数(出现次数大于n/2的元素),时间复杂度O(n),空间复杂度O(1)(边读边算),这玩意因为需要自己读,不封装了,直接裸板子.

fin>>n;
long long cnt=1,ttmp,tttmp;
fin>>ttmp;
for(int i=2;i<=n;++i){
    fin>>tttmp;
    if(tttmp==ttmp){
        cnt++;
    }else cnt--;
    if(cnt==0){
        ttmp=tttmp;
        cnt=1;
    }
}
fout<<ttmp<<"\n";

无限循环小数(小数)转分数

输入格式是 aa.bb(cc) 的格式,其中括号的cc可以没有,使用相减的方法求出循环节.

pair<i128,i128> conDiv(const char* io,int len){//[0,len)
    i128 upper=0,lower=1,circ=0,lenc=0;//循环节,循环节长度
    int ff=0,gg=0;//整数部分,是不是无限循环小数
    for(int i=0;i<len;++i){
        if(ff==0){
            if(io[i]=='.'){
                ff=1;
                continue;
            }
            upper=upper*10+io[i]-'0';
        }else{
            if(gg==0){
                if(io[i]=='('){
                    gg=1;
                }else{
                    upper=upper*10+io[i]-'0';
                    lower*=10;
                }
            }else{
                if(io[i]==')'){
                    break;
                }
                circ=circ*10+io[i]-'0';
                lenc++;
            }
        }
    }
    if(gg==0){//有限小数
        gg=__gcd(upper,lower);
        upper/=gg;
        lower/=gg;
    }else{//无限循环小数
        i128 p10=pow((long double)10,lenc);
        upper=upper*p10+circ-upper;
        lower=lower*p10-lower;
        gg=__gcd(upper,lower);
        upper/=gg;
        lower/=gg;
    }
    return {upper,lower};
}

分数转无限循环小数

给一个分数,输出对应的无限循环小数,循环节被括号包住.

string toCircle(long long upp,long long low,char flag=0){/*分数转循环小数,0正1负*/
    unordered_map<long long,long long>mp;/*eg:(1,7,0)=0.(142857)*/
    string res;
    if(flag==1)res='-';
    res+=to_string(upp/low);
    upp=upp%low*10;
    long long up=upp;
    if(up==0)return res;/*整数*/
    else res+=".";
    long long dec,dd=-1;
    for(int dep=1;;++dep){
        if(up<=0){/*不存在循环节*/
            for(int i=1;i<dep;++i){
                res+=(upp/low+'0');
                upp=upp%low*10;
            }
            return res;
        }
        if(mp[up]!=0){
            dec=mp[up];
            dd=dep-1;
            break;
        }else mp[up]=dep;
        up=up%low*10;
    }
    for(int i=1;i<dec;++i){
        res+=(upp/low+'0');
        upp=upp%low*10;
    }
    res+='(';
    for(int i=dec;i<=dd;++i){
        res+=(upp/low+'0');
        upp=upp%low*10;
    }
    return res+')';
}

连分数转分数

举例

$[1,2,3,4]=1+\frac1{2+\frac1{3+\frac14}}=\frac{43}{30}$

pair<long long,long long> conFrac(long long* dat,int len){/*[0,len],把连分数转成分数*/
    if(len==0)return {dat[0],1};
    long long upper=dat[len],lower=1;
    for(int i=len-1;i>=0;--i){
        swap(upper,lower);
        upper+=dat[i]*lower;
    }
    return {upper,lower};
}

根号转连分数

每一个根号都可以转换成有周期的连分数.长这样: $[a_0,a_1,…,a_m,a_1,a_2,…,a_m,a_1,…]$ ,一个性质是 $a_m=2a_0$ ,代码会返回最小周期m.

int conDiv(__int128 d,__int128* dat){/*根号转连分数,[0,m]*/
    long double sq=sqrt(d);
    __int128 ss=sq,m=-1,a=sq,b=1;
    dat[++m]=sq;
    if(d==dat[0]*dat[0])return -1;/*完全平方数*/
    do{
        b=(d-a*a)/b;
        dat[++m]=(sq+a)/b;
        a=dat[m]*b-a;
    }while((dat[0]<<1)!=dat[m]);
    return m;
}

简易分数类

一个分数类,支持加乘操作,输出的是最简带分数的形式(太奇怪了).

struct divisor{//假分数
    __int128 upper,lower,num;
    divisor(__int128 a=0,__int128 b=1,__int128 c=0):upper(a),lower(b),num(c){}
    divisor operator +(const divisor& io)const{
        divisor res;
        res.upper=upper*io.lower+lower*io.upper;
        res.lower=lower*io.lower;
        __int128 tmp=__gcd(res.upper,res.lower);
        // assert(tmp!=0);
        res.upper/=tmp;
        res.lower/=tmp;
        res.num=(num+io.num+((res.upper)/(res.lower)));
        res.upper%=res.lower;
        return res;
    }
    divisor operator *(const divisor& io)const{
        divisor res;
        res.upper=num*lower*io.upper+io.num*upper*io.lower+upper*io.upper;
        res.lower=lower*io.lower;
        __int128 tmp=__gcd(res.upper,res.lower);
        assert(tmp!=0);
        res.upper/=tmp;
        res.lower/=tmp;
        res.num=(num+io.num+(res.upper/res.lower));
        res.upper%=res.lower;
        return res;
    }
    int lenth(__int128 tmp){
        int len=0;
        if(tmp<=0){len++;tmp=-tmp;}
        while(tmp>0){
            len++;
            tmp/=10;
        }
        return len;
    }
    void prr(){
        if(upper!=0){
            int sp=lenth(num);
            int sl=max(lenth(upper),lenth(lower));
            for(int i=1;i<=sp;++i){
                fout<<" ";
            }
            fout<<upper<<"\n";
            fout<<num;
            for(int i=1;i<=sl;++i){
                fout<<"-";
            }enter;
            for(int i=1;i<=sp;++i){
                fout<<" ";
            }
            fout<<lower;
        }else{
            fout<<num;
        }
    }
};

德州扑克规则

按照德州扑克的规则比较两堆牌的大小.

struct cards{
    struct node{
        int num,fl;/*数字大小,花色*/
        int use;/*比较时有没有组成牌型*/
        char operator <(const node& io)const{
            if(use==io.use){
                return num>io.num;
            }else{
                return use>io.use;
            }
        }
    };
    node* dat;
    int top;
    cards(){
        dat=new node[10]{};
        top=0;
    }
    void addcard(char* ddat){/*加卡片,值域映射[2-14],A是14*/
        top++;
        dat[top].use=0;
        char &flopos=ddat[1],&numpos=ddat[0];
        switch(flopos){
            case 'H':{/*红桃*/dat[top].fl=1;break;}
            case 'S':{/*黑桃*/dat[top].fl=2;break;}
            case 'D':{/*方片*/dat[top].fl=3;break;}
            default:{/*C梅花*/dat[top].fl=4;}
        }
        switch(numpos){
            case 'T':{/*10*/dat[top].num=10;break;}
            case 'J':{dat[top].num=11;break;}
            case 'Q':{dat[top].num=12;break;}
            case 'K':{dat[top].num=13;break;}
            case 'A':{dat[top].num=14;break;}
            default:{dat[top].num=numpos-'0';}
        }
    }
    void clear(){
        top=0;
    }
    void del(int num){
        swap(dat[num],dat[top]);
        top--;
    }
    void ssort(){
        sort(dat+1,dat+1+top);
    }
    /*
    皇家同花顺 10
    普通同花顺 9 num 最大数字
    四条      8 num 相同数字
    三带一对  7 num 三个相同的数字
    同花      6 num 最大数字
    顺子      5 num 最大数字
    三条      4 num 相同数字
    两对      3 num 较大的一对
    对子      2 num 对子牌面
    散牌      1 num 散牌最大数字
    */
    pair<int,int> vval(){/*五张牌的比较,其实多了也不是不可以?*/
        int nnum[20]{};
        int se[5]{};
        for(int i=1;i<=top;++i){
            nnum[dat[i].num]++;
            se[dat[i].fl]++;
        }
        if(nnum[10]==1&&nnum[11]==1&&nnum[12]==1&&nnum[13]==1&&nnum[14]==1){
            ssort();
            if(se[1]==5||se[2]==5||se[3]==5||se[4]==5)return {10,0};/*皇家同花顺*/
            else return {5,14};/*顺子*/
        }
        for(int i=9;i>=2;--i){
            if(nnum[i]==1&&nnum[i+1]==1&&nnum[i+2]==1&&nnum[i+3]==1&&nnum[i+4]==1){
                ssort();
                if(se[1]==5||se[2]==5||se[3]==5||se[4]==5)return {9,i+4};/*皇家同花顺*/
                else return {5,i+4};/*顺子*/
            }
        }
        int cup=0,ff=0,mxx=0,mnnn=0,mxxx=0;/*对数,三个的对,两对最大的,散牌最大的,所有牌最大的*/
        for(int i=2;i<=14;++i){
            mxxx=max(mxxx,nnum[i]);
            switch(nnum[i]){
                case 4:{
                    return {8,i};
                }case 3:{
                    ff=i;
                    break;
                }case 2:{
                    cup++;
                    mxx=max(mxx,i);
                    break;
                }case 1:{
                    mnnn=max(mnnn,i);
                }
            }
        }
        if(ff!=0&&cup!=0){/*三带一对*/
            for(int i=1;i<=top;++i){           //
                if(dat[i].num==ff)dat[i].use=1;//
            }                                   //
            ssort();                           //
            return {7,ff};
        }
        if(se[1]==top||se[2]==top||se[3]==top||se[4]==top){
            ssort();
            return{6,mxxx};
        }
        if(ff!=0){
            for(int i=1;i<=top;++i){           //
                if(dat[i].num==ff)dat[i].use=1;//
            }                                   //
            ssort();                           //
            return{4,ff};
        }
        if(cup>=2){
            for(int i=1;i<=top;++i){
                if(nnum[dat[i].num]>=2)dat[i].use=1;
            }
            ssort();
            return{3,mxx};
        }
        if(cup==1){
            for(int i=1;i<=top;++i){
                if(nnum[dat[i].num]>=2)dat[i].use=1;
            }
            ssort();
            return {2,mxx};
        }
        ssort();
        return {1,mxxx};
    }
    char operator <(cards& io){
        auto i=vval();
        auto j=io.vval();
        if(i.first==j.first){
            if(i.second==j.second){
                for(int k=1;k<=top;++k){
                    if(dat[k].num!=io.dat[k].num){
                        return dat[k].num<io.dat[k].num;
                    }
                }
                return 0;/*这个值理论上不应该出现*/
            }else return i.second<j.second;
        }return i.first<j.first;
    }
    void prr(){
        for(int i=1;i<=top;++i){
            fout<<dat[i].num<<" "<<(int)dat[i].fl<<"\n";
        }enter;
    }
};

有n个因数的最小数

给定n,输出最小的有n个因数的数字.

int primes[]={1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73};
long double logs[22];
long double dp[50010][21];

long long dig[10002];
void mul(int num){
    for(int i=10000;i>0;--i){
        dig[i]*=num;
        dig[i+1]+=dig[i]/1000000000;
        dig[i]%=1000000000;
    }
}
void prr(){
    int ff=0;
    for(int i=10000;i>0;--i){
        if(ff){
            printf("%09lld",dig[i]);
        }else{
            if(dig[i]!=0){
                ff=1;
                printf("%lld",dig[i]);
            }
        }
    }
}
int tar[50010][21];
vector<int>d[50010];
long long n,m,res;
int main(){
    for(int i=1;i<=21;++i){
        logs[i]=log((double)primes[i]);
    }
    fin>>n;
    for(int i=2;i<=n;++i){
        for(int j=1;j<=20;++j){
            dp[i][j]=1e9;
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=2;j*j<=i;++j){
            if(i%j==0)
                d[i].push_back(j);
        }
        d[i].push_back(i);
        sort(d[i].begin(),d[i].end());
    }
    for(int i=2;i<=n;++i){
        dp[i][1]=(i-1)*logs[1];
        for(int j=2;j<=20;++j){
            for(int k:d[i]){
                double tmp=dp[i/k][j-1]+(k-1)*logs[j];
                if(dp[i][j]>tmp){
                    dp[i][j]=tmp;
                    tar[i][j]=k;
                }
            }
            if(dp[i][j-1]<dp[i][j]){
                dp[i][j]=dp[i][j-1];
                tar[i][j]=tar[i][j-1];
            }
        }
    }
    dig[1]=1;
    long double eps=1e-5;
    while(tar[n][20]>0){
        int k=tar[n][20];
        int j=exp((dp[n][20]-dp[n/k][20]+eps)/(k-1));
        for(int pow=1;pow<=k-1;++pow){
            mul(j);
        }
        n=n/k;
    }
    for(int i=1;i<n;++i){
        mul(2);
    }
    prr();
    return 0;
}

毕达哥拉斯方程

形如 $x^2+y^2=z^2$ 的方程,不能约分的叫做本质毕达哥拉斯方程.
设nm里面一个奇数一个偶数,较大的设为m,小的设为n,有

$\begin{cases}x=m^2-n^2\\y=2mn\\z=m^2+n^2\end{cases}$

然后求 $x+y+z<lim$ 的解发现nm的范围都是sqrt内,于是On枚举本质,然后乘上倍数即可求出所有的勾股数.

vector<pair<pair<int,int>,int> >pyth(int num){
    vector<pair<pair<int,int>,int> >res;
    int lim=sqrt(num);
    int x,y,z;
    for(int i=2;i<=lim;i+=2){
        for(int j=1;j<=lim;j+=2){
            if(__gcd(i,j)!=1)continue;
            auto k=minmax(i,j);
            x=k.second*k.second-k.first*k.first,y=2*k.second*k.first,z=k.second*k.second+k.first*k.first;
            if(x+y+z>num)break;
            res.push_back({{y,x},z});
        }
    }
    return res;
}

历法计算

下面的函数实现了常见的判断闰年计算从一天到新年有多少天,计算两个日期差多少天(全是闭区间)

const int kMonths[]={31,28,31,30,31,30,31,31,30,31,30,31};
char IsLunarYear(int y){
    return (y%4==0&&y%100!=0)||(y%400==0);
}
int CountDaysInAYear(int y,int m,int d){//计算当前年到结束有多少天
    int res=0;
    if(m<=2){
        for(int i=1;i<m;++i){
            res+=kMonths[i-1];
        }
        res+=d-1;
        if(IsLunarYear(y)==1){
            return 366-res;
        }else{
            return 365-res;
        }
    }else{
        for(int i=m;i<=12;++i){
            res+=kMonths[i-1];
        }
        res+=-d+1;
        return res;
    }
}
int CountDays(int y,int m,int d,int yy,int mm,int dd){
    if(y>yy||(y==yy&&m>mm)||(y==yy&&m==mm&&d>dd)){
        swap(y,yy);
        swap(m,mm);
        swap(d,dd);
    }
    int rres=0;
    rres+=CountDaysInAYear(y,m,d);
    for(int i=y+1;i<=yy;++i){
        rres+=(IsLunarYear(i)==1?366:365);
    }
    rres-=CountDaysInAYear(yy,mm,dd)-1;
    return rres;
}

称硬币(结论)

如果你知道假硬币比真硬币轻还是重,答案是 $\lfloor\log_3(n)\rfloor$ ,不知道答案就是 $\lfloor\log_3(2n+3)\rfloor$ .

罗马数字

下面板子的转出来的罗马数字遵循以下规则:

IVXLCDM 分别是1 5 10…
VLD 这种代表5 50 500的最多只用一次
IXX 不允许出现,尽量让表达简省.

string toRoman(int num){//[1,5000]
    string res;
    int tmp=num/1000;num%=1000;
    for(int i=0;i<tmp;++i)res+='M';
    tmp=num/100;num%=100;
    if(tmp==4){/*400*/tmp-=4;res+="DC";}
    else if(tmp==9){tmp-=9;res+="CM";}
    else if(tmp>=5){tmp-=5;res+='D';}
    for(;tmp>0;--tmp){res+='C';}
    tmp=num/10;num%=10;
    if(tmp==4){/*40*/tmp-=4;res+="XL";}
    else if(tmp==9){tmp-=9;res+="XC";}
    else if(tmp>=5){tmp-=5;res+='L';}
    for(;tmp>0;--tmp){res+='X';}
    tmp=num;
    if(tmp==4){/*40*/tmp-=4;res+="IV";}
    else if(tmp==9){tmp-=9;res+="IX";}
    else if(tmp>=5){tmp-=5;res+='V';}
    for(;tmp>0;--tmp){res+='I';}
    return res;
}//数字转罗马字符串
int RomProj(const char& io){
    switch(io){
        case 'I':return 1;
        case 'V':return 5;
        case 'X':return 10;
        case 'L':return 50;
        case 'C':return 100;
        case 'D':return 500;
        case 'M':return 1000;
        default:return 0;
    }
}//罗马字母映射
int RoToNum(const string& dat){
    int len=dat.size(),res=0,pre=0,tmp;
    for(int i=len-1;i>=0;--i){
        tmp=RomProj(dat[i]);
        if(tmp<pre)res-=tmp;
        else res+=tmp;
        pre=tmp;
    }
    return res;
}//罗马数字转字符

分形学

谢尔宾斯基分形

抑或版本的杨辉三角,注意杨辉三角第i行第j列的组合数是 $\binom{i-1}{j-1}$ .

1 
1 1 
1 0 1 
1 1 1 1 
1 0 0 0 1 
1 1 0 0 1 1
...

1
2
3

char Sierpinski(int posy,int posx){//[1,1]
    return (posx==posy?1:((((posy-1)&(posx-1))==(posx-1))?1:0));
}

常见质数 常用质数

判定奇数 判定偶数

三角形