堆积的$TIPS$

对于FFT的精度小优化：

对于$PI$，关于预处理单位复数根，

精度差不少，感谢skyh大神的帮助

const long double PI=acos(-1.0L);
inline void init(const int &lim){
    for(int i=1;i<lim;i<<=1)
        for(int k=0;k<i;++k)
            omg1[i+k]=Cp(cos(PI*k/i),sin(PI*k/i));
    return ;
}

只用开一维数组，这种存法自己手模一下还是很清晰的

一种处理图的根号算法：

今天做题一道比较清新的$O(n*sqrt{n})$算法。

好像比较套路的样子。

在这个联通图里要维护一些东西，询问某个点所有连向点对他的贡献这个样子。

因为有些修改，比较难维护，所以貌似只能枚举的类型。

此时可以按点的度数划分使总的枚举次数减少。

具体是设个$lim=sqrt{n}$，把度数大于$lim$的点划分成大点，其次为小点。

然后以今天的题举例。

给定序列，要依次求这个点的相邻点的权值和，然后修改这个点。

可以设一个$sum_{x}$表示所有小点对点$x$的贡献。

每次询问小点贡献直接调用数组，大点枚举。

修改时如果此点为小点，枚举所有边更新$sum$。

可以时间复杂度保证在$O(n*sqrt{n})$

---

UPD：

$double$小数位，整数位都有可存位数多的特点，但精确的都是十几位。

---

UPD:

有一个结论是单峰函数复合起来还是单峰函数。

---

UPD:

　　二维hash。

　　实在没搞明白它的物理意义，不太像一维$hash$是个$p$进制数。

　　但打法和二位前缀和的容斥差不多，不过行列的模数不一样。

　　而且并不知道为何可以用小质数。。。

例题：对称的正方形

#include<cstdio>
#include<iostream>
#include<cstring>
#define MAXN 1100
#define LL long long
#define ull unsigned long long
using namespace std;
inline int min(int a,int b){return a<b?a:b; }
const ull mo1=1e9+7,mo2=72871824517;
int n,m;
int jz[MAXN][MAXN];
ull sm[4][MAXN][MAXN],bin1[MAXN],bin2[MAXN];
LL ans=0;
inline ull cal(int sx,int sy,int bx,int by,int opt){
    ull t1=bin1[by-sy+1],t2=bin2[bx-sx+1];
    switch(opt){
        case 0:return sm[0][bx][by]-sm[0][bx][sy-1]*t1-sm[0][sx-1][by]*t2+sm[0][sx-1][sy-1]*t1*t2;break;
        case 1:return sm[1][bx][sy]-sm[1][bx][by+1]*t1-sm[1][sx-1][sy]*t2+sm[1][sx-1][by+1]*t1*t2;break;
        case 2:return sm[2][sx][by]-sm[2][sx][sy-1]*t1-sm[2][bx+1][by]*t2+sm[2][bx+1][sy-1]*t1*t2;break;
        case 3:return sm[3][sx][sy]-sm[3][sx][by+1]*t1-sm[3][bx+1][sy]*t2+sm[3][bx+1][by+1]*t1*t2;break;
    }
    return -1;
}
void init(){
    bin1[0]=bin2[0]=1;
    for(int i=1;i<=n;++i)bin1[i]=bin1[i-1]*mo1;
    for(int i=1;i<=m;++i)bin2[i]=bin2[i-1]*mo2;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            sm[0][i][j]=jz[i][j]+1+sm[0][i-1][j]*mo2+sm[0][i][j-1]*mo1-sm[0][i-1][j-1]*mo1*mo2;
    for(int i=1;i<=n;++i)
        for(int j=m;j>=1;--j)
            sm[1][i][j]=jz[i][j]+1+sm[1][i-1][j]*mo2+sm[1][i][j+1]*mo1-sm[1][i-1][j+1]*mo1*mo2;
    for(int i=n;i>=1;--i)
        for(int j=1;j<=m;++j)
            sm[2][i][j]=jz[i][j]+1+sm[2][i+1][j]*mo2+sm[2][i][j-1]*mo1-sm[2][i+1][j-1]*mo1*mo2;
    for(int i=n;i>=1;--i)
        for(int j=m;j>=1;--j)
            sm[3][i][j]=jz[i][j]+1+sm[3][i+1][j]*mo2+sm[3][i][j+1]*mo1-sm[3][i+1][j+1]*mo1*mo2;
    return ;
}
inline bool _judge(int i,int j,int len,int opt){
    if(!len)return true;
    if(opt==1){
        ull t1=cal(i-len+1,j-len+1,i,j,0);
        ull t2=cal(i-len+1,j,i,j+len-1,1);
        if(t1!=t2)return false;
        ull t3=cal(i,j-len+1,i+len-1,j,2);
        if(t1!=t3)return false;
        ull t4=cal(i,j,i+len-1,j+len-1,3);
        if(t1!=t4)return false;
        return true;
    }
    else{
        ull t1=cal(i-len+1,j-len+1,i,j,0);
        ull t2=cal(i-len+1,j+1,i,j+len,1);
        if(t1!=t2)return false;
        ull t3=cal(i+1,j-len+1,i+len,j,2);
        if(t1!=t3)return false;
        ull t4=cal(i+1,j+1,i+len,j+len,3);
        if(t1!=t4)return false;
        return true;
    }
    return false;
}
int main(){
    //freopen("da.in","r",stdin);
    
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            scanf("%d",&jz[i][j]);
    init();
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j){
            int l=0,r=min(min(i,n-i+1),min(j,m-j+1));
            while(r-l>1){
                int mid=l+r>>1;
                if(_judge(i,j,mid,1))l=mid;
                else r=mid;
            }
            if(_judge(i,j,r,1))ans+=r;
            else ans+=l;
        }
    for(int i=1;i<n;++i)
        for(int j=1;j<m;++j){
            int l=0,r=min(min(i,n-i),min(j,m-j));
            while(r-l>1){
                int mid=l+r>>1;
                if(_judge(i,j,mid,2))l=mid;
                else r=mid;
            }
            if(_judge(i,j,r,2))ans+=r;
            else ans+=l;
        }
    printf("%lld
",ans);
    
    return 0;
}

---

 UPD:

两个关键字的问题，可以考虑排序其中一个，相当于钦定一个关键字的答案，另一个关键字可以贪心。

那么其实可以说是在有多个限制条件时，考虑是否可以在合法的时间复杂度内枚举（二分）其中的某个，其他限制能简单解决。

---

UPD:

 $\%\%$$fh$大神

尽量把维度小的放在前面，原理是：尽管数组访问是$O(1)$的，但如果访问$f[x][j-1]$和$f[y][j-1]$时，会先在$x$里找，再去$y$，如果把第二维放前面，就能保证询问的连续性，从而节省时间。

---

 UPD：

时间戳代替bool数组清空的思想应该仔细研究

一个数组的时间戳不一定要表示成状态是否为当前状态，可以表示成是否当前合法。

那么不为当前的时间戳的，要么原来就不合法，要么之前合法，但当前不合法。

---

 UPD：

字符串不能读入空格

---

 UPD：

$lucas$也用作$(n,m)$范围大的时候

---

UPD：

概率与期望，现在只能背了，证明都不太会

 

---

 UPD:

向上取整：

$ceil((double)x)$

---

 UPD:

小于$1e9$的数的约数个数最大为$1344$

---

 UPD：

$2e8$能筛出$1e7$多个素数