ACM模板-稳赚个人版(持续更新)

稳赚的沙雕板子

1
2
3
4
5
6
7
8
/*
____ ________
\ \ / /_ | ____
\ Y / | |/ \
\ / | | | \
\___/ |___|___| /
\/
*/

头文件

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
//#include<bits/stdc++.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<sstream>
#include<utility>
#include<algorithm>
#define pf printf
#define INF 0x3f3f3f3f
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scd(x) scanf("%lf", &x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int seed = 1331;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
const double eps = 1e-10;
const double PI = acos(-1.0);

字符串操作

char函数
1
2
3
4
5
6
7
8
9
10
11
char s1[maxn], s2[maxn];
char c; int n;
strcat(s1,s2); // s1+=s2;
strncat(s1,s2,n); // 加上s2的前n个字符
strchr(s1,c); // 返回s1中第一次出现c的位置
strrchr(s1,c); // 返回s1中最后一次出现c的位置
strstr(s1,s2); // 返回s1中第一次出现s2的位置
strcmp(s1,s2); // 比较 能比大小的
strncmp(s1,s2,n); // 比前n个
strcpy(s1,s2); // s1=s2;
strncpy(s1,s2,n); // s1为s2前n个字符
string函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
string s1,s2;
int pos,len; char c;
s1.find(s2);
// 返回值为s2第一次出现在s1的位置
// 若s2不是s1子串返回 string::npos
s1.replace(pos,len,s2);
// s1从pos位开始长度len的子串替换成s2
s1.substr(pos,len);
s1.insert(pos,s2);
s1.insert(pos,s2,len);
// 插入s2的前len个字符
s1.insert(pos,len,c);
// 插入len个c
s1.erase(pos,len);
字典树
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
// 数组版
int trie[maxn][26];
int cnt[maxn];
void insert(char *s){
int u=0;
int len=strlen(s);
rep(i,0,len){
int tmp=s[i]-'a';
if(!trie[u][tmp]){
trie[u][tmp]=++n;
cnt[n]++;
}
else cnt[trie[u][tmp]]++;
u=trie[u][tmp];
}
}
int find(char *s){
int u=0,len=strlen(s);
rep(i,0,len){
int tmp=s[i]-'a';
if(!trie[u][tmp]) return 0;
u=trie[u][tmp];
} return cnt[u];
}


// 指针版
struct trie {
int cnt; trie *next[26];
trie(){ cnt=0; rep(i,0,26) next[i]=NULL; }
};
trie *root,*p;
void insert(char* s){
p=root; int len=strlen(s);
rep(i,0,len){
int tmp=s[i]-'a';
if (p->next[tmp]==NULL) p->next[tmp]=new trie();
p=p->next[tmp]; p->cnt++;
}
}
int find(char* s){
p=root;
int len=strlen(s);
rep(i,0,len){
int tmp=s[i]-'a';
if (p->next[tmp] == NULL)
return 0;
p=p->next[tmp];
} return p->cnt;
}
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
int nex[maxn];
void getnext(char *s){
nex[0]=-1;
int i=0,j=-1,len=strlen(s);
while(i<len){
if(j==-1||s[i]==s[j]){
i++; j++; nex[i]=j;
} else j=nex[j];
}
}
int kmp(char *s1,char *s2){
int i=0,j=0;
int len1=strlen(s1),len2=strlen(s2);
getnext(s2);
while(i<len1 && j<len2){
if(j==-1||s1[i]==s2[j]) { i++; j++; }
else j=nex[j];
if(j==len2) return i-j+1;
} return 0;
}
/* 关于next数组应用如
if(nex[pos] && pos % (pos-nex[pos]) == 0)
即有s的前pos位有(pos / (pos-nex[pos]))个长度为pos-nex[pos]的前缀*/
//求总前缀数 dp
rep(i,1,len+1){
int tmp=nex[i];
while(tmp){ sum++; tmp=nex[tmp]; }
}
EXKMP
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
int nex[maxn], extend[maxn];
void getnext(char s[]){
int aa=0,len=strlen(s);
nex[0]=len;
while(aa<len-1 && s[aa]==s[aa+1]) aa++;
nex[1]=aa; aa=1;
rep(i,2,len){
int p=aa+nex[aa]-1;
int l=nex[i-aa];
if(i+l-1>=p){
int j=(p-i+1)>0?p-i+1:0;
while(i+j<len && s[i+j]==s[j]) j++;
nex[i]=j; aa=i;
}
else nex[i]=l;
}
}
void getextend(char* s1,char* s2){
int aa=0; mst(nex,0); getnext(s2);
int len1=strlen(s1),len2=strlen(s2);
int minl=min(len1,len2);
while(aa<minl && s1[aa]==s2[aa]) aa++;
extend[0]=aa; aa=0;
rep(i,1,len1){
int p=aa+extend[aa]-1, l=nex[i-aa];
if(i+l-1>=p){
int j=(p-i+1)>0?p-i+1:0;
while(i+j<len1 && j<len2 && s1[i+j]==s2[j]) j++;
extend[i]=j; aa=i;
} else extend[i]=l;
}
}
马拉车
1
2
3
4
5
6
7
8
9
10
11
12
int che[2*maxn];
char s[maxn],ma[2*maxn];
void manacher(char* s,int len0){
int len=0; ma[len++]='$'; ma[len++]='#';
rep(i,0,len0) ma[len++]=s[i],ma[len++]='#';
ma[len]=0; int maxx=0,num=0;
rep(i,0,len){
che[i]=maxx>i?min(che[2*num-i],maxx-i):1;
while(ma[i+che[i]]==ma[i-che[i]]) che[i]++;
if(i+che[i]>maxx) maxx=i+che[i],num=i;
}
}
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
// 计每个单词有无出现 注释里写记单词数的 以*开头
int ans;
struct node{
node* next[26]; // 最大100够的 所有题
node* fail;
int end; // 在单词末尾做标记
//* int id;
node(){
end=0; //* id=0;
fail=0;
mst(next,0);
}
};
node* root;
// 建字典树
//* int tot;
void insert(char* s){
node* p=root;
int len=strlen(s);
rep(i,0,len){
int tmp=s[i]-'a';
if(p->next[tmp]==NULL) p->next[tmp]=new node();
p=p->next[tmp];
}
p->end++;
//* p->id=++tot;
}
queue<node*>q;
// fail数组:root指向NULL 没出现过的指向root 出现过的指向前一个
void getfail(){
root->fail=NULL;
q.push(root);
while(!q.empty()){
node* fr=q.front(); q.pop();
rep(i,0,26) if(fr->next[i]){
node* tem=fr->fail;
while(tem){
if(tem->next[i]){
fr->next[i]->fail=tem->next[i];
break;
} tem=tem->fail;
}
if(tem==NULL) fr->next[i]->fail=root;
q.push(fr->next[i]);
}
}
}
//* num[maxn], mark[maxn], cnt;
void ac_auto(char* s){
node* p=root;
int len=strlen(s);
rep(i,0,len){
int tmp=s[i]-'a';
while(!p->next[tmp] && p!=root) p=p->fail;
p=p->next[tmp];
if(!p) p=root;
node* tem=p;
while(tem!=root){
if(tem->end>=0){
ans+=tem->end;
tem->end=-1; // 出现过了第二次遇到不再统计
}
else break;
/* if(tem->id){
*if(!mark[tem->id])
*num[cnt++]=tem->id;
// num按在s串中出现顺序存id
*mark[tem->id]++;
//mark存出现与否 顺便存次数
}*/
tem=tem->fail;
}
}
}
后缀数组
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
int s[maxn];
int sa[maxn],rk[maxn];
int height[maxn];
int t1[maxn],t2[maxn],c[maxn];
int best[20][maxn];
char ss[maxn];
void getsa(int *s,int n,int m){
int *x=t1,*y=t2;
rep(i,0,m) c[i]=0;
rep(i,0,n) c[x[i]=s[i]]++;
rep(i,1,m) c[i]+=c[i-1];
dep(i,n-1,0) sa[--c[x[i]]]=i;
for(int k=1;k<=n;k<<=1){
int p=0;
rep(i,n-k,n) y[p++]=i;
rep(i,0,n) if(sa[i]>=k) y[p++]=sa[i]-k;
rep(i,0,m) c[i]=0;
rep(i,0,n) c[x[y[i]]]++;
rep(i,1,m) c[i]+=c[i-1];
dep(i,n-1,0) sa[--c[x[y[i]]]]=y[i];
swap(x,y);
p=1; x[sa[0]]=0;
rep(i,1,n) x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
if(p>=n) break; m=p;
}
}
void getheight(int n){
int k=0;
rep(i,1,n+1) rk[sa[i]]=i;
rep(i,0,n){
if(k) k--;
int j=sa[rk[i]-1];
while(s[i+k]==s[j+k]) k++;
height[rk[i]]=k;
}
}
后缀自动机
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
struct SAM{
int next[maxn<<1][26],link[maxn<<1],len[maxn<<1];
int a[maxn<<1],id[maxn<<1],right[maxn<<1];
int tot,root,last;
inline void init(){
rep(i,0,tot+1) mst(next[i],0),right[i]=0;
mst(len,0); mst(link,0); tot=last=root=1;
}
inline void extend(int x){
int p=last,now=++tot; right[now]=1; len[now]=len[p]+1;
while(p&&!next[p][x]) next[p][x]=now,p=link[p];
if(!p) link[now]=root;
else{
int q=next[p][x];
if(len[q]==len[p]+1) link[now]=q;
else{
int tmp=++tot;
memcpy(next[tmp],next[q],sizeof(next[q]));
link[tmp]=link[q]; link[q]=link[now]=tmp; len[tmp]=len[p]+1;
while(p&&next[p][x]==q) next[p][x]=tmp,p=link[p];
}
} last=now;
}
inline void solve(){
// 拓扑排序
rep(i,1,tot+1) ++a[len[i]];
rep(i,1,tot+1) a[i]+=a[i-1];
rep(i,1,tot+1) id[a[len[i]]--]=i;
}
}sam;
最大最小表示法
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
int getmin(char *s){
int len=strlen(s);
int i=0,j=1,k=0;
while(i<len&&j<len&&k<len){
int tmp=s[(i+k)%len]-s[(j+k)%len];
if(!tmp) k++;
else{
if(tmp>0) i+=k+1; else j+=k+1;
if(i==j) j++; k=0;
}
}
return min(i,j);
}
int getmax(char *s){
int len=strlen(s);
int i=0,j=1,k=0;
while(i<len&&j<len&&k<len){
int tmp=s[(i+k)%len]-s[(j+k)%len];
if(!tmp) k++;
else{
if(tmp<0) i+=k+1; else j+=k+1;
if(i==j) j++; k=0;
}
}
return min(i,j);
}
回文树
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
// 回文树初始节点01 表示偶/奇数长度串的根节点
struct PAM{
struct node{
int child[26],cnt,fail,num,len;
}tt[maxn];
int last,n,tot;
char s[maxn];
inline void clear(){
rep(i,0,tot+1){
mst(tt[i].child,0);
tt[i].cnt=tt[i].fail=tt[i].len=tt[i].num=0;
}
last=n=0; tt[0].fail=tot=1; tt[1].len=-1;
}
inline int getfail(int x){
while(s[n-tt[x].len-1]!=s[n]) x=tt[x].fail;
return x;
}
inline void add(char ch){
s[++n]=ch;
int cur=getfail(last);
if(!tt[cur].child[ch-'a']){
int now=++tot;
tt[now].len=tt[cur].len+2;
int p=getfail(tt[cur].fail);
tt[now].fail=tt[p].child[ch-'a'];
tt[cur].child[ch-'a']=now;
tt[now].num=tt[tt[now].fail].num+1;
}
last=tt[cur].child[ch-'a'];
++tt[last].cnt;
}
inline void count(){
dep(i,tot,0) tt[tt[i].fail].cnt+=tt[i].cnt;
}
}pam;

自闭图论

稳定婚姻问题
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 b[maxn][maxn],g[maxn][maxn];
// b 每个男生按好感位次排下来的女生
// g 每个女生对应每个男生的好感度
int bm[maxn],gm[maxn];
// 对应异性号数
int vis[maxn][maxn];
void stable_marriage(){
mst(bm,-1); mst(gm,-1); mst(vis,0);
queue<int> q;
rep(i,1,n+1) q.push(i);
int fr,nex;
while(!q.empty()){
fr=q.front(); q.pop();
rep(i,1,m+1){
nex=b[fr][i];
if(vis[fr][nex]) continue; vis[fr][nex]=1;
if(gm[nex]==-1){
gm[nex]=fr; bm[fr]=nex;
break;
}
else if(g[nex][gm[nex]]>g[nex][fr]){
q.push(gm[nex]);
gm[nex]=fr; bm[fr]=nex;
break;
}
}
}
}
二分匹配匈牙利算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int ans;
int mp[maxn][maxn];
int vis[maxn],line[maxn];
void init(){
ans=0; mst(mp,0); mst(line,0);
}
int dfs(int x){
rep(i,1,n+1) if(!vis[i]&&mp[i][x]){
vis[i]=1;
if(!line[i]||dfs(line[i])) {
line[i]=x; return 1;
}
}
return 0;
}
void solve(){
rep(i,1,n+1){ mst(vis,0); if(dfs(i)) ans++; }
}
强连通tarjan
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
int cnt,id;
int dfn[maxn],low[maxn];
int ins[maxn],scc[maxn];
stack<int>s;
vector<int>vv[maxn];
void init(){
cnt=id=0;
mst(dfn,0); mst(low,0);
mst(ins,0); mst(scc,0);
rep(i,1,n+1) vv[i].clear();
}
void tarjan(int x){
dfn[x]=low[x]=++id; ins[x]=1;
s.push(x);
rep(i,0,vv[x].size()){
int tmp=vv[x][i];
if(!dfn[tmp]){ tarjan(tmp); low[x]=min(low[x],low[tmp]); }
else if(ins[tmp]) low[x]=min(low[x],dfn[tmp]);
}
if(low[x]==dfn[x]){
cnt++; do{
int tmp=s.top(); s.pop();
ins[tmp]=0; scc[tmp]=cnt;
} while(x!=tmp);
}
}
void solve() {
rep(i,1,n+1) if(!dfn[i]) tarjan(i);
mst(ins,0); mst(out,0);
rep(i,1,n+1) rep(j,0,vv[i].size())
if(scc[i]!=scc[vv[i][j]]){
ins[scc[vv[i][j]]]++; out[scc[i]]++;
}
}

数据结构

并查集
1
2
3
4
5
6
7
8
int find(int x){
if(vis[x]==x) return x;
else return vis[x]=find(vis[x]);
}
void change(int x, int y){
int c=find(x),d=find(y);
if(c!=d) vis[c]=d;
}
树状数组
1
2
3
4
5
6
7
8
9
10
int tree[maxn];
int lowbit(int i){ return i&(-i); }
void update(int i,int x){
for(;i<=maxn;i+=lowbit(i)) tree[i]+=x;
}
int sum(int n){
int ans=0;
for(int i=n;i>0;i-=lowbit(i)) ans+=tree[i];
return ans;
}
线段树
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
// 单点更新,加*区间更新
#define lson (rt<<1)
#define rson ((rt<<1)|1)
#define mid ((begin+end)>>1)
int segtree[4*maxn];
//* int lazy[4*maxn];
void pushup(int rt){
segtree[rt]=segtree[lson]+segtree[rson];
}
/** void pushdown(int rt,int begin,int end){
if (!lazy(rt)) return;
segtree[lson]+=(mid-begin+1)*lazy[rt];
segtree[rson]+=(end-mid)*lazy[rt];
lazy[lson]+=lazy[rt];
lazy[rson]+=lazy[rt];
lazy[rt]=0;
}*/
void build(int rt,int begin,int end){
//* lazy[rt]=0;
if(begin==end){ sc(segtree[rt]); return; }
build(lson,begin,mid);
build(rson,mid+1,end);
pushup(rt);
}
void update(int rt,int begin,int end,int pos,int a){
if(pos<begin||pos>end) return;
if(begin==end){ segtree[rt]+=a; return; }
update(lson,begin,mid,pos,a);
update(rson,mid+1,end,pos,a);
pushup(rt);
}
/** void update(int rt,int begin,int end,int left,int right,int a){
if(left>end||right<begin) return;
if(left<=begin&&right>=end){
segtree[rt]+=(end-begin+1)*a;
lazy[rt]+=a; return;
}
pushdown(rt,begin,end);
update(lson,begin,mid,left,right,a);
update(rson,mid+1,end,left,right,a);
pushup(rt);
}*/
int solve(int rt,int begin,int end,int left,int right){
if(left>end||right<begin) return 0;
if(left<=begin&&right>=end) return segtree[rt];
//* pushdown(rt,begin,end);
int ans=0;
ans+=solve(lson,begin,mid,left,right);
ans+=solve(rson,mid+1,end,left,right);
return ans;
}

DP

背包
数位dp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int a[20]; // 位数 一般题目最大1e18
ll dp[20][state];
ll dfs(int pos,int pre,/*int state,*/int limit){
// pos位数 pre之前状态 与dp数组对应
// state各种情况包括前导零 具体看题目 limit前一位限制
if(pos == -1) return 1; // 计数,具体看题目
if(!limit&&dp[pos][pre]!=-1/*&&!state*/) return dp[pos][pre];
int last=limit?a[pos]:9;
ll ans=0; rep(i,0,last+1){
if(...) ans+=dfs(pos-1,...,/*...,*/limit&&i==a[pos]);
else(...)
}
if(!limit/*&&!state*/) dp[pos][pre]=ans;
return ans;
}
ll solve(ll x){
mst(dp -1);
// mst可能超时 t组数据什么的只用最开始mst一次
int pos=0;
while(x){ a[pos++]=x%10; x/=10; }
return dfs(pos-1,0,/*...,*/1);
}

数学

模逆元
1
2
3
4
5
6
7
8
void exgcd(ll a,ll b,ll &x,ll &y){
if(!b){ x=1; y=0; return; }
exgcd(b,a%b,y,x); y-=(a/b)*x; return;
}
ll inv(ll a,ll p){
ll x,y; exgcd(a,p,x,y);
return (x%p+p)%p;
}
组合数
1
2
3
4
5
6
7
8
9
10
11
void exgcd(ll a,ll b,ll &x,ll &y){
if(!b){ x=1,y=0; return; }
else{ exgcd(b,a%b,y,x); y-=(a/b)*x; return; }
}
ll C(int s,int x){
if(s>x-s) s=x-s;
ll ans=1,tmp=1,xx,y;
rep(i,1,s+1) ans=ans*(x-i+1)%mod,tmp=tmp*i%mod;
exgcd(tmp,mod,xx,y); ans=(ans*xx%mod+mod)%mod;
return ans;
}
1
2
3
4
5
6
ll qpow(int a,int b){
ll ans=1; while(b){
if(b&1) ans=ans*a%mod;
b>>=1; a=a*a%mod;
} return ans;
}
矩阵快速幂
1
// 记得来换板子
高精度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 想不到吧是Java
import java.math.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
// 常见函数
BigInteger.valueOf(); // 大数互转,int转大数,string转大数
BigInteger array[]=new BigInteger[maxn];
add(); subtract(); multiply(); divide();
compareTo(); mod(); pow(); gcd();
System.out.println(a.stripTrailingZeros().toPlainString()); // 实数的输出去除末尾0
Arrays.sort(a,0,n); // 数组排序
}
}
}
中国剩余定理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ll a[maxn],r[maxn];
ll exgcd(ll a,ll b,ll &x,ll &y){
if(!b){ x=1; y=0; return a; }
else{
ll ans=exgcd(b,a%b,y,x);
y-=(a/b)*x; return ans;
}
}
void excrt(){
ll m1,r1,m2,r2;
ll x,y,t,c,d;
m1=a[0],r1=r[0];
rep(i,1,tot){
m2=a[i],r2=r[i];
c=r2-r1; d=exgcd(m1,m2,x,y);
t=m2/d; x*=c/d; x=(x%t+t)%t;
r1=x*m1+r1; m1=m1*m2/d;
r1=(r1%m1+m1)%m1;
}
}
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
// 大数版
import java.math.*;
import java.util.*;
public class Main {
public static BigInteger[] exgcd(BigInteger a,BigInteger b){
BigInteger ans;
BigInteger[] result=new BigInteger[3];
if(b.compareTo(BigInteger.ZERO)==0){
result[0]=a; result[1]=BigInteger.ONE; result[2]=BigInteger.ZERO;
return result;
}
BigInteger[] tmp=exgcd(b,a.mod(b));
ans=tmp[0]; result[0]=ans; result[1]=tmp[2];
result[2]=tmp[1].subtract((a.divide(b).multiply(tmp[2])));
return result;
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
BigInteger a[]=new BigInteger[105];
BigInteger r[]=new BigInteger[105];
int n; n=sc.nextInt();
for(int i=0;i<n;i++){
a[i]=sc.nextBigInteger();
r[i]=sc.nextBigInteger();
}
BigInteger m1,m2,r1,r2,t,c;
BigInteger[] d;
m1=a[0]; r1=r[0];
for(int i=1;i<n;i++){
m2=a[i]; r2=r[i]; c=r2.subtract(r1); d=exgcd(m1,m2);
if(c.mod(d[0]).compareTo(BigInteger.ZERO)!=0){
System.out.println("-1");
return;
}
t=m2.divide(d[0]); d[1]=d[1].multiply(c.divide(d[0])).mod(t);
r1=d[1].multiply(m1).add(r1); m1=m1.multiply(t);
r1=r1.mod(m1);
}
d=exgcd(BigInteger.ONE,m1);
if(r1.mod(d[0]).compareTo(BigInteger.ZERO)!=0){
System.out.println("-1");
return;
}
t=m1.divide(d[0]); d[1]=d[1].multiply(r1.divide(d[0])).mod(t);
System.out.println(d[1]);
}
}
打表素数及莫比乌斯函数
1
2
3
4
5
6
7
8
9
10
11
12
13
int p[maxn],u[maxn],vis[maxn];
int pn;
void make_table(){
mst(vis,0); u[1]=1; pn=0;
rep(i,2,maxn){
if(!vis[i]){ p[pn++]=i; u[i]=-1; }
for(int j=0;j<pn&&i*p[j]<maxn;j++){
vis[i*p[j]]=1;
if(i%p[j]) u[i*p[j]]=-u[i];
else { u[i*p[j]]=0; break; }
}
}
}
博弈
1
2
3
4
5
6
7
/* 巴什博弈:一堆物品n两人轮流取物,一次最多m
根据n % (m+1)是否为零判断胜者
威佐夫博奕:两堆物品a, b两人轮流取物,一次只能在一堆任意取或是两堆取同样多 //默认a<b
根据(int)((double)(1.0+sqrt(5.0))/2.0)*(b-a))是否等于a判断胜者
Fibonacci博弈:一堆物品n,两人轮流取物,每一次能取的个数是上一次的两倍以内,最后取完胜
n为Fibonacci数时先手败 */
// 以下sg函数 打表 dfs
斐波那契求循环节
1
2
3
4
5
6
7
/*
给定一个数n 求n的斐波那契循坏节长度len
·n为质数且5是模n的二次剩余 len为(n-1)的因子
·n为质数且5不为模n的二次剩余 len为(2n+2)的因子
·n为质数p的k次 len为lenp*p^(k-1)
·n分解为质因数 len为每个质因数循环节长度的lcm
*/

