毛毛雨的板子们

这是一篇模板的整理
慢慢积累吧qwq
窝可以的!!

1
2
3
4
5
6
7
8
9
10
11
12
13
inline int read(){
int ret=0,ff=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') ff=-ff;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
ret=ret*10+ch-'0';
ch=getchar();
}
return ret*ff;
}

数据结构

树状数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <cstdio>
using namespace std;

int bit[MAX_N+1],n;

int sum(int i){
int s=0;
while(i>0){
s+=bit[i];
i-=i&-i;
}
return s;
}

void add(int i,int x){
while(i<=n){
bit[i]+=x;
i+=i&-i;
}
}

线段树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX=1e5+5;

int tree[MAX]; // 线段树
int lz[MAX]; // 延迟标记

void init(){
memset(tree,0,sizeof(tree));
memset(lz,0,sizeof(lz));
}

// 创建线段树
void build(int node,int l,int r){
if(l==r){
cin>>tree[node];
return;
}
int mid=(l+r)>>1;
build(node<<1,l,mid);
build(node<<1|1,mid+1,r);
tree[node]=tree[node<<1]+tree[node<<1|1];
}

// 单点更新,n为更新值,index为更新点,lr为更新范围
void update(int n,int index,int l,int r,int node){
if(l==r){
tree[node] = n; // 更新方式,可以自由改动
return;
}
int mid=(l+r)>>1;
// push_down(node,mid-l+1,r-mid); 若既有点更新又有区间更新,需要这句话
if(index<=mid) update(n,index,l,mid,node<<1);
else update(n,index,mid+1,r,node<<1|1);
tree[node]=tree[node<<1]+tree[node<<1|1];
}

void push_down(int node,int l,int r){
if(!lz[node]) return;
int mid=(l+r)>>1;
lz[node<<1]+=lz[node];
lz[node<<1|1]+=lz[node];
tree[node<<1]+=1LL*(mid-l+1)*lz[node];
tree[node<<1|1]+=1LL*(r-mid)*lz[node];
lz[node]=0;
}

// 区间更新,lr为更新范围,LR为线段树范围,add为更新值
void update_range(int node,int l,int r,int L,int R,int add){
if(l<=L&&r>=R){
lz[node]+=1LL*add;
tree[node]+=1LL*(R-L+1)*add; // 更新方式
return;
}
push_down(node,L,R);
int mid=(L+R)>>1;
if(mid>=l) update_range(node<<1,l,r,L,mid,add);
if(mid<r) update_range(node<<1|1,l,r,mid+1,R,add);
tree[node]=tree[node<<1]+tree[node<<1|1];
}

// 区间查找
LL query_range(int node,int L,int R,int l,int r){
if(l<=L&&r>=R) return tree[node];
push_down(node,L,R);
int mid=(L+R)>>1;
LL sum=0;
if(mid>=l) sum+=query_range(node<<1,L,mid,l,r);
if(mid<r) sum+=query_range(node<<1|1,mid+1,R,l,r);
return sum;
}

int main(){
init();
build(1,1,8);
return 0;
}

树链剖分

https://www.luogu.com.cn/problem/P3384

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <bits/stdc++.h>
#define inf 2000000000
using namespace std;
typedef long long ll;
const int N=100000;
//父亲节点,节点深度,子树节点个数,重儿子,所在链的顶端节点,节点dfs序,dfs序所对节点编号
int fa[N+10],dep[N+10],sz[N+10],son[N+10],top[N+10],seg[N+10],rev[N+10];
int n,m,root;
ll p,num[N+10],add[4*N+10],sum[4*N+10];
int tot=1,head[N+10];

struct EDGE{
int to,nxt;
}edge[2*N+10];

void add_edge(int u,int v){
edge[++tot].to=v;
edge[tot].nxt=head[u];
head[u]=tot;
}

void dfs1(int x,int f){ //当前节点,父亲节点
sz[x]=1;
fa[x]=f;
dep[x]=dep[f]+1;
for(int i=head[x];i;i=edge[i].nxt){
int y=edge[i].to;
if(y!=f){
dfs1(y,x);
sz[x]+=sz[y];
if(sz[y]>sz[son[x]]) son[x]=y;
}
}
}

void dfs2(int x,int t){ //当前节点,重链顶端
top[x]=t;
seg[x]=++seg[0];
rev[seg[0]]=x;
if(!son[x]) return;
dfs2(son[x],t);
for(int i=head[x];i;i=edge[i].nxt){
int y=edge[i].to;
if(y==fa[x]||y==son[x]) continue;
dfs2(y,y);
}
}

