一些常用算法及数据结构模板
【模板】堆
题目描述
如题，初始小根堆为空，我们需要支持以下3种操作：
操作1： 1 x 表示将x插入到堆中
操作2： 2 输出该小根堆内的最小数
操作3： 3 删除该小根堆内的最小数
1 | |
2 | using namespace std; |
3 | int h[10000005]; |
4 | int s=0,t,b,top; |
5 | void c(int x){ |
6 | s++; |
7 | h[s]=x; |
8 | t=s; |
9 | while(t>1){ |
10 | if(h[t/2]>h[t]){ |
11 | b=h[t/2];h[t/2]=h[t];h[t]=b; |
12 | } |
13 | else break; |
14 | t=t/2; |
15 | } |
16 | } |
17 | void ss(){ |
18 | cout<<h[1]<<endl; |
19 | } |
20 | void pop(){ |
21 | if(s>0){ |
22 | h[1]=h[s]; |
23 | int root=1; |
24 | s--; |
25 | while(root*2<=s){ |
26 | if(root*2+1<=s&&h[root*2]>h[root*2+1]){ |
27 | if(h[root]>h[root*2+1]){ |
28 | t=h[root];h[root]=h[root*2+1];h[root*2+1]=t; |
29 | root=root*2+1; |
30 | } |
31 | else break; |
32 | } |
33 | else if(h[root*2]<=h[root*2+1]){ |
34 | if(h[root]>h[root*2]){ |
35 | t=h[root];h[root]=h[root*2];h[root*2]=t; |
36 | root=root*2; |
37 | } |
38 | else break; |
39 | } |
40 | else break; |
41 | } |
42 | } |
43 | } |
44 | int main(){ |
45 | int N,x,y; |
46 | cin>>N; |
47 | for(int i=1;i<=N;i++){ |
48 | cin>>x; |
49 | if(x==1){ |
50 | cin>>y; |
51 | c(y); |
52 | } |
53 | else{ |
54 | if(x==2) ss(); |
55 | if(x==3) pop(); |
56 | } |
57 | } |
58 | return 0; |
59 | } |
【模板】负环
题目描述
暴力枚举/SPFA/Bellman-ford/奇怪的贪心/超神搜索
寻找一个从顶点1所能到达的负环，负环定义为：一个边权之和为负的环。
输入格式
第一行一个正整数T表示数据组数，对于每组数据：
第一行两个正整数N M，表示图有N个顶点，M条边
接下来M行，每行三个整数a b w，表示a->b有一条权值为w的边（若w<0则为单向，否则双向）
输出格式
共T行。对于每组数据，存在负环则输出一行”YE5”(不含引号)，否则输出一行”N0”(不含引号)。
1 | |
2 | |
3 | |
4 | |
5 | using namespace std; |
6 | int read(){ |
7 | int re=0;char c=getchar();bool flag=0; |
8 | while((c<'0'||c>'9')&&c!='-') c=getchar(); |
9 | if(c=='-') flag=1,c=getchar(); |
10 | while(c>='0'&&c<='9'){ |
11 | re=re*10+c-'0'; |
12 | c=getchar(); |
13 | } |
14 | if(flag) re=-re; |
15 | return re; |
16 | } |
17 | struct TU{ |
18 | int to,nxt,val; |
19 | }t[6005]; |
20 | int last[2500],cnt; |
21 | int dis[2500],rq[2500]; |
22 | void build(int u,int v,int w){ |
23 | t[++cnt].to=v; |
24 | t[cnt].val=w; |
25 | t[cnt].nxt=last[u]; |
26 | last[u]=cnt; |
27 | } |
28 | int n; |
29 | bool vis[2500]; |
30 | bool spfa(){ |
31 | queue<int> q; |
32 | memset(dis,63/3,sizeof(dis)); |
33 | memset(vis,0,sizeof(vis)); |
34 | memset(rq,0,sizeof(rq)); |
35 | q.push(1);vis[1]=1;dis[1]=0;rq[1]=1; |
36 | while(!q.empty()){ |
37 | int u=q.front();q.pop();vis[u]=0; |
38 | int e=last[u]; |
39 | while(e){ |
40 | int v=t[e].to; |
41 | if(dis[v]>dis[u]+t[e].val){ |
42 | dis[v]=dis[u]+t[e].val; |
43 | if(!vis[v]){ |
44 | q.push(v); |
45 | vis[v]=1; |
46 | rq[v]++; |
47 | if(rq[v]>n){ |
48 | return 1; |
49 | } |
50 | } |
51 | } |
52 | e=t[e].nxt; |
53 | } |
54 | } |
55 | return 0; |
56 | } |
57 | int main(){ |
58 | int i,j,k,m,T,u,v,w;bool flag=0; |
59 | T=read(); |
60 | while(T--){ |
61 | n=read();m=read(); |
62 | memset(last,0,sizeof(last));cnt=0; |
63 | for(i=1;i<=m;i++){ |
64 | u=read();v=read();w=read(); |
65 | if(w<0) build(u,v,w); |
66 | else build(u,v,w),build(v,u,w); |
67 | } |
68 | |
69 | if(spfa()) printf("YE5\n"); |
70 | else printf("N0\n"); |
71 | } |
72 | return 0; |
73 | } |
【模板】ST表
题目描述
给定一个长度为 N 的数列，和 M 次询问，求出每一次询问的区间内数字的最大值。
输入格式
第一行包含两个整数 N, M，分别表示数列的长度和询问的个数。
第二行包含 N 个整数（记为 $a_i$），依次表示数列的第 i 项。
接下来 MM行，每行包含两个整数$ l_i, r_i$，表示查询的区间为 $[ l_i, r_i]$
输出格式
输出包含 $M$行，每行一个整数，依次表示每一次询问的结果。
1 | |
2 | |
3 | using namespace std; |
4 | int a[105000],f[105000][22],lg[105000]; |
5 | int max(int a,int b){ |
6 | return a>b?a:b; |
7 | } |
8 | int read(){ |
9 | int re=0;char c=getchar(); |
10 | while(c<'0'||c>'9') c=getchar(); |
11 | while(c>='0'&&c<='9'){ |
12 | re=re*10+c-'0'; |
13 | c=getchar(); |
14 | } |
15 | return re; |
16 | } |
17 | int main(){ |
18 | int i,j,k,n,m,l,r; |
19 | n=read();m=read(); |
20 | for(i=1;i<=n;i++){ |
21 | a[i]=read(); |
22 | f[i][0]=a[i]; |
23 | } |
24 | lg[1]=0; |
25 | for(i=2;i<=n;i++) lg[i]=lg[i>>1]+1; |
26 | for(j=1;j<=21;j++){ |
27 | for(i=1;i+(1<<j)-1<=n;i++){ |
28 | f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]); |
29 | } |
30 | } |
31 | for(i=1;i<=m;i++){ |
32 | l=read();r=read(); |
33 | k=lg[r-l+1]; |
34 | printf("%d\n",max(f[l][k],f[r-(1<<k)+1][k])); |
35 | } |
36 | return 0; |
37 | } |
【模板】缩点
题目描述
给定一个 $n$ 个点 $m$ 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。
允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。
输入格式
第一行两个正整数 $n,m$
第二行 $n$ 个整数，依次代表点权
第三至 $m+2$ 行，每行两个整数 $u,v$，表示一条 $u\rightarrow v$ 的有向边。
输出格式
共一行，最大的点权之和。
1 | |
2 | |
3 | |
4 | using namespace std; |
5 | int pt[10050]; |
6 | struct TU{ |
7 | int frm,to,nxt; |
8 | }t[100500],wt[100500]; |
9 | stack<int> st; |
10 | int last[10050],cnt,lst[10050],ctt;int dfn[10050],low[10050],dpt=0; |
11 | int qfl=0,pb[10050],lw[10050],f[10050],rd[10050];bool vis[10050]; |
12 | void build(int u,int v){ |
13 | t[++cnt].to=v; |
14 | t[cnt].frm=u; |
15 | t[cnt].nxt=last[u]; |
16 | last[u]=cnt; |
17 | } |
18 | void bild(int u,int v){ |
19 | wt[++ctt].to=v; |
20 | wt[ctt].frm=u; |
21 | wt[ctt].nxt=lst[u]; |
22 | lst[u]=ctt; |
23 | } |
24 | void tarjan(int x){ |
25 | dfn[x]=low[x]=++dpt;st.push(x); |
26 | int e=last[x]; |
27 | while(e){ |
28 | int v=t[e].to; |
29 | if(!dfn[v]){ |
30 | tarjan(v); |
31 | if(low[v]<low[x]) low[x]=low[v]; |
32 | } |
33 | else if(!pb[v]){ |
34 | if(low[x]>low[v]) low[x]=low[v]; |
35 | } |
36 | e=t[e].nxt; |
37 | } |
38 | if(dfn[x]==low[x]){ |
39 | qfl++;int j=-1; |
40 | do{ |
41 | j=st.top(); |
42 | pb[j]=qfl; |
43 | lw[qfl]+=pt[j]; |
44 | st.pop(); |
45 | }while(j!=x); |
46 | } |
47 | } |
48 | int dfs(int x){ |
49 | if(f[x]!=0) return f[x]; |
50 | int e=lst[x];int nw=0; |
51 | while(e){ |
52 | int v=wt[e].to; |
53 | nw=max(nw,dfs(v)); |
54 | e=wt[e].nxt; |
55 | } |
56 | f[x]=nw+lw[x]; |
57 | return f[x]; |
58 | } |
59 | int main(){ |
60 | int i,j,k,m,n,u,v;int ans=0; |
61 | scanf("%d%d",&n,&m); |
62 | for(i=1;i<=n;i++) scanf("%d",&pt[i]); |
63 | for(i=1;i<=m;i++){ |
64 | scanf("%d%d",&u,&v); |
65 | build(u,v); |
66 | } |
67 | for(i=1;i<=n;i++){ |
68 | if(!dfn[i]) tarjan(i); |
69 | } |
70 | for(i=1;i<=cnt;i++){ |
71 | u=t[i].frm,v=t[i].to; |
72 | if(pb[u]!=pb[v]){ |
73 | bild(pb[u],pb[v]); |
74 | rd[pb[v]]++; |
75 | } |
76 | } |
77 | for(i=1;i<=qfl;i++){ |
78 | if(rd[i]==0){ |
79 | ans=max(ans,dfs(i)); |
80 | } |
81 | } |
82 | cout<<ans; |
83 | return 0; |
84 | } |
【模板】乘法逆元
题目描述
给定n,p求1~n中所有整数在模p意义下的乘法逆元。
输入格式
一行n,p
输出格式
n行,第i行表示i在模p意义下的逆元。
1 | |
2 | |
3 | using namespace std; |
4 | long long p; |
5 | //long long pow(long long a,long long k){ |
6 | // long long base=a,ans=1; |
7 | // while(k){ |
8 | // if(k&1){ |
9 | // ans=(ans*base)%p; |
10 | // } |
11 | // base=(base*base)%p; |
12 | // k>>=1; |
13 | // } |
14 | // return ans; |
15 | //} |
16 | long long f[3000050]; |
17 | int main(){ |
18 | int i,j;long long k,m,n,u; |
19 | cin>>n>>p; |
20 | f[1]=1; |
21 | printf("1\n"); |
22 | for(i=2;i<=n;i++){ |
23 | f[i]=-(p/i)*f[p%i]; |
24 | f[i]=(f[i]%p+p)%p; |
25 | printf("%lld\n",f[i]); |
26 | } |
27 | return 0; |
28 | } |
【模板】线段树 1
题目描述
如题，已知一个数列，你需要进行下面两种操作：
1.将某区间每一个数加上x
2.求出某区间每一个数的和
输入格式
第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。
第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。
接下来M行每行包含3或4个整数，表示一个操作，具体如下：
操作1： 格式：1 x y k 含义：将区间[x,y]内每个数加上k
操作2： 格式：2 x y 含义：输出区间[x,y]内每个数的和
输出格式
输出包含若干行整数，即为所有操作2的结果。
1 | |
2 | |
3 | |
4 | |
5 | |
6 | const int N=100000; |
7 | long long a[100500]; |
8 | using namespace std; |
9 | struct segtree{ |
10 | long long val[(N<<2)+50],mark[(N<<2)+50]; |
11 | void pushup(int o){ |
12 | val[o]=val[ls]+val[rs]; |
13 | } |
14 | void build(int o,int l,int r){ |
15 | mark[o]=0; |
16 | if(l==r){ |
17 | val[o]=a[l]; |
18 | return; |
19 | } |
20 | int mid=(l+r)>>1; |
21 | build(ls,l,mid);build(rs,mid+1,r); |
22 | pushup(o); |
23 | } |
24 | void pushdown(int o,int l,int r){ |
25 | if(mark[o]!=0){ |
26 | mark[ls]+=mark[o]; |
27 | mark[rs]+=mark[o]; |
28 | int mid=(l+r)>>1; |
29 | val[ls]+=(long long)mark[o]*(mid-l+1); |
30 | val[rs]+=(long long)mark[o]*(r-mid); |
31 | mark[o]=0; |
32 | } |
33 | } |
34 | void add(int o,int l,int r,int ql,int qr,long long v){ |
35 | if(ql<=l&&r<=qr){ |
36 | mark[o]+=v; |
37 | val[o]+=(long long)v*(r-l+1); |
38 | return; |
39 | } |
40 | int mid=(l+r)>>1; |
41 | pushdown(o,l,r); |
42 | if(ql<=mid) add(ls,l,mid,ql,qr,v); |
43 | if(qr>mid) add(rs,mid+1,r,ql,qr,v); |
44 | pushup(o); |
45 | } |
46 | long long checksum(int o,int l,int r,int ql,int qr){ |
47 | long long ans=0; |
48 | if(ql<=l&&r<=qr){ |
49 | return val[o]; |
50 | } |
51 | int mid=(l+r)>>1; |
52 | pushdown(o,l,r); |
53 | if(ql<=mid) ans+=checksum(ls,l,mid,ql,qr); |
54 | if(qr>mid) ans+=checksum(rs,mid+1,r,ql,qr); |
55 | return ans; |
56 | } |
57 | }st; |
58 | int main(){ |
59 | int n,m,i,j,k,d,b,x;long long c; |
60 | scanf("%d%d",&n,&m); |
61 | for(i=1;i<=n;i++){ |
62 | scanf("%lld",&a[i]); |
63 | } |
64 | st.build(1,1,n); |
65 | for(i=1;i<=m;i++){ |
66 | scanf("%d",&x); |
67 | if(x==1){ |
68 | scanf("%d%d%lld",&d,&b,&c); |
69 | st.add(1,1,n,d,b,c); |
70 | } |
71 | else if(x==2){ |
72 | scanf("%d%d",&d,&b); |
73 | cout<<st.checksum(1,1,n,d,b)<<endl; |
74 | } |
75 | } |
76 | return 0; |
77 | } |
【模板】线段树 2
题目描述
如题，已知一个数列，你需要进行下面三种操作：
- 将某区间每一个数乘上 $x$
- 将某区间每一个数加上 $x$
- 求出某区间每一个数的和
输入格式
第一行包含三个整数 $n,m,p$，分别表示该数列数字的个数、操作的总个数和模数。
第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 ii 项的初始值。
接下来 $m$ 行每行包含若干个整数，表示一个操作，具体如下：
操作 1： 格式：1 x y k 含义：将区间$[x,y]$ 内每个数乘上 $k$
操作 2： 格式：2 x y k 含义：将区间$[x,y]$内每个数加上 kk
操作 3： 格式：3 x y 含义：输出区间$[x,y]$ 内每个数的和对 $p$ 取模所得的结果
输出格式
输出包含若干行整数，即为所有操作 $3$ 的结果。
1 | |
2 | |
3 | using namespace std; |
4 | |
5 | |
6 | long long p; |
7 | long long read(){ |
8 | long long res=0;char c=getchar();bool flag=0; |
9 | while((c<'0'||c>'9')&&c!='-') c=getchar(); |
10 | if(c=='-'){ |
11 | flag=1; |
12 | c=getchar(); |
13 | } |
14 | while(c>='0'&&c<='9'){ |
15 | res=res*10+int(c)-48; |
16 | c=getchar(); |
17 | } |
18 | if(flag) res=-res; |
19 | return res; |
20 | } |
21 | struct segtree{ |
22 | long long add,mul,val; |
23 | }ct[405000]; |
24 | long long a[105000]; |
25 | void build(int o,int l,int r){ |
26 | ct[o].mul=1; |
27 | ct[o].add=0; |
28 | if(l==r) ct[o].val=a[l]%p; |
29 | else{ |
30 | int mid=(l+r)/2; |
31 | build(ls,l,mid); |
32 | build(rs,mid+1,r); |
33 | ct[o].val=(ct[ls].val+ct[rs].val)%p; |
34 | } |
35 | return; |
36 | } |
37 | void pushdown(int o,int l,int r){ |
38 | int mid=(l+r)>>1; |
39 | ct[ls].val=(((ct[ls].val*ct[o].mul)%p)+((mid+1-l)*ct[o].add)%p)%p; |
40 | ct[rs].val=(((ct[rs].val*ct[o].mul)%p)+((r-mid)*ct[o].add)%p)%p; |
41 | ct[ls].mul=(ct[ls].mul*ct[o].mul)%p; |
42 | ct[rs].mul=(ct[rs].mul*ct[o].mul)%p; |
43 | ct[ls].add=(((ct[ls].add*ct[o].mul)%p)+ct[o].add)%p; |
44 | ct[rs].add=(((ct[rs].add*ct[o].mul)%p)+ct[o].add)%p; |
45 | ct[o].mul=1; |
46 | ct[o].add=0; |
47 | return; |
48 | } |
49 | void ltagm(int o,int l,int r,int ql,int qr,long long v){ |
50 | if(ql<=l&&qr>=r){ |
51 | ct[o].mul=(ct[o].mul*v)%p; |
52 | ct[o].val=(ct[o].val*v)%p; |
53 | ct[o].add=(ct[o].add*v)%p; |
54 | return; |
55 | } |
56 | else if(l>qr||r<ql) return; |
57 | pushdown(o,l,r); |
58 | int mid=(l+r)>>1; |
59 | if(ql<=mid) ltagm(ls,l,mid,ql,qr,v); |
60 | if(qr>mid) ltagm(rs,mid+1,r,ql,qr,v); |
61 | ct[o].val=(ct[ls].val+ct[rs].val)%p; |
62 | return; |
63 | } |
64 | void ltaga(int o,int l,int r,int ql,int qr,long long v){ |
65 | if(ql<=l&&qr>=r){ |
66 | ct[o].val=(ct[o].val+v*(r-l+1))%p; |
67 | ct[o].add=(ct[o].add+v)%p; |
68 | return; |
69 | } |
70 | else if(l>qr||r<ql) return; |
71 | pushdown(o,l,r); |
72 | int mid=(l+r)>>1; |
73 | if(ql<=mid) ltaga(ls,l,mid,ql,qr,v); |
74 | if(qr>mid) ltaga(rs,mid+1,r,ql,qr,v); |
75 | ct[o].val=(ct[ls].val+ct[rs].val)%p; |
76 | return; |
77 | } |
78 | long long check(int o,int l,int r,int ql,int qr){ |
79 | long long ans=0; |
80 | if(ql>r||qr<l){ |
81 | return 0; |
82 | } |
83 | else if(l>=ql&&qr>=r) return ct[o].val%p; |
84 | int mid=(l+r)>>1; |
85 | pushdown(o,l,r); |
86 | if(ql<=mid) ans=(ans+check(ls,l,mid,ql,qr))%p; |
87 | if(qr>mid) ans=(ans+check(rs,mid+1,r,ql,qr))%p; |
88 | return ans; |
89 | } |
90 | int main(){ |
91 | int m,n,i,j,x,y,d,c;long long k; |
92 | scanf("%d%d%lld",&n,&m,&p); |
93 | for(i=1;i<=n;i++){ |
94 | scanf("%lld",&a[i]); |
95 | } |
96 | build(1,1,n); |
97 | for(i=1;i<=m;i++){ |
98 | scanf("%d",&d); |
99 | if(d==3){ |
100 | scanf("%d%d",&x,&y); |
101 | printf("%d\n",check(1,1,n,x,y)); |
102 | } |
103 | else{ |
104 | scanf("%d%d%lld",&x,&y,&k); |
105 | if(d==1) ltagm(1,1,n,x,y,k); |
106 | else ltaga(1,1,n,x,y,k); |
107 | } |
108 | } |
109 | return 0; |
110 | } |
【模板】树状数组 1
题目描述
如题，已知一个数列，你需要进行下面两种操作：
- 将某一个数加上 $x$
- 求出某区间每一个数的和
输入格式
第一行包含两个正整数 $n,m$，分别表示该数列数字的个数和操作的总个数。
第二行包含 $n$ 个用空格分隔的整数，其中第$ i$ 个数字表示数列第$ i$ 项的初始值。
接下来 $m$ 行每行包含 3 个整数，表示一个操作，具体如下：
1 x k含义：将第$x$ 个数加上 $k$2 x y含义：输出区间$ [x,y]$内每个数的和
输出格式
输出包含若干行整数，即为所有操作 $2$ 的结果。
1 | |
2 | |
3 | using namespace std; |
4 | int a[505000],c[505000],n; |
5 | inline int lowbit(int x){ |
6 | return x & -x; |
7 | } |
8 | void change(int x,int t){ |
9 | while(x<=n){ |
10 | c[x]+=t; |
11 | x+=lowbit(x); |
12 | } |
13 | } |
14 | int Sum(int x){ |
15 | int res=0; |
16 | while(x!=0){ |
17 | res+=c[x]; |
18 | x-=lowbit(x); |
19 | } |
20 | return res; |
21 | } |
22 | int main(){ |
23 | int m,i,j,k,l,x,y,e; |
24 | scanf("%d%d",&n,&m); |
25 | for(i=1;i<=n;i++){ |
26 | scanf("%d",&a[i]); |
27 | change(i,a[i]); |
28 | } |
29 | for(i=1;i<=m;i++){ |
30 | scanf("%d%d%d",&e,&x,&y); |
31 | if(e==1){ |
32 | change(x,y); |
33 | } |
34 | else if(e==2){ |
35 | printf("%d\n",Sum(y)-Sum(x-1)); |
36 | } |
37 | } |
38 | return 0; |
39 | } |
【模板】树状数组 2
题目描述
如题，已知一个数列，你需要进行下面两种操作：
1.将某区间每一个数数加上x
2.求出某一个数的值
输入格式
第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。
第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。
接下来M行每行包含2或4个整数，表示一个操作，具体如下：
操作1： 格式：1 x y k 含义：将区间[x,y]内每个数加上k
操作2： 格式：2 x 含义：输出第x个数的值
输出格式
输出包含若干行整数，即为所有操作2的结果。
1 | |
2 | |
3 | using namespace std; |
4 | int c[500060],n; |
5 | int read(){ |
6 | int re=0,f=1;char c=getchar(); |
7 | while(c<'0'||c>'9'){ |
8 | if(c=='-') f=-1; |
9 | c=getchar(); |
10 | } |
11 | while(c>='0'&&c<='9'){ |
12 | re=re*10+c-'0'; |
13 | c=getchar(); |
14 | } |
15 | return re*f; |
16 | } |
17 | int lowbit(int x){ |
18 | return x & -x; |
19 | } |
20 | void change(int x,int u){ |
21 | while(x<=n){ |
22 | c[x]+=u; |
23 | x+=lowbit(x); |
24 | } |
25 | } |
26 | int Sum(int x){ |
27 | int s=0; |
28 | while(x){ |
29 | s+=c[x]; |
30 | x-=lowbit(x); |
31 | } |
32 | return s; |
33 | } |
34 | int main(){ |
35 | int m,i,j,a,k,p,l,r,w,t=0; |
36 | n=read();m=read(); |
37 | for(i=1;i<=n;i++){ |
38 | a=read(); |
39 | change(i,a-t); |
40 | t=a; |
41 | } |
42 | for(i=1;i<=m;i++){ |
43 | cin>>p; |
44 | if(p==1){ |
45 | l=read();r=read();w=read(); |
46 | change(l,w); |
47 | change(r+1,-w); |
48 | } |
49 | else if(p==2){ |
50 | w=read(); |
51 | cout<<Sum(w)<<endl; |
52 | } |
53 | } |
54 | return 0; |
55 | } |
【模板】卢卡斯定理
题目描述
给定$n,m,p(1\le n,m,p\le 10^5)$
求 $C_{n+m}^{m}\ mod\ p$
保证P为prime
C表示组合数。
一个测试点内包含多组数据。
输入格式
第一行一个整数$T(T\le 10)$，表示数据组数
第二行开始共T行，每行三个数n m p，意义如上
输出格式
共T行，每行一个整数表示答案。
1 | |
2 | |
3 | using namespace std; |
4 | long long n,m,p,jc[1000500]; |
5 | long long ksm(long long a,long long k){ |
6 | long long ans=1,base=a,mi=k; |
7 | while(mi){ |
8 | if(mi&1) ans=(ans*base)%p; |
9 | base=(base*base)%p; |
10 | mi>>=1; |
11 | } |
12 | return ans; |
13 | } |
14 | long long C(long long a,long long b){ |
15 | if(b>a) return 0; |
16 | long long ans=(((jc[a]*ksm(jc[b],p-2))%p)*ksm(jc[a-b],p-2))%p; |
17 | return ans; |
18 | } |
19 | long long lucas(long long a,long long b){ |
20 | if(a==0&&b!=0) return 0; |
21 | else if(b==0) return 1; |
22 | // cout<<a<<" "<<b<<endl; |
23 | return (C(a%p,b%p)*lucas(a/p,b/p))%p; |
24 | } |
25 | int main(){ |
26 | long long i,j;int t; |
27 | scanf("%d",&t); |
28 | while(t--){ |
29 | scanf("%lld%lld%lld",&n,&m,&p); |
30 | jc[0]=1; |
31 | for(i=1;i<=p;i++){ |
32 | jc[i]=(jc[i-1]*i)%p; |
33 | } |
34 | cout<<lucas(n+m,m)<<endl; |
35 | } |
36 | } |
【模板】最近公共祖先（LCA）
题目描述
如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。
输入格式
第一行包含三个正整数N、M、S，分别表示树的结点个数、询问的个数和树根结点的序号。
接下来N-1行每行包含两个正整数x、y，表示x结点和y结点之间有一条直接连接的边（数据保证可以构成树）。
接下来M行每行包含两个正整数a、b，表示询问a结点和b结点的最近公共祖先。
输出格式
输出包含M行，每行包含一个正整数，依次为每一个询问的结果。
1 | |
2 | |
3 | |
4 | using namespace std; |
5 | struct TREE{ |
6 | int x,y,next; |
7 | }t[1005000]; |
8 | int last[1005000],cent,lg[1005000],dep[1005000],f[1005000][20]; |
9 | void add(int x,int y){ |
10 | t[++cent].x=x; |
11 | t[cent].y=y; |
12 | t[cent].next=last[x]; |
13 | last[x]=cent; |
14 | } |
15 | void build(int a,int fa){ |
16 | dep[a]=dep[fa]+1; |
17 | f[a][0]=fa; |
18 | for(int i=1;i<=lg[dep[a]];i++){ |
19 | f[a][i]=f[f[a][i-1]][i-1]; |
20 | } |
21 | int u=last[a]; |
22 | while(u){ |
23 | int v=t[u].y; |
24 | if(fa!=v){ |
25 | build(v,a); |
26 | } |
27 | u=t[u].next; |
28 | } |
29 | } |
30 | int lca(int x,int y){ |
31 | if(dep[x]<dep[y]){ |
32 | int tmp=x; |
33 | x=y; |
34 | y=tmp; |
35 | } |
36 | while(dep[x]>dep[y]){ |
37 | x=f[x][lg[dep[x]-dep[y]]]; |
38 | } |
39 | if(x==y) return x; |
40 | for(int k=lg[dep[x]];k>=0;k--){ |
41 | if(f[x][k]!=f[y][k]){ |
42 | x=f[x][k]; |
43 | y=f[y][k]; |
44 | } |
45 | |
46 | } |
47 | return f[x][0]; |
48 | } |
49 | int main(){ |
50 | int m,n,i,j,k,l,x,y,s; |
51 | scanf("%d%d%d",&n,&m,&s); |
52 | for(i=2;i<=n;i++) lg[i]=lg[i>>1]+1; |
53 | for(i=1;i<n;i++){ |
54 | scanf("%d%d",&x,&y); |
55 | add(x,y); |
56 | add(y,x); |
57 | } |
58 | build(s,0); |
59 | for(i=1;i<=m;i++){ |
60 | scanf("%d%d",&x,&y); |
61 | printf("%d\n",lca(x,y)); |
62 | } |
63 | } |
【模板】KMP字符串匹配
题目描述
如题，给出两个字符串s1和s2，其中s2为s1的子串，求出s2在s1中所有出现的位置。
为了减少骗分的情况，接下来还要输出子串的前缀数组next。
（如果你不知道这是什么意思也不要问，去百度搜[kmp算法]学习一下就知道了。）
输入格式
第一行为一个字符串，即为s1
第二行为一个字符串，即为s2
输出格式
若干行，每行包含一个整数，表示s2在s1中出现的位置
接下来1行，包括length(s2)个整数，表示前缀数组next[i]的值。
1 | |
2 | |
3 | |
4 | using namespace std; |
5 | int kmp[MAXN]; |
6 | char a[MAXN],b[MAXN]; |
7 | int main() |
8 | { |
9 | cin>>a+1; |
10 | cin>>b+1; |
11 | int la,lb,j; |
12 | la=strlen(a+1); |
13 | lb=strlen(b+1); |
14 | for (int i=2;i<=lb;i++) |
15 | { |
16 | while(j&&b[i]!=b[j+1]) |
17 | j=kmp[j]; |
18 | if(b[j+1]==b[i])j++; |
19 | kmp[i]=j; |
20 | } |
21 | j=0; |
22 | for(int i=1;i<=la;i++) |
23 | { |
24 | while(j>0&&b[j+1]!=a[i]) |
25 | j=kmp[j]; |
26 | if (b[j+1]==a[i]) |
27 | j++; |
28 | if (j==lb) {cout<<i-lb+1<<endl;j=kmp[j];} |
29 | } |
30 | |
31 | for (int i=1;i<=lb;i++) |
32 | cout<<kmp[i]<<" "; |
33 | return 0; |
34 | } |
【模板】二分图匹配
题目描述
给定一个二分图，结点个数分别为n,m，边数为e，求二分图最大匹配数
输入格式
第一行，n,m,e
第二至e+1行，每行两个正整数u,v，表示u,v有一条连边
输出格式
共一行，二分图最大匹配
1 | |
2 | |
3 | |
4 | using namespace std; |
5 | struct EDGE{ |
6 | int to,nxt; |
7 | }t[6000050]; |
8 | int last[2200],cnt,ans=0;bool vis[2200];int pd[2200]; |
9 | void build(int u,int v){ |
10 | t[++cnt].to=v; |
11 | t[cnt].nxt=last[u]; |
12 | last[u]=cnt; |
13 | } |
14 | bool dfs(int x){ |
15 | int e=last[x]; |
16 | while(e){ |
17 | int v=t[e].to; |
18 | if(!vis[v]){ |
19 | vis[v]=1; |
20 | if(pd[v]==-1||dfs(pd[v])){ |
21 | pd[x]=v; |
22 | pd[v]=x; |
23 | return 1; |
24 | } |
25 | } |
26 | e=t[e].nxt; |
27 | } |
28 | return 0; |
29 | } |
30 | int n,m; |
31 | void hungary(){ |
32 | memset(pd,-1,sizeof(pd)); |
33 | for(int i=1;i<=n;i++){ |
34 | memset(vis,0,sizeof(vis)); |
35 | if(dfs(i)) ans++; |
36 | } |
37 | } |
38 | int main(){ |
39 | int i,j,k,e,u,v; |
40 | scanf("%d%d%d",&n,&m,&e); |
41 | for(i=1;i<=e;i++){ |
42 | scanf("%d%d",&u,&v); |
43 | if(v>m) continue; |
44 | build(u,v+n); |
45 | build(v+n,u); |
46 | } |
47 | hungary(); |
48 | printf("%d",ans); |
49 | return 0; |
50 | } |
【模板】字符串哈希
题目描述
如题，给定N个字符串（第i个字符串长度为Mi，字符串内包含数字、大小写字母，大小写敏感），请求出N个字符串中共有多少个不同的字符串。
#友情提醒：如果真的想好好练习哈希的话，请自觉，否则请右转PJ试炼场:)
输入格式
第一行包含一个整数N，为字符串的个数。
接下来N行每行包含一个字符串，为所提供的字符串。
输出格式
输出包含一行，包含一个整数，为不同的字符串个数。
1 | |
2 | |
3 | |
4 | using namespace std; |
5 | int list[1005000],next[1005000],cent;string data[1005000]; |
6 | int hash(string x){ |
7 | int ha=0; |
8 | int seed=233; |
9 | int mod=441449; |
10 | for(int i=0;i<x.size();i++){ |
11 | ha=((ha*seed)+x[i]-'0')%mod; |
12 | } |
13 | return ha; |
14 | } |
15 | void add(string x){ |
16 | int sum=hash(x); |
17 | int u=list[sum]; |
18 | while(u){ |
19 | if(data[u]==x) return; |
20 | u=next[u]; |
21 | } |
22 | cent++; |
23 | data[cent]=x; |
24 | next[cent]=list[sum]; |
25 | list[sum]=cent; |
26 | } |
27 | int main(){ |
28 | int i,j,k,n;string s; |
29 | cin>>n; |
30 | for(i=1;i<=n;i++){ |
31 | cin>>s; |
32 | add(s); |
33 | } |
34 | cout<<cent; |
35 | return 0; |
36 | } |
【模板】单源最短路径（标准版）
题目描述
给定一个 $n$ 个点，$m$ 条有向边的带非负权图，请你计算从 $s$ 出发，到每个点的距离。
数据保证你能从 $s$ 出发到任意点。
输入格式
第一行为三个正整数 $n, m, s$。 第二行起 $m$ 行，每行三个非负整数 $u_i, v_i, w_i$，表示从 $u_i$到 $v_i$ 有一条权值为 $w_i$的有向边。
输出格式
输出一行 $n$ 个空格分隔的非负整数，表示 $s$ 到每个点的距离。
1 | |
2 | |
3 | |
4 | using namespace std; |
5 | struct UU{ |
6 | int u;long long w; |
7 | }; |
8 | struct TU{ |
9 | int to,nxt;long long w; |
10 | }e[400005]; |
11 | int cnt,last[100004];long long dis[100004]; |
12 | struct cmp{ |
13 | bool operator()(const UU &a,const UU &b){ |
14 | return a.w>b.w; |
15 | } |
16 | }; |
17 | void build(int u,int v,long long w){ |
18 | e[++cnt].to=v;e[cnt].w=w;e[cnt].nxt=last[u]; |
19 | last[u]=cnt; |
20 | } |
21 | priority_queue<UU,vector<UU>,cmp> q; |
22 | int main(){ |
23 | int i,j,k,m,n,u,v,x,y,s;long long w; |
24 | scanf("%d%d%d",&n,&m,&s); |
25 | for(i=1;i<=m;i++){ |
26 | scanf("%d%d%lld",&u,&v,&w); |
27 | build(u,v,w); |
28 | } |
29 | for(i=1;i<=n;i++) dis[i]=2e9; |
30 | dis[s]=0; |
31 | UU tmp; |
32 | tmp.u=s;tmp.w=0; |
33 | q.push(tmp); |
34 | while(!q.empty()){ |
35 | u=q.top().u;w=q.top().w;q.pop(); |
36 | if(dis[u]<w) continue; |
37 | y=last[u]; |
38 | while(y){ |
39 | v=e[y].to; |
40 | if(dis[u]+e[y].w<dis[v]){ |
41 | dis[v]=dis[u]+e[y].w; |
42 | tmp.u=v;tmp.w=dis[v]; |
43 | q.push(tmp); |
44 | } |
45 | y=e[y].nxt; |
46 | } |
47 | } |
48 | for(i=1;i<=n;i++){ |
49 | printf("%lld ",dis[i]); |
50 | } |
51 | return 0; |
52 | } |
【模板】强连通分量 / [HAOI2006]受欢迎的牛
题目描述
每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果A喜欢B，B喜欢C，那么A也喜欢C。牛栏里共有N 头奶牛，给定一些奶牛之间的爱慕关系，请你算出有多少头奶牛可以当明星。
输入格式
第一行：两个用空格分开的整数：N和M
第二行到第M + 1行：每行两个用空格分开的整数：A和B，表示A喜欢B
输出格式
第一行：单独一个整数，表示明星奶牛的数量
1 | |
2 | |
3 | |
4 | using namespace std; |
5 | struct TU{ |
6 | int from,to,nxt; |
7 | }t[55000]; |
8 | int last[10050],cnt; |
9 | void build(int u,int v){ |
10 | t[++cnt].to=v; |
11 | t[cnt].from=u; |
12 | t[cnt].nxt=last[u]; |
13 | last[u]=cnt; |
14 | } |
15 | stack<int> st; |
16 | int dfn[10050],low[10050],tcr,bq[10050],qfl,sz[10050],f[10050],cd[10050]; |
17 | void tarjan(int x){ |
18 | dfn[x]=low[x]=++tcr;st.push(x); |
19 | int e=last[x]; |
20 | while(e){ |
21 | int v=t[e].to; |
22 | if(!dfn[v]){ |
23 | tarjan(v); |
24 | if(low[x]>low[v]) low[x]=low[v]; |
25 | } |
26 | else if(!bq[v]){ |
27 | if(low[x]>low[v]) low[x]=low[v]; |
28 | } |
29 | e=t[e].nxt; |
30 | } |
31 | if(dfn[x]==low[x]){ |
32 | qfl++;int j=-1; |
33 | do{ |
34 | j=st.top(); |
35 | st.pop(); |
36 | bq[j]=qfl; |
37 | sz[qfl]++; |
38 | }while(j!=x); |
39 | } |
40 | } |
41 | int find(int x){ |
42 | if(x!=f[x]) f[x]=find(f[x]); |
43 | return f[x]; |
44 | } |
45 | int main(){ |
46 | int i,j,k,m,n,u,v;int ans=-1; |
47 | scanf("%d%d",&n,&m); |
48 | for(i=1;i<=m;i++){ |
49 | scanf("%d%d",&u,&v); |
50 | build(u,v); |
51 | } |
52 | for(i=1;i<=n;i++){ |
53 | if(!dfn[i]) tarjan(i); |
54 | } |
55 | for(i=1;i<=qfl;i++) f[i]=i; |
56 | int ctw=qfl-1; |
57 | for(i=1;i<=m;i++){ |
58 | u=bq[t[i].from];v=bq[t[i].to]; |
59 | if(u!=v){ |
60 | cd[u]++; |
61 | } |
62 | } |
63 | for(i=1;i<=qfl;i++){ |
64 | if(cd[i]==0){ |
65 | if(ans==-1) ans=i; |
66 | else{ |
67 | printf("0"); |
68 | return 0; |
69 | } |
70 | } |
71 | } |
72 | printf("%d",sz[ans]); |
73 | return 0; |
74 | } |
【模板】普通平衡树
题目描述
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
- 插入 x 数
- 删除 x数(若有多个相同的数，因只删除一个)
- 查询 x 数的排名(排名定义为比当前数小的数的个数 +1 )
- 查询排名为 x 的数
- 求 x的前驱(前驱定义为小于 x，且最大的数)
- 求 x 的后继(后继定义为大于 x，且最小的数)
输入格式
第一行为 $n$，表示操作的个数,下面 n 行每行有两个数$ \text{opt} 和 x，\text{opt} $表示操作的序号$( 1 \leq \text{opt} \leq 6 )$
输出格式
对于操作 $3,4,5,6$每行输出一个数，表示对应答案
1 | |
2 | |
3 | |
4 | using namespace std; |
5 | const int N=1e5+5; |
6 | struct SBT{ |
7 | int l,r,size,v,rnd,w; |
8 | }t[N]; |
9 | int root,cnt,ans; |
10 | int read(){ |
11 | int re=0,f=1;char c=getchar(); |
12 | while(c<'0'||c>'9'){ |
13 | if(c=='-') f=-1; |
14 | c=getchar(); |
15 | } |
16 | while(c>='0'&&c<='9'){ |
17 | re=re*10+c-'0'; |
18 | c=getchar(); |
19 | } |
20 | return re*f; |
21 | } |
22 | void update(int x){ |
23 | t[x].size=t[t[x].l].size+t[t[x].r].size+t[x].w; |
24 | } |
25 | void lturn(int &x){ |
26 | int c=t[x].r; |
27 | t[x].r=t[c].l; |
28 | t[c].l=x; |
29 | t[c].size=t[x].size; |
30 | update(x); |
31 | x=c; |
32 | } |
33 | void rturn(int &x){ |
34 | int c=t[x].l; |
35 | t[x].l=t[c].r; |
36 | t[c].r=x; |
37 | t[c].size=t[x].size; |
38 | update(x); |
39 | x=c; |
40 | } |
41 | void insert(int &x,int v){ |
42 | if(x==0){ |
43 | x=++cnt; |
44 | t[cnt].v=v; |
45 | t[cnt].size=t[cnt].w=1; |
46 | t[cnt].rnd=rand(); |
47 | t[cnt].l=t[cnt].r=0; |
48 | return; |
49 | } |
50 | t[x].size++; |
51 | if(v==t[x].v){ |
52 | t[x].w++; |
53 | return; |
54 | } |
55 | else if(v<t[x].v){ |
56 | insert(t[x].l,v); |
57 | if(t[t[x].l].rnd<t[x].rnd) rturn(x); |
58 | } |
59 | else{ |
60 | insert(t[x].r,v); |
61 | if(t[t[x].r].rnd<t[x].rnd) lturn(x); |
62 | } |
63 | } |
64 | void del(int &x,int v){ |
65 | if(x==0) return; |
66 | if(t[x].v==v){ |
67 | if(t[x].w>1){ |
68 | t[x].w--; |
69 | t[x].size--; |
70 | return; |
71 | } |
72 | if(t[x].l*t[x].r==0) x=t[x].l+t[x].r; |
73 | else{ |
74 | if(t[t[x].l].rnd<t[t[x].r].rnd){ |
75 | rturn(x); |
76 | del(x,v); |
77 | } |
78 | else{ |
79 | lturn(x); |
80 | del(x,v); |
81 | } |
82 | } |
83 | } |
84 | else{ |
85 | t[x].size--; |
86 | if(v<t[x].v) del(t[x].l,v); |
87 | else del(t[x].r,v); |
88 | } |
89 | } |
90 | int rnk(int x,int v){ |
91 | if(x==0) return 0; |
92 | if(t[x].v==v) return t[t[x].l].size+1; |
93 | else if(v<t[x].v){ |
94 | return rnk(t[x].l,v); |
95 | } |
96 | else return t[t[x].l].size+t[x].w+rnk(t[x].r,v); |
97 | } |
98 | int kth(int x,int k){ |
99 | if(x==0) return 0; |
100 | if(k<=t[t[x].l].size) return kth(t[x].l,k); |
101 | else if(k>t[t[x].l].size+t[x].w) return kth(t[x].r,k-t[t[x].l].size-t[x].w); |
102 | else return t[x].v; |
103 | } |
104 | void pre(int x,int v){ |
105 | if(x==0) return; |
106 | if(t[x].v<v){ |
107 | ans=x; |
108 | pre(t[x].r,v); |
109 | } |
110 | else pre(t[x].l,v); |
111 | } |
112 | void suf(int x,int v){ |
113 | if(x==0) return; |
114 | if(t[x].v>v){ |
115 | ans=x; |
116 | suf(t[x].l,v); |
117 | } |
118 | else suf(t[x].r,v); |
119 | } |
120 | int main(){ |
121 | int i,j,k,m,n,opt,w; |
122 | // freopen("treap1.out","w",stdout); |
123 | srand(1217); |
124 | n=read(); |
125 | while(n--){ |
126 | opt=read(); |
127 | w=read(); |
128 | switch(opt){ |
129 | case 1:insert(root,w);break; |
130 | case 2:del(root,w);break; |
131 | case 3:printf("%d\n",rnk(root,w));break; |
132 | case 4:printf("%d\n",kth(root,w));break; |
133 | case 5:ans=0;pre(root,w);printf("%d\n",t[ans].v);break; |
134 | case 6:ans=0;suf(root,w);printf("%d\n",t[ans].v);break; |
135 | } |
136 | } |
137 | return 0; |
138 | } |
高精度模板
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
9 | |
10 | using namespace std; |
11 | struct Wint:vector<int>//用标准库vector做基类，完美解决位数问题，同时更易于实现 |
12 | { |
13 | //将低精度转高精度的初始化，可以自动被编译器调用 |
14 | //因此无需单独写高精度数和低精度数的运算函数，十分方便 |
15 | Wint(int n=0)//默认初始化为0，但0的保存形式为空 |
16 | { |
17 | push_back(n); |
18 | check(); |
19 | } |
20 | Wint& check()//在各类运算中经常用到的进位小函数，不妨内置 |
21 | { |
22 | while(!empty()&&!back())pop_back();//去除最高位可能存在的0 |
23 | if(empty())return *this; |
24 | for(int i=1; i<size(); ++i)//处理进位 |
25 | { |
26 | (*this)[i]+=(*this)[i-1]/10; |
27 | (*this)[i-1]%=10; |
28 | } |
29 | while(back()>=10) |
30 | { |
31 | push_back(back()/10); |
32 | (*this)[size()-2]%=10; |
33 | } |
34 | return *this;//为使用方便，将进位后的自身返回引用 |
35 | } |
36 | }; |
37 | //输入输出 |
38 | istream& operator>>(istream &is,Wint &n) |
39 | { |
40 | string s; |
41 | is>>s; |
42 | n.clear(); |
43 | for(int i=s.size()-1; i>=0; --i)n.push_back(s[i]-'0'); |
44 | return is; |
45 | } |
46 | ostream& operator<<(ostream &os,const Wint &n) |
47 | { |
48 | if(n.empty())os<<0; |
49 | for(int i=n.size()-1; i>=0; --i)os<<n[i]; |
50 | return os; |
51 | } |
52 | //比较，只需要写两个，其他的直接代入即可 |
53 | //常量引用当参数，避免拷贝更高效 |
54 | bool operator!=(const Wint &a,const Wint &b) |
55 | { |
56 | if(a.size()!=b.size())return 1; |
57 | for(int i=a.size()-1; i>=0; --i) |
58 | if(a[i]!=b[i])return 1; |
59 | return 0; |
60 | } |
61 | bool operator==(const Wint &a,const Wint &b) |
62 | { |
63 | return !(a!=b); |
64 | } |
65 | bool operator<(const Wint &a,const Wint &b) |
66 | { |
67 | if(a.size()!=b.size())return a.size()<b.size(); |
68 | for(int i=a.size()-1; i>=0; --i) |
69 | if(a[i]!=b[i])return a[i]<b[i]; |
70 | return 0; |
71 | } |
72 | bool operator>(const Wint &a,const Wint &b) |
73 | { |
74 | return b<a; |
75 | } |
76 | bool operator<=(const Wint &a,const Wint &b) |
77 | { |
78 | return !(a>b); |
79 | } |
80 | bool operator>=(const Wint &a,const Wint &b) |
81 | { |
82 | return !(a<b); |
83 | } |
84 | //加法，先实现+=，这样更简洁高效 |
85 | Wint& operator+=(Wint &a,const Wint &b) |
86 | { |
87 | if(a.size()<b.size())a.resize(b.size()); |
88 | for(int i=0; i!=b.size(); ++i)a[i]+=b[i]; |
89 | return a.check(); |
90 | } |
91 | Wint operator+(Wint a,const Wint &b) |
92 | { |
93 | return a+=b; |
94 | } |
95 | //减法，返回差的绝对值，由于后面有交换，故参数不用引用 |
96 | Wint& operator-=(Wint &a,Wint b) |
97 | { |
98 | if(a<b)swap(a,b); |
99 | for(int i=0; i!=b.size(); a[i]-=b[i],++i) |
100 | if(a[i]<b[i])//需要借位 |
101 | { |
102 | int j=i+1; |
103 | while(!a[j])++j; |
104 | while(j>i) |
105 | { |
106 | --a[j]; |
107 | a[--j]+=10; |
108 | } |
109 | } |
110 | return a.check(); |
111 | } |
112 | Wint operator-(Wint a,const Wint &b) |
113 | { |
114 | return a-=b; |
115 | } |
116 | //乘法不能先实现*=，原因自己想 |
117 | Wint operator*(const Wint &a,const Wint &b) |
118 | { |
119 | Wint n; |
120 | n.assign(a.size()+b.size()-1,0); |
121 | for(int i=0; i!=a.size(); ++i) |
122 | for(int j=0; j!=b.size(); ++j) |
123 | n[i+j]+=a[i]*b[j]; |
124 | return n.check(); |
125 | } |
126 | Wint& operator*=(Wint &a,const Wint &b) |
127 | { |
128 | return a=a*b; |
129 | } |
130 | //除法和取模先实现一个带余除法函数 |
131 | Wint divmod(Wint &a,const Wint &b) |
132 | { |
133 | Wint ans; |
134 | for(int t=a.size()-b.size(); a>=b; --t) |
135 | { |
136 | Wint d; |
137 | d.assign(t+1,0); |
138 | d.back()=1; |
139 | Wint c=b*d; |
140 | while(a>=c) |
141 | { |
142 | a-=c; |
143 | ans+=d; |
144 | } |
145 | } |
146 | return ans; |
147 | } |
148 | Wint operator/(Wint a,const Wint &b) |
149 | { |
150 | return divmod(a,b); |
151 | } |
152 | Wint& operator/=(Wint &a,const Wint &b) |
153 | { |
154 | return a=a/b; |
155 | } |
156 | Wint& operator%=(Wint &a,const Wint &b) |
157 | { |
158 | divmod(a,b); |
159 | return a; |
160 | } |
161 | Wint operator%(Wint a,const Wint &b) |
162 | { |
163 | return a%=b; |
164 | } |
165 | //顺手实现一个快速幂，可以看到和普通快速幂几乎无异 |
166 | Wint pow(const Wint &n,const Wint &k) |
167 | { |
168 | if(k.empty())return 1; |
169 | if(k==2)return n*n; |
170 | if(k.back()%2)return n*pow(n,k-1); |
171 | return pow(pow(n,k/2),2); |
172 | } |
173 | int main() |
174 | { |
175 | |
176 | } |
高精加
1 | |
2 | |
3 | |
4 | |
5 | |
6 | using namespace std; |
7 | |
8 | const int L = 110; |
9 | |
10 | string a, b; |
11 | |
12 | string add(string a, string b)//只限两个非负整数相加 |
13 | { |
14 | string ans; |
15 | int na[L] = {0}; |
16 | int nb[L] = {0}; |
17 | int la = a.size(); |
18 | int lb = b.size(); |
19 | for (int i = 0; i < la; i++) |
20 | na[la - 1 - i] = a[i] - '0'; |
21 | for (int i = 0; i < lb; i++) |
22 | nb[lb - 1 - i] = b[i] - '0'; |
23 | int lmax = la > lb ? la : lb; |
24 | for (int i = 0; i < lmax; i++) |
25 | { |
26 | na[i] += nb[i]; |
27 | na[i + 1] += na[i] / 10; |
28 | na[i] %= 10; |
29 | } |
30 | if (na[lmax]) lmax++; |
31 | for (int i = lmax - 1; i >= 0; i--) |
32 | ans += na[i] + '0'; |
33 | return ans; |
34 | } |
35 | |
36 | int main() |
37 | { |
38 | ios::sync_with_stdio(false); |
39 | cin.tie(0); |
40 | while (cin >> a >> b) |
41 | cout << add(a, b) << endl; |
42 | return 0; |
43 | } |
高精减
1 | |
2 | |
3 | |
4 | |
5 | |
6 | using namespace std; |
7 | //#define DEBUG(x) cerr << #x << "=" << x << endl |
8 | typedef unsigned char BYTE; |
9 | |
10 | BYTE a[10005] = {0}; |
11 | BYTE b[10005] = {0}; |
12 | BYTE *pa = 0, *pb = 0; |
13 | int la, lb; |
14 | int sign; |
15 | |
16 | int main() |
17 | { |
18 | scanf("%s", a); |
19 | scanf("%s", b); |
20 | la = strlen((char*)a); |
21 | lb = strlen((char*)b); |
22 | int i; |
23 | for (int i = 0; i < la; i++) |
24 | { |
25 | a[i] -= '0'; |
26 | } |
27 | for (int i = 0; i < lb; i++) |
28 | { |
29 | b[i] -= '0'; |
30 | } |
31 | if (la > lb) |
32 | { |
33 | sign = 1; |
34 | } |
35 | else if (la < lb) |
36 | { |
37 | sign = 0; |
38 | } |
39 | else |
40 | { |
41 | sign = -1; |
42 | int BCT; |
43 | for (BCT = 0; BCT < la; BCT++) |
44 | { |
45 | if (a[BCT] > b[BCT]) |
46 | { |
47 | sign = 1; |
48 | break; |
49 | } |
50 | if (a[BCT] < b[BCT]) |
51 | { |
52 | sign = 0; |
53 | break; |
54 | } |
55 | } |
56 | if (sign == -1) |
57 | { |
58 | printf("0"); |
59 | return 0; |
60 | } |
61 | } |
62 | if (sign == 1) |
63 | { |
64 | pa = a; |
65 | pb = b; |
66 | } |
67 | else |
68 | { |
69 | pa = b; |
70 | pb = a; |
71 | int buf; |
72 | buf = la; |
73 | la = lb; |
74 | lb = buf; |
75 | } |
76 | memmove(pb + la - lb, pb, lb); |
77 | memset(pb, 0, la - lb); |
78 | for (int i = 0; i < la; i++) |
79 | { |
80 | pb[i] = 9 - pb[i]; |
81 | } |
82 | pb[la - 1]++; |
83 | for (int i = la - 1; i >= 0; i--) |
84 | { |
85 | pa[i] += pb[i]; |
86 | if (pa[i] >= 10) |
87 | { |
88 | pa[i] -= 10; |
89 | if (i != 0) |
90 | { |
91 | pa[i - 1]++; |
92 | } |
93 | } |
94 | } |
95 | for (int i = 0; i < la; i++) |
96 | { |
97 | pa[i] += '0'; |
98 | } |
99 | if (sign == 0) |
100 | { |
101 | printf("-"); |
102 | } |
103 | for (int i = 0; i < la; i++) |
104 | { |
105 | if (pa[i] != '0') |
106 | { |
107 | printf((char*)pa + i); |
108 | return 0; |
109 | } |
110 | } |
111 | return 0; |
112 | } |
高精乘
1 | |
2 | |
3 | |
4 | |
5 | |
6 | using namespace std; |
7 | //#define DEBUG(x) cerr << #x << "=" << x << endl |
8 | const int L = 110; |
9 | |
10 | string a, b; |
11 | |
12 | string mul(string a, string b) |
13 | { |
14 | string s; |
15 | int na[L]; |
16 | int nb[L]; |
17 | int nc[L]; |
18 | int La = a.size(); |
19 | int Lb = b.size(); |
20 | fill(na, na + L, 0); |
21 | fill(nb, nb + L, 0); |
22 | fill(nc, nc + L, 0); |
23 | for (int i = La - 1; i >= 0; i--) |
24 | na[La - i] = a[i] - '0'; |
25 | for (int i = Lb - 1; i >= 0; i--) |
26 | nb[Lb - i] = b[i] - '0'; |
27 | for (int i = 1; i <= La; i++) |
28 | { |
29 | for (int j = 1; j <= Lb; j++) |
30 | { |
31 | nc[i + j - 1] += na[i] * nb[j]; |
32 | } |
33 | } |
34 | for (int i = 1; i <= La + Lb; i++) |
35 | { |
36 | nc[i + 1] += nc[i] / 10; |
37 | nc[i] %= 10; |
38 | } |
39 | if (nc[La + Lb]) |
40 | s += nc[La + Lb] + '0'; |
41 | for (int i = La + Lb - 1; i >= 1; i--) |
42 | s += nc[i] + '0'; |
43 | return s; |
44 | } |
45 | |
46 | int main() |
47 | { |
48 | while (cin >> a >> b) |
49 | cout << mul(a, b) << endl; |
50 | return 0; |
51 | } |
高精度乘法FFT优化
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | using namespace std; |
8 | //#define DEBUG(x) cerr << #x << "=" << x << endl |
9 | |
10 | const double PI = acos(-1.0); |
11 | const int maxn = 133015; |
12 | |
13 | double ax[maxn], ay[maxn], bx[maxn], by[maxn]; |
14 | char sa[maxn / 2], sb[maxn / 2]; |
15 | int sum[maxn]; |
16 | int x1[maxn], x2[maxn]; |
17 | string a, b; |
18 | |
19 | int max(int a, int b) |
20 | { |
21 | return a > b ? a : b; |
22 | } |
23 | |
24 | int revv(int x, int bits) |
25 | { |
26 | int ret = 0; |
27 | for (int i = 0; i < bits; i++) |
28 | { |
29 | ret <<= 1; |
30 | ret |= x & 1; |
31 | x >>= 1; |
32 | } |
33 | return ret; |
34 | } |
35 | |
36 | void fft(double *a, double *b, int n, bool rev) |
37 | { |
38 | int bits = 0; |
39 | while (1 << bits < n) |
40 | ++bits; |
41 | for (int i = 0; i < n; i++) |
42 | { |
43 | int j = revv(i, bits); |
44 | if (i < j) |
45 | { |
46 | swap(a[i], a[j]); |
47 | swap(b[i], b[j]); |
48 | } |
49 | } |
50 | for (int len = 2; len <= n; len <<= 1) |
51 | { |
52 | int half = len >> 1; |
53 | double wmx = cos(2 * PI / len); |
54 | double wmy = sin(2 * PI / len); |
55 | if (rev) |
56 | wmy = -wmy; |
57 | for (int i = 0; i < n; i += len) |
58 | { |
59 | double wx = 1; |
60 | double wy = 0; |
61 | for (int j = 0; j < half; j++) |
62 | { |
63 | double cx = a[i + j]; |
64 | double cy = b[i + j]; |
65 | double dx = a[i + j + half]; |
66 | double dy = b[i + j + half]; |
67 | double ex = dx * wx - dy * wy; |
68 | double ey = dx * wy + dy * wx; |
69 | a[i + j] = cx + ex; |
70 | b[i + j] = cy + ey; |
71 | a[i + j + half] = cx - ex; |
72 | b[i + j + half] = cy - ey; |
73 | double wnx = wx * wmx - wy * wmy; |
74 | double wny = wx * wmy + wy * wmx; |
75 | wx = wnx; |
76 | wy = wny; |
77 | } |
78 | } |
79 | } |
80 | if (rev) |
81 | { |
82 | for (int i = 0; i < n; i++) |
83 | { |
84 | a[i] /= n; |
85 | b[i] /= n; |
86 | } |
87 | } |
88 | } |
89 | |
90 | int solve(int a[], int na, int b[], int nb, int ans[]) |
91 | { |
92 | int len = max(na, nb); |
93 | int ln; |
94 | for (int ln = 0; L(ln) < len; ++ln) |
95 | len = L(++ln); |
96 | for (int i = 0; i < len; ++i) |
97 | { |
98 | if (i >= na) |
99 | { |
100 | ax[i] = 0; |
101 | ay[i] = 0; |
102 | } |
103 | else |
104 | { |
105 | ax[i] = a[i]; |
106 | ay[i] = 0; |
107 | } |
108 | } |
109 | fft(ax, ay, len, 0); |
110 | for (int i = 0; i < len; ++i) |
111 | { |
112 | if (i >= nb) |
113 | { |
114 | bx[i] = 0; |
115 | by[i] = 0; |
116 | } |
117 | else |
118 | { |
119 | bx[i] = b[i]; |
120 | by[i] = 0; |
121 | } |
122 | } |
123 | fft(bx, by, len, 0); |
124 | for (int i = 0; i < len; ++i) |
125 | { |
126 | double cx = ax[i] * bx[i] - ay[i] * by[i]; |
127 | double cy = ax[i] * by[i] + ay[i] * bx[i]; |
128 | ax[i] = cx; |
129 | ay[i] = cy; |
130 | } |
131 | fft(ax, ay, len, 1); |
132 | for (int i = 0; i < len; ++i) |
133 | ans[i] = (int)(ax[i] + 0.5); |
134 | return len; |
135 | } |
136 | |
137 | string mul(string sa, string sb) |
138 | { |
139 | int l1, l2, l; |
140 | int i; |
141 | string ans; |
142 | memset(sum, 0, sizeof(sum)); |
143 | l1 = sa.size(); |
144 | l2 = sb.size(); |
145 | for (int i = 0; i < l1; i++) |
146 | x1[i] = sa[l1 - i - 1] - '0'; |
147 | for (int i = 0; i < l2; i++) |
148 | x2[i] = sb[l2 - i - 1] - '0'; |
149 | l = solve(x1, l1, x2, l2, sum); |
150 | for (int i = 0; i < l || sum[i] >= 10; i++) |
151 | { |
152 | sum[i + 1] += sum[i] / 10; |
153 | sum[i] %= 10; |
154 | } |
155 | l = i; |
156 | while (sum[l] <= 0 && l > 0) |
157 | l--; |
158 | for (int i = l; i >= 0; i--) |
159 | ans += sum[i] + '0'; |
160 | return ans; |
161 | } |
162 | |
163 | int main() |
164 | { |
165 | ios::sync_with_stdio(false); |
166 | cin.tie(0); |
167 | while (cin >> a >> b) |
168 | cout << mul(a, b) << endl; |
169 | return 0; |
170 | } |
高精度除法(包括取模)
1 | |
2 | |
3 | |
4 | |
5 | |
6 | using namespace std; |
7 | //#define DEBUG(x) cerr << #x << "=" << x << endl |
8 | const int L = 110; |
9 | |
10 | string a, b; |
11 | |
12 | int sub(int *a, int *b, int La, int Lb) |
13 | { |
14 | if (La < Lb) return -1; |
15 | if (La == Lb) |
16 | { |
17 | for (int i = La - 1; i >= 0; i--) |
18 | { |
19 | if (a[i] > b[i]) break; |
20 | else if (a[i] < b[i]) return -1; |
21 | } |
22 | } |
23 | for (int i = 0; i < La; i++) |
24 | { |
25 | a[i] -= b[i]; |
26 | if (a[i] < 0) |
27 | { |
28 | a[i] += 10; |
29 | a[i + 1]--; |
30 | } |
31 | } |
32 | for (int i = La - 1; i >= 0; i--) |
33 | if (a[i]) return i + 1; |
34 | return 0; |
35 | } |
36 | |
37 | string div(string n1, string n2, int nn) |
38 | { |
39 | string s, v; |
40 | int a[L], b[L], r[L]; |
41 | int La = n1.size(), Lb = n2.size(); |
42 | int i, tp = La; |
43 | fill(a, a + L, 0); |
44 | fill(b, b + L, 0); |
45 | fill(r, r + L, 0); |
46 | for (int i = La - 1; i >= 0; i--) a[La - i - 1] = n1[i] - '0'; |
47 | for (int i = Lb - 1; i >= 0; i--) b[Lb - i - 1] = n2[i] - '0'; |
48 | if (La < Lb || (La == Lb && n1 < n2)) |
49 | { |
50 | return n1; |
51 | } |
52 | int t = La - Lb; |
53 | for (int i = La - 1;i >= 0; i--) |
54 | if (i >= t) b[i] = b[i - t]; |
55 | else b[i] = 0; |
56 | Lb = La; |
57 | for (int j = 0; j <= t; j++) |
58 | { |
59 | int temp; |
60 | while ((temp = sub(a, b + j, La, Lb - j)) >= 0) |
61 | { |
62 | La = temp; |
63 | r[t - j]++; |
64 | } |
65 | } |
66 | for (int i = 0; i < L - 10; i++) |
67 | { |
68 | r[i + 1] += r[i] / 10; |
69 | r[i] %= 10; |
70 | } |
71 | while (!r[i]) i--; |
72 | while (i >= 0) s += r[i--] + '0'; |
73 | i = tp; |
74 | while (!a[i]) i--; |
75 | while (i >= 0) v += a[i--] + '0'; |
76 | if (v.empty()) v = "0"; |
77 | if (nn == 1) return s; |
78 | if (nn == 2) return v; |
79 | } |
80 | |
81 | int main() |
82 | { |
83 | ios::sync_with_stdio(false); |
84 | cin.tie(0); |
85 | while (cin >> a >> b) |
86 | cout << div(a, b, 1) << endl; |
87 | return 0; |
88 | } |