计算几何

二维几何
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
// 一般形式
// 直线L上两点(x1,y1),(x2,y2);
// 直线外一点P(x0,y0);
// L表示为Ax+By+C=0;
double A,B,C;
A=y2-y1; B=x1-x2; C=x2*y1-x1*y2;
// 点到直线距离d
double d=fabs(A*x0+B*y0+C)/sqrt(A*A+B*B);
// 点到直线垂足H(x, y)
double x,y;
x=(B*B*x0-A*B*y0-A*C)/(A*A+B*B);
y=(-A*B*x0+A*A*y0-B*C)/(A*A+B*B);
// 点关于直线的对称点P'(_x, _y);
double k,_x,_y;
k=-2*(A*x0+B*y0+C)/(A*A+B*B); _x=x0+k*A; _y=y0+k*B;
// 求三角形内整数点个数
// 三角形三个顶点坐标(x1, y1), (x2, y2), (x3, y3) 都为整数点
int t1,t2,t3; // 三边上整数点个数
t1=gcd(abs(x1-x2),abs(y1-y2));
t2=gcd(abs(x3-x2),abs(y3-y2));
t3=gcd(abs(x1-x3),abs(y1-y3));
int num; // 三角形内整数点
num=abs((x2-x1)*(y3-y2)-(x3-x2)*(y2-y1))/2;
num-=(t1+t2+t3)/2-1;
// 皮克定理
// 一个格点多边形有 S=a+b / 2-1;
// S面积 a内部格点数 b边上格点数