void build(int k,int l,int r){
if(l==r){
sum[k]=num[rev[l]];
return;
}
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
sum[k]=(sum[k<<1]+sum[k<<1|1])%p;
}

void pushdown(int k,int l,int r){
if(!add[k]) return;
int mid=(l+r)>>1;
sum[k<<1]=(sum[k<<1]+add[k]*(mid-l+1))%p;
add[k<<1]=(add[k<<1]+add[k])%p;
sum[k<<1|1]=(sum[k<<1|1]+add[k]*(r-mid))%p;
add[k<<1|1]=(add[k<<1|1]+add[k])%p;
add[k]=0;
}

void ask_add(int k,int l,int r,int ql,int qr,ll d){
if(ql<=l&&r<=qr){
add[k]=(add[k]+d)%p;
sum[k]=(sum[k]+d*(r-l+1))%p;
return;
}
pushdown(k,l,r);
int mid=(l+r)>>1;
if(ql<=mid) ask_add(k<<1,l,mid,ql,qr,d);
if(qr>=mid+1) ask_add(k<<1|1,mid+1,r,ql,qr,d);
sum[k]=(sum[k<<1]+sum[k<<1|1])%p;
}

ll ask_sum(int k,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){
return sum[k];
}
pushdown(k,l,r);
int mid=(l+r)>>1;
ll val=0;
if(ql<=mid) val=(val+ask_sum(k<<1,l,mid,ql,qr))%p;
if(qr>=mid+1) val=(val+ask_sum(k<<1|1,mid+1,r,ql,qr))%p;
return val;
}

ll ask_path(int x,int y,ll d){
ll val=0;
int fx=top[x],fy=top[y];
while(fx!=fy){
if(dep[fx]>dep[fy]) swap(x,y),swap(fx,fy);
if(d==0) val=(val+ask_sum(1,1,seg[0],seg[fy],seg[y]))%p;
else ask_add(1,1,seg[0],seg[fy],seg[y],d);
y=fa[fy];fy=top[y];
}
if(dep[x]>dep[y]) swap(x,y);
if(d==0){//求和
val=(val+ask_sum(1,1,seg[0],seg[x],seg[y]))%p;
return val;
}
else{//给x到y所有节点都加d
ask_add(1,1,seg[0],seg[x],seg[y],d);
return 0;
}
}

int main(){
scanf("%d%d%d%lld",&n,&m,&root,&p);
for(int i=1;i<=n;++i){
scanf("%lld",&num[i]);
num[i]%=p;
}
for(int i=1;i<=n-1;i++){
int x,y;
scanf("%d%d",&x,&y);
add_edge(x,y),add_edge(y,x);
}
dfs1(root,0);
dfs2(root,root);
build(1,1,seg[0]);
for(int i=1;i<=m;i++){
int t;
scanf("%d",&t);
if(t==1){ //1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z
int x,y;ll z;
scanf("%d%d%lld",&x,&y,&z);
if(z==0) continue;
ask_path(x,y,z%p);
}
if(t==2){ //2 x y 表示求树从x到y结点最短路径上所有节点的值之和
int x,y;
scanf("%d%d",&x,&y);
printf("%lld\n",ask_path(x,y,0));
}
if(t==3){ // 3 x z 表示将以x为根节点的子树内所有节点值都加上z
int x;ll z;
scanf("%d%lld",&x,&z);
ask_add(1,1,seg[0],seg[x],seg[x]+sz[x]-1,z%p);
}
if(t==4){ //4 x 表示求以x为根节点的子树内所有节点值之和
int x;
scanf("%d",&x);
printf("%lld\n",ask_sum(1,1,seg[0],seg[x],seg[x]+sz[x]-1));
}
}
return 0;
}

图论

并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int find(int x)//找父节点
{
if(x!=farther[x])
return farther[x]=find(farther[x]);
return x;
}

int find(int x)//非递归压缩路径
{
int r=x;
while(r!=farther[r])
r=farther[r];
int i=x,j;
if(i!=r){
j=farther[i];
farther[i]=r;
i=j;
}
return r;
}

void merge(int a,int b)//合并
{
int pa=find(a);
int pb=find(b);
if(pa!=pb)
farther[pb]=pa;
}

最短路

dijkstra+堆优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;

int first[maxn],next[maxn],d[maxn],tot=0;
bool used[maxn];

struct edge{
int from,to,cost;
}es[maxn];

struct node{
int num,d;
};

bool operator <(node a,node b){
return a.d>b.d;
}

priority_queue<node> q;

void init(){
memset(first,-1,sizeof(first));
memset(d,0x3f,sizeof(d));
memset(used,0,sizeof(used));
tot=0;
}

