CSP-S rp+++++++++++
ǰ����ʾ,��ƪ���´���ע��~
��ѧ
������
int ksm(int a,int b,int p){
int ret=1;
while(b){
if(b&1)ret=(ret*a)%p;
a=(a*a)%p;
b=b>>1;
}
return ret;
}
//b��λö�� �����λΪ1�������a ÿ��a�˷�
Lucas
int init(int a,int b){
ny[1]=1;
for(int i=2;i<N;i++)ny[i]=(mod-mod/i)*ny[mod%i]%mod;
jcny[0]=jcny[1]=1;
for(int i=2;i<N;i++)jcny[i]=jcny[i-1]*ny[i]%mod;
jc[0]=jc[1]=1;
for(int i=1;i<N;i++)jc[i]=jc[i-1]*i%mod;
}
//��ʼ�� ny��¼��Ԫ jcny��¼��Ԫ�Ľ׳� jc��¼�׳�
int c(int a,int b){
if(b>a)return 0;
return jc[a]*jcny[a-b]%mod*jcny[b]%mod;
}
//��a!/(a-b!*b!)���������
int lucas(int a,int b){
if(!b)return 1;
return c(a%mod,b%mod)*lucas(a/mod,b/mod)%mod;
}
//
exgcd
int exgcd(int a,int b,int &x,int &y){
//����ע������ ��ΪҪ��ֵ
if(!b){
//�Զ����ĵ�ax+0y=aʱ x=1,y=0
x=1,y=0;
return a;
int ret=exgcd(b,a%b,y,x);
//exgcd�ı��� ax+by=bx+(a%b)y
y-=(a/b)*x;
//exgcd�IJ��� x1=y2 y1=x2-(a/b)*x2
return ret;
}
}
exgcd����Ԫ
int inv(int a,int b){
int x,y;
int d=exgcd(a,m,x,y);
return (d==1?(x+m)%m:-1);
}
//exgcd����Ԫ������ͬ��̵�����ͬ
����С��������Ԫ
int inv(int a,int p){
//���� ����С���� a^p��a��mod p������ͬ��
//��תΪ a^p-2��a^-1��mod p������ͬ��
return ksm(a,p-2,p);
}
��������Ԫ
for(int i=2;i<n;i++){
int[i]=inv[p%i]*(p-p*i);
}
CRT
int crt(int k,int *a,int *r){
int n=1,ans=0;
for(int i=1;i<=k;i++)n=n*r[i];
//��������ģ���Ļ�
for(int i=1;i<=k;i++){
int m=n/r[i],b,y;//�� m=Sigma(ģ��)/��ģ��
exgcd(m,r[i],b,y);//���b*m mod r[i]=1�õ�m����Ԫ
ans=(ans+a[i]*m*b)%n;//�õ�c[i]=m[i]*m[i]^-1,��a[i]��˵õ���
}
return (ans%n+n)%n;//ȡģ~
}
exCRT
int excrt(int k,int *a,int *r){
int m=a[i],ans=a[i];
for(int i=2;i<=2;i++){
int c=
}
}
ŷ��ɸ+����ŷ������
bool vis[N];
int p[N],phi[N],cnt=1;
void initphi(){
phi[1]=1;
for(int i=2;i<N;i++){
if(!vis[i])p[cnt++]=i,phi[i]=i-1;
//���i��δ�����ʹ�i�϶�Ϊ����,������ŷ������ֵΪi-1
for(int j=1,v;(v=i*p[j])<N;j++){
vis[v]=1;
if(i%p[j]==0){
//���p[j]Ϊi������,��ͳ��ŷ������,��ͣ��
phi[i*p[j]]=phi[i]*p[j];
break;
}else phi[i*p[j]]=phi[i]*phi[p[j]];
}
}
}
Miller Rabin
//��ģ�峬��,�����ں���,��������Ӳ��
bool Miller_Rabin(int n,int s){
if(n==2)return 1;//2ΪΨһ��ż����,����
if(n<2||!(n&1))return 0;//����ż���϶�������,1ɶҲ����
int x,y,u=n-1,t=0;
while((u&1)==0)t++,u>>1;
for(int i=0;i<s;i++){//sΪ���Դ���
int a=rand()%(n-1)+1;
int x=ksm(a,u,n);
for(int j=0;j<t;j++){
int y=ksm(x,x,n);
if(y==1&&x!+1&&x!=n-1)return 0;
x=y;
}
}
if(x!=1)return 0;
}
ŷ������ ������
int euler(int n){
int ret=n;
for(int i=2;i*i<=n;i++){
if(n%i==0){
ret-=ret/i;
while(!(n%i))n/=i;
}
}
if(n>1)ret-=ret/n;
return ret;
//����˵ʲô,���Ƿֽ�������
}
�����ֿ�
for(int l=1,r;l<=n;l=r+1){
r=(n/(n/l));
cout<<n/l<<" "<<r-l+1<<endl;
}
��˹��Ԫ
int now=1;
for(int i=1;i<=n;i++){
//TODO: ��ϰ��˹��Ԫ
}
ɨ����
//���� ��������ѧ�������ģ��,ɨ����+�߶���
//TODO: ���߶���ģ��д�ú�ϰɨ����
���ݽṹ~
����ջ
void insert(int x){
while(!sta.empty()&&sta.top()<x)sta.pop();
//ά�������� ����pop�������ϵ����Ե�
sta.push(x);
}
��������
deque<int>d;
for(int i=1;i<=n;i++){
cin>>a;
while(!d.empty()&&d.end()>a)d.pop_back();
//ά�������� ����pop�������ϵ����Ե�
d.push_back(a);
}
01trie
int t[N*31][2],nv=1;
void build(int p,int d,int v){
bool flag=(v&(1<<d));
if(!t[p][flag])t[p][fkag]=++nv;
if(d)build(t[p][flag],d-1,v);
//�ݹ���λö��
}
int query(int p,int d,int v){
//��ѯ��λ���
if(d<0)return 0;
bool flag(v&(1<<d));
if(t[p][!flag])return (1<<d)+query(t[p][!flag],d-1,v);
//��ͬΪ1
if(t[p][!flag])return query(t[p][flag],d-1,v);
//��ͬΪ0
}
ST��
int logn=21;
void pre(){
Logn[1]=0;
Logn[2]=1;
for (int i=3;i<maxn;i++) {
Logn[i] = Logn[i / 2] + 1;
}
}
for(int j=1;j<=logn;j++){
for(int i=1;i+(i<<j)-1<=n;i++){
f[i][j]=max(f[i][j-1],f[i+(i<<(j-1))][j-1]);
}
}
��״����
#define lower_bit(x) (x)&-(x)
void add(int a,int c){
for(int i=a;i<=n;i+=lower_bit(i))tree[i]+=c;
}
void add(int r){
int ret=0;
for(int i=r;i>=1;i-=lower_bit(i))ret+=tree[i];
}