// 结构体形式
struct point{
double x, y;
point(double a=0,double b=0){ x=a,y=b; }
}; // 点
struct line{
point s,e;
line(point a,point b){ s=a,e=b; }
line(){}
}; // 线
double getdis(point a, point b){
double xx=a.x-b.x,yy=a.y-b.y;
return sqrt(xx*xx+yy*yy);
} // 两点距离
double multi(point a,point b,point c){
double xa,ya,xb,yb;
xa=b.x-a.x; ya=b.y-a.y;
xb=c.x-b.x; yb=c.y-b.y;
return xa*xb+ya*yb;
} // 点乘
double multi(point a,point b,point c){
double xa,ya,xb,yb;
xa=b.x-a.x; ya=b.y-a.y;
xb=c.x-b.x; yb=c.y-b.y;
return xa*yb-xb*ya;
} // 叉乘
int judge(line a,line b){
if (max(a.s.x,a.e.x)>=min(b.s.x, b.e.x) &&
max(a.s.y,a.e.y)>=min(b.s.y, b.e.y) &&
max(b.s.x,b.e.x)>=min(a.s.x, a.e.x) &&
max(b.s.y,b.e.y)>=min(a.s.y, a.e.y) &&
multi(a.s,b.s,b.e)*multi(a.e,b.s,b.e)<=0
&& multi(b.s,a.s,a.e)*multi(b.e,a.s,a.e)<=0
) return 1;
else return 0;
} // 判断线段是否相交
double area(){
double ans=0,tmp;
p[n].x=p[0].x; p[n].y=p[0].y;
rep(i,0,n) { tmp=p[i].x*p[i+1].y-p[i+1].x*p[i].y; ans+=tmp; }
return ans/2;
} // 多边形面积
double gx, gy;
void find_gra(){
double area=0, tmp;
rep(i,1,n-1){
tmp=(p[i].x-p[0].x)*(p[i+1].y-p[0].y)-(p[i+1].x-p[0].x)*(p[i].y-p[0].y); area+=tmp;
gx+=(p[0].x+p[i].x+p[i+1].x)*tmp;
gy+=(p[0].y+p[i].y+p[i+1].y)*tmp;
} gx=gx/3/area, gy=gy/3/area;
} // 求重心坐标
二维凸包
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 以下凸包Graham
int top;
point p[maxn], s[maxn];
int iszero(double x){ return fabs(x) < eps; }
int cmp(point a,point b){
double tt=multi(a,b,p[0]);
if(tt>0||iszero(tt)&&getdis(a,p[0])<getdis(b,p[0])) return 1;
return 0;
}
void graham() {
point tmp;
rep(i,1,n) if(p[i].y<p[0].y||(p[i].y==p[0].y&&p[i].x<p[0].x)) swap(p[0],p[i]);
sort(p+1,p+n,cmp);
s[0]=p[0]; s[1]=p[1]; s[2]=p[2]; top=2;
rep(i,3,n){
while(top>=2&&multi(s[top-1],s[top],p[i])<=eps) top--;
s[++top]=p[i];
}
}

其他

STL操作
1
2
3
map<int,int>::reverse_iterator rit;
for(rit=aaa.rbegin();rit!=aaa.rend();rit++);
// 反向迭代器
读入优化
1
std::ios::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);
读入挂
1
2


给逆元求概率
1
2
3
4
5
6
7
8
9
10
11
12
void solve(ll pa,ll xa,ll pb,ll xb,ll &a,ll &b){
ll tmp=(pa-1)/xa;
if(tmp+1<=pb/xb){ a=tmp+1; b=1; return; }
pa-=tmp*xa; pb-=tmp*xb;
solve(xb,pb,xa,pa,b,a); a+=tmp*b;
}
void getsample(){
ll p,x,a,b; scl(p); scl(x);
// p模的质数 x结果
solve(p,x,p,x-1,a,b);
ll c=x*a-p*b; pf("%lld/%lld\n",c,a);
}