void build(int f,int t,int d){
es[++tot]=(edge){f,t,d};
next[tot]=first[f];
first[f]=tot;
}

void dijkstra(int s){
q.push((node){s,0});
d[s]=0;
used[s]=1;
while(!q.empty()){
int now=q.top().num;
int dist=q.top().d;
q.pop();
used[now]=1;
for(int i=first[now];i!=-1;i=next[i]){
int v=es[i].to;
if(d[v]>d[now]+es[i].cost){
d[v]=d[now]+es[i].cost;
if(!used[v]) q.push((node){v,d[v]});
}
}
}
}

int main(){
init();
int t,c,ts,te;
scanf("%d%d%d%d",&t,&c,&ts,&te);
for(int i=1;i<=c;i++){
int f,t,d;
scanf("%d%d%d",&f,&t,&d);
build(f,t,d);
build(t,f,d);
}
dijkstra(ts);
cout<<d[te];
return 0;
}

tarjan缩点+拓扑排序

luoguP3387

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<bits/stdc++.h>
using namespace std;

const int maxn=10000+15;
int n,m,sum,tim,top,s;
int p[maxn],head[maxn],sd[maxn],dfn[maxn],low[maxn];//DFN(u)为节点u搜索被搜索到时的次序编号(时间戳),Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号
int stac[maxn],vis[maxn];//栈只为了表示此时是否有父子关系
int h[maxn],in[maxn],dist[maxn];
struct EDGE
{
int to;int next;int from;
}edge[maxn*10],ed[maxn*10];
void add(int x,int y)
{
edge[++sum].next=head[x];
edge[sum].from=x;
edge[sum].to=y;
head[x]=sum;
}
void tarjan(int x)
{
low[x]=dfn[x]=++tim;
stac[++top]=x;vis[x]=1;
for (int i=head[x];i;i=edge[i].next)
{
int v=edge[i].to;
if (!dfn[v]) {
tarjan(v);
low[x]=min(low[x],low[v]);
}
else if (vis[v])
{
low[x]=min(low[x],low[v]);
}
}
if (dfn[x]==low[x])
{
int y;
while (y=stac[top--])
{
sd[y]=x;
vis[y]=0;
if (x==y) break;
p[x]+=p[y];
}
}
}
int topo()
{
queue <int> q;
int tot=0;
for (int i=1;i<=n;i++)
if (sd[i]==i&&!in[i])
{
q.push(i);
dist[i]=p[i];
}
while (!q.empty())
{
int k=q.front();q.pop();
for (int i=h[k];i;i=ed[i].next)
{
int v=ed[i].to;
dist[v]=max(dist[v],dist[k]+p[v]);
in[v]--;
if (in[v]==0) q.push(v);
}
}
int ans=0;
for (int i=1;i<=n;i++)
ans=max(ans,dist[i]);
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
scanf("%d",&p[i]);
for (int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
}
for (int i=1;i<=n;i++)
if (!dfn[i]) tarjan(i);
for (int i=1;i<=m;i++)
{
int x=sd[edge[i].from],y=sd[edge[i].to];
if (x!=y)
{
ed[++s].next=h[x];
ed[s].to=y;
ed[s].from=x;
h[x]=s;
in[y]++;
}
}
printf("%d",topo());
return 0;
}

二分图

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=6808
dinic+离散化,复杂度$O(n\sqrt n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>
using namespace std;
const int maxn=400010;
const int inf=0x3f3f3f3f;
struct edge{
int to,flow,rev;
edge(int to_,int flow_,int rev_){
to=to_;
flow=flow_;
rev=rev_;
}
};

int n,lsz,rsz;
vector<edge> gpe[maxn];
int dep[maxn];
bool vis[maxn];

bool bfs(int st,int ed) {
for(int i=0;i<=lsz+rsz+1;i++) dep[i]=0;
//memset(dep, 0, sizeof dep);
queue<int> q;
q.push(st);
dep[st]=1;
while(!q.empty()) {
int u=q.front();
q.pop();
for(int i=0;i<gpe[u].size();i++) {
int v=gpe[u][i].to;
if(dep[v]||gpe[u][i].flow<=0) continue;
dep[v]=dep[u]+1;
q.push(v);
}
}
return dep[ed];
}

int dfs(int u,int flow,int ed){
if(u==ed) return flow;
int add=0;
for(int i=0;i<gpe[u].size();i++) {
int v=gpe[u][i].to;
if(dep[v]!=dep[u]+1) continue;
if(!gpe[u][i].flow) continue;
int tmpadd=dfs(v,min(gpe[u][i].flow,flow-add),ed);
gpe[u][i].flow-=tmpadd;
gpe[v][gpe[u][i].rev].flow+=tmpadd;
add+=tmpadd;
}
return add;
}

int dinic(int st,int ed){
int max_flow=0;
while(bfs(st,ed)){
max_flow+=dfs(st,inf,ed);
}
return max_flow;
}

void addedge(int u,int v,int w){
gpe[u].push_back(edge(v,w,gpe[v].size()));
gpe[v].push_back(edge(u,0,gpe[u].size()-1));
}

int p[100005],x[100005];
int aa[200005];
int l[200005],r[100005];

int main(){
int T;scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d%d",&p[i],&x[i]);
l[i]=x[i]-p[i];
r[i]=x[i]+p[i];
}
sort(l,l+n);
sort(r,r+n);
lsz=unique(l,l+n)-l;
rsz=unique(r,r+n)-r;
for(int i=0;i<=lsz+rsz+1;i++) gpe[i].clear();
for(int i=1;i<=lsz;i++) addedge(0,i,1);
for(int i=1;i<=rsz;i++) addedge(i+lsz,lsz+rsz+1,1);
for(int i=0;i<n;i++){
int pos1=lower_bound(l,l+lsz,x[i]-p[i])-l+1;
int pos2=lower_bound(r,r+rsz,x[i]+p[i])-r+1;
addedge(pos1,pos2+lsz,1);
}
printf("%d\n",dinic(0,lsz+rsz+1));
}
return 0;
}

网络流

dinic

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
#define maxn 1000010
const int inf=1e9+7;
inline int read(){
int ret=0,ff=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') ff=-ff;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
ret=ret*10+ch-'0';
ch=getchar();
}
return ret*ff;
}
struct Edge{
int u,v,w,next;
}E[maxn<<3];
int head[maxn],ecnt=0;
int dis[maxn];
int N;
void addedge(int u,int v,int w){
E[++ecnt].u=u;
E[ecnt].v=v;
E[ecnt].w=w;
E[ecnt].next=head[u];
head[u]=ecnt;
}
void Addedge(int u,int v,int w){
addedge(u,v,w);
addedge(v,u,w);
}
bool bfs(){
queue<int> q;
q.push(1);
dis[1]=1;
for(int i=2;i<=N;++i){
dis[i]=inf;
}
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=head[x];i;i=E[i].next){
int v=E[i].v;
if(!E[i].w||dis[v]!=inf) continue;
dis[v]=dis[x]+1;
q.push(v);
}
}
return dis[N]!=inf;
}
int dfs(int x,int nar){
if(x==N) return nar;
int used=0;
for(int i=head[x];i;i=E[i].next){
int v=E[i].v;
if(dis[v]!=dis[x]+1||!E[i].w)continue;
int tmp=nar-used;
int flow=dfs(v,min(tmp,E[i].w));
E[i].w-=flow;
E[i+1].w+=flow;
used+=flow;
if(used==nar) return nar;
}
if(!used) dis[x]=-1;
return used;
}
void dinic(){
int ans=0;
while(bfs()){
// for(int i=1;i<=N;++i){
// printf("dis[%d]=%d\n",i,dis[i]);
// }
ans+=dfs(1,inf);
// printf("ans=%d\n",ans);
}
printf("%d\n",ans);
}
int main(){
// freopen("bzoj1001.in","r",stdin);
// freopen("bzoj1001.out","w",stdout);
int n=read(),m=read();
for(int i=1;i<=n;++i){
for(int j=1;j<m;++j){
int w=read();
Addedge((i-1)*m+j,(i-1)*m+j+1,w);
}
}
for(int i=1;i<n;++i){
for(int j=1;j<=m;++j){
int w=read();
Addedge((i-1)*m+j,i*m+j,w);
}
}
for(int i=1;i<n;++i){
for(int j=1;j<m;++j){
int w=read();
Addedge((i-1)*m+j,i*m+j+1,w);
}
}
N=n*m;
dinic();
return 0;
}

数论

威尔逊定理

$(p−1)!≡−1(mod p)$当且仅当$p$为素数时成立;

扩展欧拉函数

令$m=2^{2^{2^{…}}}$,即求$m%p$。
考虑到m和p不一定互质,易想到扩展欧拉函数:

因此,令$f(p)=m\%p$,则有

于是可以递归求解,复杂度约为$O(\sqrt p * \log p)$

gcd

1
2
3
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}

exgcd

1
2
3
4
5
6
7
8
9
10
ll exgcd(ll l,ll r,ll &x,ll &y)
{
if(r==0){x=1;y=0;return l;}
else
{
ll d=exgcd(r,l%r,y,x);
y-=l/r*x;
return d;
}
}

快速幂取模

1
2
3
4
5
6
7
8
9
int qpow(int a,int b,int mod){
int ans=1;
while(b){
if(b&1) ans*=a,ans%=mod;
a*=a,a%=mod;
b>>=1;
}
return ans%mod;
}

逆元

1
2
3
int inv(int a) {  
return qpow(a, mod - 2);
}

线性求组合数

1
2
3
4
5
6
inline void init(ll n){
Fact[1]=1;Fact[0]=1;
for(ll i=2;i<=n;++i) Fact[i]=Fact[i-1]*i%mod;
INV[n]=qpow(Fact[n],mod-2);
for(ll i=n-1;i>=0;--i) INV[i]=INV[i+1]*(i+1)%mod;
}

判断素数

暴力判断 复杂度$O(\sqrt n)$

1
2
3
4
5
6
int Prime(int x){
for(int i=2;i*i<=x;i++){
if(x%i==0) return 0;
}
return 1;
}

欧拉筛 复杂度$O(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
bool isPrime[n];
vector<int> prime;

int Prime(int n){
for(int i=2;i<=n;i++){
if(isPrime[i]) prime.push_back(i);
for(int j=0;j<prime.size();j++){
if(i*prime[j]>n) break;
isPrime[i*prime[j]]=false;
if(i%prime[j]==0) break;
}
}
}

欧拉函数

暴力求 复杂度$O(\sqrt(n))$

1
2
3
4
5
6
7
8
9
int phi(int x){
int ret=x;
for(int i=2;i*i<=x;i++){
if(x%i==0) ret-=ret/i;
while(x%i==0) x/=i;
}
if(x>1) ret-=ret/x;
return ret;
}

线性筛 复杂度$O(n)$
1
2
3
4
5
6
7
8
void Euler(){     
phi[1]=1;
for(int i=2;i<MAXN;i++) phi[i]=i;
for(int i=2;i<MAXN;i++){
if(phi[i]==i)
for(int j=i;j<MAXN;j+=i) phi[j]-=phi[j]/i;
}
}

min25筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<cstdio>  
#include<cmath>
using namespace std;
#define LL long long
const int N = 5e6 + 2;
bool np[N];
int prime[N], pi[N];
int getprime()
{
int cnt = 0;
np[0] = np[1] = true;
pi[0] = pi[1] = 0;
for(int i = 2; i < N; ++i){
if(!np[i]) prime[++cnt] = i;
pi[i] = cnt;
for(int j = 1; j <= cnt && i * prime[j] < N; ++j){
np[i * prime[j]] = true;
if(i % prime[j] == 0) break;
}
}
return cnt;
}
const int M = 7;
const int PM = 2 * 3 * 5 * 7 * 11 * 13 * 17;
int phi[PM + 1][M + 1], sz[M + 1];
void init(){
getprime();
sz[0] = 1;
for(int i = 0; i <= PM; ++i) phi[i][0] = i;
for(int i = 1; i <= M; ++i){
sz[i] = prime[i] * sz[i - 1];
for(int j = 1; j <= PM; ++j) phi[j][i] = phi[j][i - 1] - phi[j / prime[i]][i - 1];
}
}
int sqrt2(LL x){
LL r = (LL)sqrt(x - 0.1);
while(r * r <= x) ++r;
return int(r - 1);
}
int sqrt3(LL x){
LL r = (LL)cbrt(x - 0.1);
while(r * r * r <= x) ++r;
return int(r - 1);
}
LL getphi(LL x, int s){
if(s == 0) return x;
if(s <= M) return phi[x % sz[s]][s] + (x / sz[s]) * phi[sz[s]][s];
if(x <= prime[s]*prime[s]) return pi[x] - s + 1;
if(x <= prime[s]*prime[s]*prime[s] && x < N){
int s2x = pi[sqrt2(x)];
LL ans = pi[x] - (s2x + s - 2) * (s2x - s + 1) / 2;
for(int i = s + 1; i <= s2x; ++i) ans += pi[x / prime[i]];
return ans;
}
return getphi(x, s - 1) - getphi(x / prime[s], s - 1);
}
LL getpi(LL x){
if(x < N) return pi[x];
LL ans = getphi(x, pi[sqrt3(x)]) + pi[sqrt3(x)] - 1;
for(int i = pi[sqrt3(x)] + 1, ed = pi[sqrt2(x)]; i <= ed; ++i) ans -= getpi(x / prime[i]) - i + 1;
return ans;
}
LL lehmer_pi(LL x){
if(x < N) return pi[x];
int a = (int)lehmer_pi(sqrt2(sqrt2(x)));
int b = (int)lehmer_pi(sqrt2(x));
int c = (int)lehmer_pi(sqrt3(x));
LL sum = getphi(x, a) +(LL)(b + a - 2) * (b - a + 1) / 2;
for (int i = a + 1;i<= b;i++){
LL w = x / prime[i];
sum -= lehmer_pi(w);
if (i > c) continue;
LL lim = lehmer_pi(sqrt2(w));
for (int j = i; j <= lim; j++) sum -= lehmer_pi(w / prime[j]) - (j - 1);
}
return sum;
}
int main(){
init();
LL n;
while(~scanf("%lld",&n)){
printf("%lld\n",lehmer_pi(n));
}
return 0;
}

中国剩余定理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <iostream>
#include <cstdio>
#include<cstring>
#include<string>

using namespace std;
typedef long long LL;

const int maxn = 100000 + 10;
LL a[maxn],m[maxn],n;
LL ex_gcd(LL a,LL b,LL &x,LL &y){//拓展欧几里得
if(b==0){
x = 1;
y = 0;
return a;
}
LL ans = ex_gcd(b,a%b,x,y);
LL temp = x;
x = y;
y = temp - a/b*y;
return ans;
}
LL inv(LL a,LL b){//求逆元
LL x,y;
LL ans = ex_gcd(a,b,x,y);
if(ans!=1)
return -1;
if(x<0)
x=(x%b+b)%b;
return x;
}
LL China(){//中国剩余定理
LL M=1;
for(int i=0;i<n;i++){
M*=m[i];
}
LL sum=0;
for(int i=0;i<n;i++){
LL res=M/m[i];
sum=(sum+a[i]*res*inv(res,m[i]))%M;
}
return sum;
}
int main()
{
while(scanf("%lld",&n)!=EOF){
for(int i=0;i<n;i++){
scanf("%lld%lld",&m[i],&a[i]);
}
LL ans=China();
printf("%lld\n",ans);
}
return 0;
}



//不互素版

#include<iostream>
#include<stdio.h>
using namespace std;
long long exgcd(long long a,long long b,long long &x,long long &y){
if(b==0){
x=1,y=0;
return a;
}
long long q=exgcd(b,a%b,y,x);
y-=a/b*x;
return q;
}
int main(){
long long a1,c1,a2,c2,x,y,t;
long long n;
while(cin>>n){
long long flag=1;
cin>>a1>>c1;
for(long long i=1;i<n;i++){
cin>>a2>>c2;
long long q=exgcd(a1,a2,x,y);
if((c2-c1)%q!=0){
flag=0;
}
t=a2/q;
x=((x*(c2-c1)/q)%t+t)%t;
//cout<<x;
c1=c1+a1*x;
a1=a1*(a2/q);
}
if(flag==0){
cout<<"-1"<<endl;
continue;
}
cout<<c1<<endl;
}
return 0;
}


线性基

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55


struct L_B{
int d[61],p[61];
int cnt;
L_B(){
memset(d,0,sizeof(d));
memset(p,0,sizeof(p));
cnt=0;
}
bool insert(int val){
for(int i=60;i>=0;i--)
if(val&(1LL<<i)){
if(!d[i]){
d[i]=val;
break;
}
val^=d[i];
}
return val>0;
}
int query_max(){
int ret=0;
for (int i=60;i>=0;i--)
if((ret^d[i])>ret) ret^=d[i];
return ret;
}
int query_min(){
for(int i=0;i<=60;i++)
if(d[i]) return d[i];
return 0;
}
void rebuild(){
for(int i=60;i>=0;i--)
for(int j=i-1;j>=0;j--)
if(d[i]&(1LL<<j)) d[i]^=d[j];
for(int i=0;i<=60;i++)
if(d[i]) p[cnt++]=d[i];
}
int kthquery(int k){
int ret=0;
if(k>=(1LL<<cnt)) return -1;
for(int i=60;i>=0;i--)
if(k&(1LL<<i)) ret^=p[i];
return ret;
}
}

L_B merge(const L_B &n1,const L_B &n2){
L_B ret=n1;
for(int i=60;i>=0;i--)
if(n2.d[i]) ret.insert(n1.d[i]);
return ret;
}

计算几何

极角排序

1
2
3
4
5
6
7
8
9
10
11
12
13
struct node{
int x,y,id;
long double deg;
friend bool operator < (const node &a,const node &b){
return a.deg<b.deg;
}
}p[maxn];

long double atann(int y,int x){
long double t=atan2(y,x);
if(t<0) t+=pi*2;
return t;
}

圆的反演

hdu6097

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const double pi = acos(-1);
const double zero = 1e-14;
int i, j, k, n, m, s, t;
double r1, r2, R, x1, x2, ans, r;
struct node {
double x, y;
} p;
struct circle {
node o;
double r;
} now;
double sqr(const double &x) {
return x * x;
}
int sign(const double &x) {
if (fabs(x) < zero) {
return 0;
} else if (x > 0) {
return 1;
} else {
return -1;
}
}
double dist(const node &x, const node &y) {
return sqrt(sqr(x.x - y.x) + sqr(x.y - y.y));
}
circle inversion(const node &p, const double &r) {
circle res;
res.r = r / (sqr(dist(p, (node){0, 0})) - sqr(r)) * sqr(R);
res.o = (node){0, 0};
return res;
}
int main() {
R = 20.0;
int T;
scanf("%d", &T);
while (T--) {
scanf("%lf %lf", &r1, &r2);
if (r1 < r2) {
swap(r1, r2);
}
scanf("%d", &n);
x1 = sqr(R) / (2.0 * r1);
x2 = sqr(R) / (2.0 * r2);
r = (x2 - x1) / 2.0;
p = (node){(x1 + x2) / 2.0 , 0};
now = inversion(p, r);
ans = pi * sqr(now.r);
for (int i = 2; i <= n; i++) {
if ((i & 1) == 0) {
p.y += 2.0 * r;
now = inversion(p, r);
}
ans += pi * sqr(now.r);
if (sign(pi * sqr(now.r)) != 1) {
break;
}
}
printf("%.5f\n", ans);
}
return 0;
}

字符串

KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int next[1000010];
char text[1000010],s[1000010];
int main(){
scanf("%s%s",text+1,s+1);
int len1=strlen(text+1);
int len2=strlen(s+1);
int k=0;
for(int i=1;i<len2;++i){
while(k>0&&s[i+1]!=s[k+1]) k=next[k];
if(s[i+1]==s[k+1]) k++;
next[i+1]=k;
}
k=1;
for(int i=1;i<len1;++i){
while(k>0&&text[i+1]!=s[k+1]) k=next[k];
if(text[i+1]==s[k+1]) ++k;
// printf("k=%d\n",k);
if(k==len2) printf("%d\n",i-len2+2);
}
for(int i=1;i<=len2;++i){
printf("%d ",next[i]);
}
}

扩展kmp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;

int Next[1000005];
char x[1000005],y[1000005];
//Next[i]:x[i……m-1]与x[0……m-1]的最长公共前缀
//extend[i]:y[i……n-1]与x[0……m-1]的最长公共前缀
void pre_EKMP(char x[],int m,int Next[]){
next[0]=m;
int j=0;
while(j+1<m&&x[j]==x[j+1]) j++;
Next[1]=j;
int k=1;
for(int i=2;i<m;i++){
int p=Next[k]+k-1;
int L=Next[i-k];
if(i+L<p+1) Next[i]=L;
else{
j=max(0,p-i+1);
while(i+j<m&&x[i+j]==x[j])j++;
Next[i]=j;
k=i;
}
}
}
void EKMP(char x[],int m,char y[],int n,int Next[],int extend[]){
pre_EKMP(x,m,next);
int j=0;
while(j<n&&j<m&&x[j]==y[j]) j++;
extend[0]=j;
int k=0;
for(int i=1;i<n;i++){
int p=extend[k]+k-1;
int L=Next[i-k];
if(i+L<p+1) extend[i]=L;
else{
j=max(0,p-i+1);
while(i+j<n&&j<m&&y[i+j]==x[j]) j++;
extend[i]=j;
k=i;
}
}
}

马拉车

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 21000010
char str[maxn],s[maxn];
int p[maxn];
int main(){
scanf("%s",str+1);
int n=strlen(str+1);
s[0]='#',s[1]='$';
for(int i=1;i<=n;++i) s[i<<1]=str[i],s[i<<1|1]='$';
n=n<<1|1;
int id=0,mx=0,ans=0;
for(int i=1;i<=n;++i){
int j=(id<<1)-i;
p[i]=i<mx?min(p[j],mx-i):1;
while(s[i+p[i]]==s[i-p[i]]) ++p[i];
if(i+p[i]>mx)mx=i+p[i],id=i;
ans=max(ans,p[i]);
}
printf("%d",ans-1);
return 0;
}

trie树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;
int root;
int tot=1;
int trie[400500][30];
int cnt[400500];
void init()//最后清空,节省时间
{
memset(trie,0,sizeof(trie));
memset(cnt,0,sizeof(cnt));
tot=1;//RE有可能是这里的问题
}
void build_trie(char *s)
{
root=0;
for(int i=0;s[i];i++)
{
int id=s[i]-'a';
if(!trie[root][id]) trie[root][id]=++tot;
root=trie[root][id];
cnt[root]++; //前缀匹配
}
//cnt[root]++; //词频统计
}
int query(char *s)
{
root=0;
for(int i=0;s[i];i++)
{
int id=s[i]-'a';
if(!trie[root][id]) return false;
root=trie[root][id];
}
return cnt[root];
}
int main()
{
char s[105];
char t[105];
int ans=0;
init();
while(gets(s)){
int x=strlen(s);
if(x==0) break;
build_trie(s);
}
while(gets(t)){
int flag=query(t);
printf("%d\n",flag);
}
return 0;
}

01trie树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
//01trie树处理异或最值问题
//CF 1286A
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll tol;
const ll maxn=100005;
ll val[33*maxn];
ll ch[33*maxn][2];

void init(){
tol=1;
ch[0][0]=ch[0][1]=0;
}

void insert(ll x){
ll u=0;
for(ll i=31;i>=0;i--){
ll v=(x>>i)&1ll;
if(!ch[u][v]){
ch[tol][0]=ch[tol][1]=0;
val[tol]=0;
ch[u][v]=tol++;
}
u=ch[u][v];
}
val[u]=x;
}

ll ans;
void dfs(ll x,ll qwq,ll k){
if(ch[x][0]==0&&ch[x][1]==0){
ans=min(ans,qwq);
//cout<<qwq<<endl;
return;
}
if(ch[x][0]==0) dfs(ch[x][1],qwq,k-1);
else if(ch[x][1]==0) dfs(ch[x][0],qwq,k-1);
else{
//cout<<x<<endl;
dfs(ch[x][0],qwq+(1<<k),k-1);
dfs(ch[x][1],qwq+(1<<k),k-1);
}
}

int main(){
init();
ans=10000000009;
ll n;scanf("%lld",&n);
for(ll i=0;i<n;i++){
ll num;scanf("%lld",&num);
insert(num);
}
//cout<<tol<<endl;
//for(int i=0;i<=tol;i++) cout<<ch[i][0]<<" "<<ch[i][1]<<endl;
dfs(0,0,31);
cout<<ans<<endl;
}

ac自动机

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
inline int read(){
int ret=0,ff=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') ff=-ff;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
ret=ret*10+ch-'0';
ch=getchar();
}
return ret*ff;
}
#define maxn 1000010
char str1[210][210];
struct AC{
int trie[400010][30];
int val[maxn];
int fail[maxn];
int siz;
int cnt[220];
void clr(){
for(int i=0;i<=siz+1;++i) for(int j=0;j<=28;++j) trie[i][j]=0;
memset(val,0,sizeof(val));
memset(fail,0,sizeof(fail));
memset(str1,0,sizeof(str1));
memset(cnt,0,sizeof(cnt));
siz=0;
}
void ins(char *str,int len,int x){
int now=0;
for(int i=1;i<=len;++i){
int ch=str[i]-'a';
if(trie[now][ch]==0) trie[now][ch]=++siz;
now=trie[now][ch];
}
val[now]=x;
}
void getfail(){
queue<int> q;
for(int i=0;i<=25;++i) if(trie[0][i]) q.push(trie[0][i]);
while(q.empty()==0){
int now=q.front();q.pop();
for(int i=0;i<=25;++i){
int v=trie[now][i];
if(v==0){
trie[now][i]=trie[fail[now]][i];
continue;
}
fail[v]=trie[fail[now]][i];
q.push(v);
}
}

}
void query(char *str,int len,int n){
int u=0;
for(int i=1;i<=len;++i){
int v=u=trie[u][str[i]-'a'];
while(v){
if(val[v]) ++cnt[val[v]];
v=fail[v];
}
}
int maxx=0;
for(int i=1;i<=n;++i) maxx=max(maxx,cnt[i]);
printf("%d\n",maxx);
for(int i=1;i<=n;++i){
if(cnt[i]==maxx) printf("%s\n",str1[i]+1);
}
}
}ac;
char str[maxn];
int main(){
int n;
while((n=read())){
ac.clr();
memset(str,0,sizeof(str));
for(int i=1;i<=n;++i){
scanf("%s",str1[i]+1);
int len=strlen(str1[i]+1);
ac.ins(str1[i],len,i);
}
ac.getfail();
scanf("%s",str+1);
int len=strlen(str+1);
ac.query(str,len,n);
}
return 0;
}