模板整理

发表于 | 更新于: | 分类于 | | 阅读数

Collected By Hope_Y…

STL

部分来自QuincyTan

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

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>//用tree
#include<ext/pb_ds/hash_policy.hpp>//用hash
#include<ext/pb_ds/trie_policy.hpp>//用trie
#include<ext/pb_ds/priority_queue.hpp>//用priority_queue
using namespace __gnu_pbds;


//hash表 用法类似map,时间复杂度O(n)
cc_hash_table<int,bool> h; //拉链法
gp_hash_table<int,bool> h; //探测法
h.clear() //初始化

// 平衡树 以下操作时间复杂度均为O(logn)
struct team{
    int t,p,id;
    bool operator <(const team&hs)const{
        return t!=hs.t?t>hs.t:p!=hs.p?p<hs.p:id<hs.id;
    }
}
typedef tree<team,null_type,less<team>,rb_tree_tag,tree_order_statistics_node_update> rebtree;
null_type //无映射(低版本g++为null_mapped_type)
less<T> //从小到大排序
rb_tree_tag //红黑树
tree_order_statistics_node_update //更新方式
tr.insert(x); //插入;
tr.erase(x); //删除;
tr.order_of_key(x); //求比x小的个数 rank=res+1
tr.find_by_order(k-1); //找k小值,返回迭代器 k值非法，则会返回end()
tr.join(b); //将b并入tr,前提是两棵树类型一样且没有重复元素
tr.split(v,b); //分裂,key小于等于v的元素属于tr,其余的属于b
tr.lower_bound(x); //返回第一个>=x的元素的迭代器 x的前驱 *--tr.lower_bound(x)
tr.upper_bound(x); //返回第一个>x的元素的迭代器  x的后继 *tr.lower_bound(x)
//迭代器支持++,--操作


//堆
priority_queue<int,greater<int>,TAG> Q; //注意命名空间别和std中的那个重了
/*其中的TAG为类型，有以下几种：
pairing_heap_tag //最快
thin_heap_tag
binomial_heap_tag
rc_binomial_heap_tag
binary_heap_tag
*/
struct node{
    int x;
    node(){}
    node(int x):x(x){}
    friend bool operator < (node i,node j){
        return i.x>j.x; // 队首元素是小的，即小的的优先级大，这个在sort的bool函数有点差别
    }
};
priority_queue<int,vector<int>,greater<int> > q;/////采取最小优先策略，即按从小到大的顺序排列
priority_queue<int,vector<int>,less<int> > q;  ////采取最大优先策略，即按从大到小的顺序排列


__gnu_pbds::priority_queue<int>::point_iterator it;  //支持迭代器
Q.push(x); //push()会返回迭代器,用一个迭代器数组保存所有进队列的元素的迭代器，就可以持久化操作
Q.pop();
Q.top();
Q.join(b);
Q.empty();
Q.size();
Q.modify(it,6);
Q.erase(it);

sort //排序中的bool函数的使用

bool cmp(int x,int y){
    return x<y;  //就是比较x元素和y元素，如果表达式为真，就不交换
}
//但是呢，当你要自定义某个元素的优先级，比如说2排最前面
bool cmp(int x,int t){
    return x==2; // 否则y==2
}

//rope 时间复杂度O(logN)
#include <ext/rope>
using namespace __gnu_cxx;
rope<int> r;
push_back(x)    //在末尾添加x
insert(pos,x)   //在pos插入x
erase(pos,x)    //从pos开始删除x个
copy(pos,len,x) //从pos开始到pos+len为止用x代替
replace(pos,x)  //从pos开始换成x
substr(pos,x)   //提取pos开始x个
at(x)/[x]   //访问第x个元素
//可持久化 O(1)复制根节点
rope<char> *his[maxn];
his[0] = new rope<char>();
his[i] = new rope<char>(*his[i-1]);



//list 合并操作
void merge(list <T> & x)
//将链表x合并进来并清空x,要求链表自身和x都是有序的
void splice ( iterator position, list<T,Allocator>& x );
//在position后把list&x所有的元素到剪接到要操作的list对象
void splice ( iterator position, list<T,Allocator>& x, iterator it );
//只会把it的值剪接到要操作的list对象中
void splice ( iterator position, list<T,Allocator>& x, iterator first, iterator last );
//把first到last剪接到要操作的list对象中

//O(n)查询第k大
nth_element(a+1,a+k,a+1+n);

deque//双向队列
pop_back() //删除尾部的元素 
pop_front() //删除头部的元素 
push_back() //在尾部加入一个元素 
push_front() //在头部加入一个元素 
    
int read(){
    int x=0; bool f=0; char ch=getchar();
    while (ch<'0' || '9'<ch) f|=ch=='-', ch=getchar();
    while ('0'<=ch && ch<='9') x=x*10+ch-'0', ch=getchar();
    return f?-x:x;
}
void print(int x){
    if(x<0){
        putchar('-');
        x = -x;
    }
    if(x>9) print(x / 10);
    putchar(x % 10 + '0');
}

inline long long multi(long long x,long long y,long long mod){
	long long tmp=(x*y-(long long)((long double)x/mod*y+1.0e-8)*mod);
	return tmp<0 ? tmp+mod : tmp;
}

动态规划

引入

LIS问题：最长上升子序列

$ dp_i $表示以$ i $结尾的最长上升子序列，$ dp_i=max_{0 \leq j <i,a_j<a_i}(dp_j+1) $。

$O(nlogn)$的解法( )：

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>
using namespace std;
const int maxn=1e5+5;
int a[maxn];
int n;
int lis[maxn];
int len=1;
int Find(int x){
    int l=1,r=len,m;
    while(l<r){
        m=l+(r-l)/2;
        if(lis[m]>=a[x]){//这里若去掉等号即为 非严格递增序列 
            r=m;
        } 
        else{
            l=m+1;
        }
    }
    return l;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    lis[1]=a[1];
    for(int i=2;i<=n;i++){
        if(a[i]>lis[len]){
            lis[++len]=a[i];
        }
        else{
            int pos=Find(i);
            lis[pos]=a[i];//同时记录了路径
        }
    }
    printf("%d\n",len);
}

LCS问题：最长公共子序列

$dp_{i,j}$表示前缀子串中$a_{1-i}$与$b_{1-j}$的最长公共子序列，$dp_{i,j} = max({dp_{i-1,j},dp_{i,j-1},if(a_i = b_j) dp_{i-1,j-1}+1})$

$O(nlogn)$的解法：

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int n,len=0;
int lis[maxn];
int a[maxn];
int b[maxn];
int loc[maxn];
int Find(int x){
    int l=1,r=len,m;
    while(l<r){
        m=l+(r-l)/2;
        if(lis[m]>=x){
            r=m;
        }
        else  l=m+1;
    }
    return l;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        scanf("%d",&b[i]);
        loc[b[i]]=i;
    }
    for(int i=1;i<=n;i++){
        b[i]=loc[a[i]];
    }
    if(n!=0)lis[++len]=b[1];
    for(int i=2;i<=n;i++){
        if(b[i]>lis[len]){
            lis[++len]=b[i];
        }
        else{
            int pos=Find(b[i]);
            lis[pos]=b[i];
        }
    }
    printf("%d\n",len);
}

背包dp

01背包

$n$个物品放入容积为$M$的背包，第$i$个物品的容量为$v_i$，价值为$w_i$，问最大价值。

1
2
3
4
5
6
7
8
9
10
int dp[maxn];
memset(dp,-inf,sizeof dp);
dp[0]=0;
for(int i=1; i<=n; i++){
    for(int j=M; j>=v[i]; j--){
        dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
    }
}
int ans=0;
for(int i=0; i<=M; i++) ans=max(ans,dp[i]);
完全背包

在01背包的基础上，每个物品是无限多的。

1
2
3
4
5
6
7
8
9
10
int dp[maxn];
memset(dp,-inf,sizeof dp);
dp[0]=0;
for(int i=1; i<=n; i++){
    for(int j=v[i]; j<=M; j++){
        dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
    }
}
int ans=0;
for(int i=0; i<=M; i++) ans=max(ans,dp[i]);
多重背包

在01背包的基础上，每种物品的数量是$c_i$个。

我们将所有物品全部摊开，相当于$\sum_{i=1}^{n} {c_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
//输入
int n;
int W; //总容量
int w[MAX_N]; //每种物品的容量
int v[MAX_N]; //每种物品的价值
int m[MAX_N]; //每种物品的数量
int dp[MAX_N+1];
int deq[MAX_N+1];//双端队列，保存下标
int deqv[MAX_N+1];//双端队列，保存值
void solve(){
    for(int i=0;i<n;i++){
        for(int a=0;a<w[i];a++){//把每个分组都打一遍
            int s=0;//初始化双端队列头尾
            int t=0;
            for(int j=0;j*w[i]+a<=W;j++){//每组第j个元素
                int val=dp[j*w[i]+a]-j*v[i];
                while(s<t && deqv[t-1]<=val)//直到不改变单调性
                    t--;
                deq[t]=j;
                deqv[t]=val;
                t++;
                //利用队头求出dp
                dp[j*w[i]+a]=deqv[s]+j*v[i];
                if(deq[s]==j-m[i])s++;//检查过期
            }
        }
    }
}
分组背包

给定$n$组物品，第$i$组有$c_i$个物品，第$i$组的第$j$个物品的体积为$v_{i,j}$，价值为$w_{i,j}$，容积$M$的背包，求装得下的最大价值。

1
2
3
4
5
6
7
8
9
10
11
12
int dp[maxn];
memset(dp,-inf,sizeof dp);
dp[0]=0;
for(int i=1; i<=n; i++){
    for(int j=M; j>=0; j--){
        for(int k=1; k<=c[i]; k++){
            if(j>=v[i][k]) dp[j]=max(dp[j],dp[j-v[i][k]]+w[i][k]);
        }
    }
}
int ans=0;
for(int i=0; i<=M; i++) ans=max(ans,dp[i]);

数位dp

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
typedef long long ll;
int a[20];
ll dp[20][state];//不同题目状态不同
ll dfs(int pos,/*state变量*/,bool lead/*前导零*/,bool limit/*数位上界变量*/){
    //不是每个题都要判断前导零
    //递归边界，既然是按位枚举，最低位是0，那么pos==-1说明这个数我枚举完了
    if(pos==-1)
        return 1;/*这里一般返回1，表示你枚举的这个数是合法的，
        那么这里就需要你在枚举时必须每一位都要满足题目条件，
        也就是说当前枚举到pos位，一定要保证前面已经枚举的数位是合法的。
        不过具体题目不同或者写法不同的话不一定要返回1 */
    //第二个就是记忆化(在此前可能不同题目还能有一些剪枝)
    if(!limit && !lead && dp[pos][state]!=-1)
        return dp[pos][state];
    int up=limit?a[pos]:9;//根据limit判断枚举的上界up;这个的例子前面用213讲过了
    ll ans=0;
    //开始计数
    for(int i=0; i<=up; i++){ //枚举，然后把不同情况的个数加到ans就可以了
        if()
            ...
            else if()
                ...
                ans+=dfs(pos-1,/*状态转移*/,lead && i==0,limit && i==a[pos]) //最后两个变量传参都是这样写的
                     /*这里还算比较灵活，不过做几个题就觉得这里也是套路了
                     大概就是说，我当前数位枚举的数是i，然后根据题目的约束条件分类讨论
                     去计算不同情况下的个数，还有要根据state变量来保证i的合法性，比如题目
                     要求数位上不能有62连续出现,那么就是state就是要保存前一位pre,然后分类，
                     前一位如果是6那么这意味就不能是2，这里一定要保存枚举的这个数是合法*/
            }
    //计算完，记录状态
    if(!limit && !lead)
        dp[pos][state]=ans;
    /*这里对应上面的记忆化，在一定条件下时记录，保证一致性，当然如果约束条件不需要考虑lead，这里就是lead就完全不用考虑了*/
    return ans;
}
ll solve(ll x){
    int pos=0;
    while(x){//把数位都分解出来
        a[pos++]=x%10;
        x/=10;
    }
    return dfs(pos-1/*从最高位开始枚举*/,/*一系列状态 */,true,true);
    //刚开始最高位都是有限制并且有前导零的，显然比最高位还要高的一位视为0嘛
}
int main(){
    ll le,ri;
    while(~scanf("%lld%lld",&le,&ri)){
        //初始化dp数组为-1,这里还有更加优美的优化,后面讲
        printf("%lld\n",solve(ri)-solve(le-1));
    }
}

区间dp

1
2
3
4
5
6
7
8
9
10
dp[i][i]=1;
for(int len=2; len<=n; len++){//长度
    for(int i=1; i<=n; i++){
        int j=i+len-1;
        if(j>n) break;
        for(int k=i; k<j; k++){//枚举断点
            //
        }
    }
}

树形dp

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
//求树的直径和第二长的路径
#include<bits/stdc++.h>
#define MAXN 10010
using namespace std;
struct edge{
    int to,next,v;
}edges[MAXN*2];
int dp[MAXN][3],ecnt,head[MAXN],N,x,y;
void add(int from,int to,int x){
    edges[++ecnt].to=to;
    edges[ecnt].next=head[from];
    edges[ecnt].v=x;
    head[from]=ecnt;
}
void init(){
    memset(head,0,sizeof(head));
    memset(dp,0,sizeof(dp));
    ecnt=0;
}
void dfs(int root,int par){
    for(int i=head[root]; i!=0; i=edges[i].next){
        int son=edges[i].to;
        if(son!=par){
            dfs(son,root);
            if(dp[son][0]+edges[i].v >= dp[root][0]){
                dp[root][1]=dp[root][0];
                dp[root][0]=dp[son][0]+edges[i].v;
            }
            else dp[root][1]=max(dp[root][1],dp[son][0]+edges[i].v);
        }
    }
}

斜率优化dp

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
//HDU3507
#include<bits/stdc++.h>
using namespace std;
int dp[500005];
int q[500005];
int sum[500005];
int head,tail,n,m;
int getDP(int i,int j){
    return dp[j]+m+(sum[i]-sum[j])*(sum[i]-sum[j]);
}
int getUP(int j,int k){   //yj-yk的部分
    return dp[j]+sum[j]*sum[j]-(dp[k]+sum[k]*sum[k]);
}
int getDOWN(int j,int k){  //xj-xk的部分
    return 2*(sum[j]-sum[k]);
}
int main(){
    int i;
    while(scanf("%d%d",&n,&m)==2){
        for(i=1; i<=n; i++)
            scanf("%d",&sum[i]);
        sum[0]=dp[0]=0;
        for(i=1; i<=n; i++)
            sum[i]+=sum[i-1];
        head=tail=0;
        q[tail++]=0;
        for(i=1; i<=n; i++){
            while(head+1<tail &&
            getUP(q[head+1],q[head])<=
            sum[i]*getDOWN(q[head+1],q[head]))
                head++;
            dp[i]=getDP(i,q[head]);
            while(head+1<tail &&
            getUP(i,q[tail-1])*getDOWN(q[tail-1],q[tail-2])<=
            getUP(q[tail-1],q[tail-2])*getDOWN(i,q[tail-1]))
                tail--;
            q[tail++]=i;
        }
        printf("%d\n",dp[n]);
    }
}

图论

最短路

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
struct node{
    int val,id;
    node(int id,int val):id(id),val(val) {}
    bool operator <(const node &hs)const{
        return val>hs.val;
    }
};
struct edge{
    int next,to,w;
}e[maxm*2];
int head[maxn],cnt;

void addedge(int u,int v,int w){
    e[++cnt]=edge{head[u],v,w};
    head[u]=cnt;
}

int dis[maxn],vis[maxn];
void dijkstra(int from){
    for(int i=1;i<=n;i++){
        dis[i]=INF;
        vis[i]=0;
    }
    priority_queue<node>q;
    q.push(node(from,0));
    dis[from]=0;
    while(!q.empty()){
        int cur=q.top().id;
        q.pop();
        if(vis[cur])continue;
        vis[cur]=true;
        for(int i=head[cur]; i ; i=e[i].next){
            int v=e[i].to;
            if(dis[cur]+e[i].w < dis[v]){
                dis[v]=dis[cur]+e[i].w;
                q.push(node(v,dis[v]));
            }
        }
    }
}
Floyd
1
2
3
4
5
6
7
for(int k=1;k<=n;k++){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
        }
    }
}

网络流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
typedef long long ll;
const ll maxn = 50100;//点的数量
const ll maxm = 60010*2;//边的数量，一般为maxn*maxn
const ll inf = 0x7f7f7f7f7f7f7f7f;
struct edge{
    ll to, next;
    ll w;
    edge(){}
    edge(ll to, ll next, ll w) : to(to), next(next), w(w){}
}e[maxm];
ll head[maxn], d[maxn], num, n, m;
ll st, ed, cur[maxn];
ll N,M;
void Init(){
    memset(head, -1, sizeof head);
    num = 0;
}
void add(ll u, ll v, ll w){
    e[num] = edge(v, head[u], w);head[u] = num++;
    e[num] = edge(u, head[v], 0);head[v] = num++;
}
bool bfs(){
    memset(d, -1, sizeof d);
    d[st] = 1;
    queue<int>q;
    q.push(st);
    while(!q.empty()){
        ll u = q.front();
        q.pop();
        for(ll i=head[u]; i!=-1; i=e[i].next){
            ll v = e[i].to;
            if(e[i].w == 0 || d[v] > 0) continue;
            d[v] = d[u] + 1;
            if(v == ed) return 1;
            q.push(v);
        }
    }
    return 0;
}
ll dfs(ll u, ll exp){
    if(u == ed || !exp) return exp;
    ll flow=0, f;
    for(ll & i =cur[u];i!=-1;i=e[i].next){
        ll v = e[i].to;
        if(d[v] == d[u] + 1 && (f=dfs(v, min(exp, e[i].w)))){
            e[i].w -= f;
            e[i^1].w += f;
            flow += f;
            exp -= f;
            if(!exp) break;
        }
    }
    return flow;
}
ll dinic(){
    ll ans = 0;
    while(bfs()){
        memcpy(cur, head, sizeof head);
        while(ll d=dfs(st, inf))
            ans += d;
    }
    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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define intmid  int mid = (l+r)>>1
const int maxn=1e5+10;
typedef long long ll;
int n,q;
ll sum[maxn<<2],cur[maxn<<2];
void push_up(int rt){
    sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void push_down(int l,int r,int rt){
    if(cur[rt]){
        intmid;
        cur[rt<<1]  += cur[rt];
        cur[rt<<1|1]+= cur[rt];
        sum[rt<<1]  += (mid-l+1)*cur[rt];
        sum[rt<<1|1]+= (r-mid)*cur[rt];
        cur[rt]=0;
    }
}
void build(int l,int r,int rt){
    intmid;cur[rt]=0;
    if(l==r){
        scanf("%lld",&sum[rt]);return;
    }
    build(lson);
    build(rson);
    push_up(rt);
}
void update(int ll,int rr,int val,int l,int r,int rt){
    intmid;
    if( ll<=l && rr>=r ){
        cur[rt]+=val;
        sum[rt]+=(r-l+1)*val;
        return ;
    }
    push_down(l,r,rt);
    if(ll<=mid)update(ll,rr,val,lson);
    if(rr>mid)update(ll,rr,val,rson);
    push_up(rt);
}
ll query(int ll,int rr,int l,int r,int rt){
    long long ret=0;
    if(ll<=l && rr>=r) return sum[rt];
    push_down(l,r,rt);
    intmid;
    if(ll<=mid) ret += query(ll,rr,lson);
    if(rr>mid) ret += query(ll,rr,rson);
    return ret;
}
int main(){
    cin>>n>>q;
    build(1,n,1);
    char s[2];
    int a,b,c;
    while(q--){
        scanf("%s%d%d",s,&a,&b);
        if(s[0]=='C'){
            scanf("%d",&c);
            update(a,b,c,1,n,1);
        }
        else printf("%lld\n",query(a,b,1,n,1));
    }
    return 0;
}
二维线段树(HDU1823)

求二维区间的最大值（最小值）

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
#include<bits/stdc++.h>
using namespace std;
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
int n, s[1005][4005];
void subBuild(int xrt, int l, int r, int rt) {
    s[xrt][rt] = -1;
    if(l != r) {
        int m = l + r >> 1;
        subBuild(xrt, lson);
        subBuild(xrt, rson);
    }
}
void build(int l, int r, int rt) {
    subBuild(rt, 0, n, 1);
    if(l != r) {
        int m = l + r >> 1;
        build(lson);
        build(rson);
    }
}
void subUpdate(int xrt, int y, int c, int l, int r, int rt) {
    if(l == r && l == y) s[xrt][rt] = max(s[xrt][rt], c);
    else {
        int m = l + r >> 1;
        if(y <= m) subUpdate(xrt, y, c, lson);
        else subUpdate(xrt, y, c, rson);
        s[xrt][rt] = max(s[xrt][rt << 1], s[xrt][rt << 1 | 1]);
    }
}
void update(int x, int y, int c, int l, int r, int rt) {
    subUpdate(rt, y, c, 0, n, 1);
    if(l != r) {
        int m = l + r >> 1;
        if(x <= m) update(x, y, c, lson);
        else update(x, y, c, rson);
    }
}
int subQuery(int xrt, int yl, int yr, int l, int r, int rt) {
    if(yl <= l && r <= yr) return s[xrt][rt];
    else {
        int m = l + r >> 1;
        int res = -1;
        if(yl <= m) res = subQuery(xrt, yl, yr, lson);
        if(yr > m) res = max(res, subQuery(xrt, yl, yr, rson));
        return res;
    }
}
int query(int xl, int xr, int yl, int yr, int l, int r, int rt) {
    if(xl <= l && r <= xr) return subQuery(rt, yl, yr, 0, n, 1);
    else {
        int m = l + r >> 1;
        int res = -1;
        if(xl <= m) res = query(xl, xr, yl, yr, lson);
        if(xr > m) res = max(res, query(xl, xr, yl, yr, rson));
        return res;
    }
}
int main() {
    int t;
    while(scanf("%d", &t) && t) {
        n = 1000;
        build(100, 200, 1);
        while(t--) {
            char ch[2];
            int a, b;
            double c, d;
            scanf("%s", ch);
            if(ch[0] == 'I') {
                scanf("%d%lf%lf", &a, &c, &d);
                update(a, c * 10, d * 10, 100, 200, 1);
            } else {
                scanf("%d%d%lf%lf", &a, &b, &c, &d);
                int cc = c * 10, dd = d * 10;
                if(a > b) swap(a, b);
                if(cc > dd) swap(cc, dd);
                int ans = query(a, b, cc, dd, 100, 200, 1);
                if(ans == -1) printf("-1\n");
                else printf("%.1f\n", ans / 10.0);
            }
        }
    }
    return 0;
}
势能线段树

BZOJ4695

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
//1.给一个区间[L,R] 加上一个数x 
//2.把一个区间[L,R] 里小于x 的数变成x 
//3.把一个区间[L,R] 里大于x 的数变成x 
//4.求区间[L,R] 的和
//5.求区间[L,R] 的最大值
//6.求区间[L,R] 的最小值
#include<bits/stdc++.h>
#define N 600005
#define lson (o<<1)
#define rson (o<<1|1)
#define inf 1<<30
using namespace std;
typedef long long ll;
int n;
inline int read(){
    int f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return f*x;
}
//Segment-Tree-Beats!
int maxv[N<<2],seca[N<<2],cnta[N<<2],minv[N<<2],seci[N<<2],cnti[N<<2],tagv[N<<2];
ll sumv[N<<2];
inline void pushup(int o){
  int l=o<<1,r=o<<1|1;sumv[o]=sumv[l]+sumv[r];
  if(maxv[l]==maxv[r])maxv[o]=maxv[l],cnta[o]=cnta[l]+cnta[r],seca[o]=max(seca[l],seca[r]);
  else{
    if(maxv[l]>maxv[r]) swap(l,r);maxv[o]=maxv[r]; cnta[o]=cnta[r];seca[o]=max(seca[r],maxv[l]);
  }
  if(minv[l]==minv[r])
    minv[o]=minv[l],cnti[o]=cnti[l]+cnti[r],seci[o]=min(seci[l],seci[r]);
  else{
    if(minv[l]<minv[r]) swap(l,r);minv[o]=minv[r]; cnti[o]=cnti[r];seci[o]=min(seci[r],minv[l]);
  }
}
inline void puttag(int o,int l,int r,int v){
    tagv[o]+=v;sumv[o]+=(ll)(r-l+1)*v;
    minv[o]+=v;maxv[o]+=v;seca[o]+=v;seci[o]+=v;
}
inline void tmax(int o,int l,int r,int v){
    sumv[o]+=(ll)(cnti[o])*(v-minv[o]);
    minv[o]=v;maxv[o]=max(v,maxv[o]);
    if(minv[o]==maxv[o]){
        sumv[o]=1LL*(r-l+1)*v;cnta[o]=cnti[o]=r-l+1;seca[o]=-inf;seci[o]=inf;
    }else seca[o]=max(v,seca[o]);
}
inline void tmin(int o,int l,int r,int v){
    sumv[o]-=(ll)(cnta[o])*(maxv[o]-v);
    maxv[o]=v;minv[o]=min(v,minv[o]);
    if(maxv[o]==minv[o]){
        sumv[o]=(ll)(r-l+1)*v;cnta[o]=cnti[o]=r-l+1;seca[o]=-inf;seci[o]=inf;
    }else seci[o]=min(v,seci[o]);
}
inline void pushdown(int o,int l,int r){
    int mid=(l+r)>>1;
    if(tagv[o]){
        puttag(lson,l,mid,tagv[o]);puttag(rson,mid+1,r,tagv[o]);
        tagv[o]=0;
    }
    if(maxv[lson]>maxv[o]&&seca[lson]<maxv[o])tmin(lson,l,mid,maxv[o]);
    if(maxv[rson]>maxv[o]&&seca[rson]<maxv[o])tmin(rson,mid+1,r,maxv[o]);
    if(minv[lson]<minv[o]&&seci[lson]>minv[o])tmax(lson,l,mid,minv[o]);
    if(minv[rson]<minv[o]&&seci[rson]>minv[o])tmax(rson,mid+1,r,minv[o]);
}
void build(int o,int l,int r){
    tagv[o]=0;
    if(l==r){
        int x=read();
        sumv[o]=maxv[o]=minv[o]=x;cnta[o]=cnti[o]=1;seca[o]=-inf;seci[o]=inf;tagv[o]=0;return;
    }
    int mid=(l+r)>>1;
    build(lson,l,mid);build(rson,mid+1,r);
    pushup(o);
}
void changemax(int o,int l,int r,int ql,int qr,int v){
    if(minv[o]>=v)return;
    if(ql<=l&&r<=qr&&v<seci[o]){tmax(o,l,r,v);return;}
    pushdown(o,l,r);int mid=(l+r)>>1;
    if(ql<=mid)changemax(lson,l,mid,ql,qr,v);
    if(qr>mid)changemax(rson,mid+1,r,ql,qr,v);
    pushup(o);
}
void changemin(int o,int l,int r,int ql,int qr,int v){
    if(maxv[o]<=v)return;
    if(ql<=l&&r<=qr&&v>seca[o]){tmin(o,l,r,v);return;}
    pushdown(o,l,r);int mid=(l+r)>>1;
    if(ql<=mid)changemin(lson,l,mid,ql,qr,v);
    if(qr>mid)changemin(rson,mid+1,r,ql,qr,v);
    pushup(o);
}
void add(int o,int l,int r,int ql,int qr,int v){
    if(ql<=l&&r<=qr){puttag(o,l,r,v);return;}
    pushdown(o,l,r);int mid=(l+r)>>1;
    if(ql<=mid)add(lson,l,mid,ql,qr,v);
    if(qr>mid)add(rson,mid+1,r,ql,qr,v);
    pushup(o);
}
int querymax(int o,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr)return maxv[o];
    pushdown(o,l,r);int mid=(l+r)>>1,ans=-inf;
    if(ql<=mid)ans=max(ans,querymax(lson,l,mid,ql,qr));
    if(qr>mid)ans=max(ans,querymax(rson,mid+1,r,ql,qr));
    return ans;
}
int querymin(int o,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr)return minv[o];
    pushdown(o,l,r);int mid=(l+r)>>1,ans=inf;
    if(ql<=mid)ans=min(ans,querymin(lson,l,mid,ql,qr));
    if(qr>mid)ans=min(ans,querymin(rson,mid+1,r,ql,qr));
    return ans;
}
ll querysum(int o,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr)return sumv[o];
    pushdown(o,l,r);int mid=(l+r)>>1;ll ans=0;
    if(ql<=mid)ans+=querysum(lson,l,mid,ql,qr);
    if(qr>mid)ans+=querysum(rson,mid+1,r,ql,qr);
    return ans;
}
//End of Segment Tree
int main(){
    n=read();build(1,1,n);
    int T=read();
    while(T--){
        int opt=read(),l=read(),r=read(),v;
        if(opt==1)v=read(),add(1,1,n,l,r,v);
        if(opt==2)v=read(),changemax(1,1,n,l,r,v);
        if(opt==3)v=read(),changemin(1,1,n,l,r,v);
        if(opt==4)printf("%lld\n",querysum(1,1,n,l,r));
        if(opt==5)printf("%d\n",querymax(1,1,n,l,r));
        if(opt==6)printf("%d\n",querymin(1,1,n,l,r));
    }
}

BZOJ5312

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
//1，给出l,r,x，将序列l,r之间的所有数都 and x
//2，给出l,r,x，将序列l,r之间的所有数都 or x
//3，给出l,r，询问l,r之间的最大值
#include<bits/stdc++.h>
using namespace std;
const int INF=(1<<21)-1;
const int N=2e5+5;
inline int read(){
    int X=0,w=0;char ch=0;
    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
    while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}
int n,m,b[N],mx[N*4],ran[N*4],ror[N*4],lza[N*4],lzo[N*4];
inline void upt(int a){
    mx[a]=max(mx[a<<1],mx[a<<1|1]);
    ran[a]=ran[a<<1]&ran[a<<1|1];
    ror[a]=ror[a<<1]|ror[a<<1|1];
}
void build(int a,int l,int r){
    lza[a]=INF,lzo[a]=0;
    if(l==r){
    mx[a]=b[l];ran[a]=b[l];ror[a]=b[l];
    return;
    }
    int mid=(l+r)>>1;
    build(a<<1,l,mid);build(a<<1|1,mid+1,r);
    upt(a);
}
inline void push(int a){
    int ls=a<<1,rs=a<<1|1;
    if(lzo[a]!=0){
    mx[ls]|=lzo[a];mx[rs]|=lzo[a];
    ran[ls]|=lzo[a];ran[rs]|=lzo[a];
    ror[ls]|=lzo[a];ror[rs]|=lzo[a];
    lza[ls]|=lzo[a];lza[rs]|=lzo[a];
    lzo[ls]|=lzo[a];lzo[rs]|=lzo[a];
    lzo[a]=0;
    }
    if(lza[a]!=INF){
    mx[ls]&=lza[a];mx[rs]&=lza[a];
    ran[ls]&=lza[a];ran[rs]&=lza[a];
    ror[ls]&=lza[a];ror[rs]&=lza[a];
    lza[ls]&=lza[a];lza[rs]&=lza[a];
    lza[a]=INF;
    }
}
void mdy(int a,int l,int r,int l1,int r1,int x,bool k){
    if(r<l1||r1<l)return;
    if(l1<=l&&r<=r1&&(!((ran[a]^ror[a])&x))){
    if(!k){mx[a]&=x;ran[a]&=x;ror[a]&=x;lza[a]&=x;}
    else{mx[a]|=x;ran[a]|=x;ror[a]|=x;lza[a]|=x;lzo[a]|=x;}
    return;
    }
    int mid=(l+r)>>1;
    push(a);
    mdy(a<<1,l,mid,l1,r1,x,k);mdy(a<<1|1,mid+1,r,l1,r1,x,k);
    upt(a);
}
int qry(int a,int l,int r,int l1,int r1){
    if(r<l1||r1<l)return -1;
    if(l1<=l&&r<=r1)return mx[a];
    int mid=(l+r)>>1;
    push(a);
    return max(qry(a<<1,l,mid,l1,r1),qry(a<<1|1,mid+1,r,l1,r1));
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++)b[i]=read();
    build(1,1,n);
    while(m--){
    int op=read(),x=read(),y=read();
    if(op==1)mdy(1,1,n,x,y,read(),0);
    if(op==2)mdy(1,1,n,x,y,read(),1);
    if(op==3)printf("%d\n",qry(1,1,n,x,y));
    }
    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
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
//点权
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const int maxn=1e5+10;
inline int read(){
    int x=0; bool f=0; char ch=getchar();
    while (ch<'0' || '9'<ch) f|=ch=='-', ch=getchar();
    while ('0'<=ch && ch<='9') x=x*10+ch-'0', ch=getchar();
    return f?-x:x;
}
struct edge{
    int next,to;
}e[maxn*2];
int head[maxn],cnt;
void add(int u,int v){
    e[++cnt]=edge{head[u],v};
    head[u]=cnt;
}
int n,m,root,P;
int w[maxn];
int fa[maxn],deep[maxn],siz[maxn],son[maxn],rk[maxn],top[maxn],id[maxn];
void dfs1(int u,int pre,int dep){
    fa[u]=pre;deep[u]=dep;siz[u]=1;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v==pre)continue;
        dfs1(v,u,dep+1);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])son[u]=v;
    }
}
void dfs2(int u,int t){
    top[u]=t;id[u]=++cnt;rk[cnt]=u;
    if(!son[u])return;
    dfs2(son[u],t);
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v!=son[u]&&v!=fa[u])dfs2(v,v);
    }
}
int sum[maxn<<2],lazy[maxn<<2];
void push_up(int rt){
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void push_down(int ls,int rs,int rt){
    if(lazy[rt]){
        int val=lazy[rt];
        sum[rt<<1]=(sum[rt<<1]+val*ls)%P;
        sum[rt<<1|1]=(sum[rt<<1|1]+val*rs)%P;
        lazy[rt<<1]=(lazy[rt<<1]+lazy[rt])%P;
        lazy[rt<<1|1]=(lazy[rt<<1|1]+lazy[rt])%P;
        lazy[rt]=0;
    }
}
void build(int l,int r,int rt){
    if(l==r){
        sum[rt]=w[rk[l]]; //重新编号后的
        return;
    }
    int mid=(l+r)>>1;
    build(lson);
    build(rson);
    push_up(rt);
}
void update(int L,int R,int v,int l,int r,int rt){
    if(L<=l&&r<=R){
        sum[rt]=(sum[rt]+v*(r-l+1))%P;
        lazy[rt]=(lazy[rt]+v)%P;
        return;
    }
    int mid=(l+r)>>1;
    push_down(mid-l+1,r-mid,rt);
    if(L<=mid) update(L,R,v,lson);
    if(R>mid)  update(L,R,v,rson);
    push_up(rt);
}
int querysum(int L,int R,int l,int r,int rt){
    if(L<=l&&r<=R){
        return sum[rt];
    }
    int mid=(l+r)>>1,ret=0;
    push_down(mid-l+1,r-mid,rt);
    if(L<=mid) ret=(ret+querysum(L,R,lson))%P;
    if(R>mid)  ret=(ret+querysum(L,R,rson))%P;
    return ret;
}
void PathUpdate(int x,int y,int v){
    while(top[x]!=top[y]){
        if(deep[top[x]]<deep[top[y]]) swap(x,y);
        update(id[top[x]],id[x],v,1,n,1);
        x=fa[top[x]];
    }
    if(id[x]>id[y]) swap(x,y);
    update(id[x],id[y],v,1,n,1);
}
int PathQuery(int x,int y){
    int ret=0;
    while(top[x]!=top[y]){
        if(deep[top[x]]<deep[top[y]]) swap(x,y);
        ret=(ret+querysum(id[top[x]],id[x],1,n,1))%P;
        x=fa[top[x]];
    }
    if(id[x]>id[y])swap(x,y);
    ret=(ret+querysum(id[x],id[y],1,n,1))%P;
    return ret;
}

int main(){
    //初始化只需要将head和son置零
    n=read(),m=read(),root=read(),P=read();
    for(int i=1;i<=n;i++){
        w[i]=read();
    }
    cnt=0;
    for(int i=1;i<=n;i++) head[i]=0;
    for(int i=0;i<n-1;i++){
        int u=read(),v=read();
        add(u,v);
        add(v,u);
    }
    cnt=0;
    dfs1(root,0,1);  //注意根节点不一定是1(一般为1就好)
    dfs2(root,root);
    build(1,n,1);

    while(m--){
        int op=read(),x,y,z;
        if(op==1){ //更新x-y最短路径上所有点
            x=read(),y=read(),z=read();
            PathUpdate(x,y,z);
        }
        else if(op==2){ //查询x-y最短路径上所有点
            x=read(),y=read();
            printf("%d\n",PathQuery(x,y));
        }
        else if(op==3){ //更新以x为根节点的子树
            x=read(),z=read();
            update(id[x],id[x]+siz[x]-1,z,1,n,1);
        }
        else{ //查询以x为根节点的子树
            x=read();
            printf("%d\n",querysum(id[x],id[x]+siz[x]-1,1,n,1));
        }
    }
}
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 fa[maxn],deep[maxn],siz[maxn],son[maxn],rk[maxn],top[maxn],id[maxn];
int dis[maxn],w[maxn];
void dfs1(int u,int pre,int dep){
    fa[u]=pre;deep[u]=dep;siz[u]=1;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v==pre)continue;
        dis[v]=dis[u]+e[i].v;
        dfs1(v,u,dep+1);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])son[u]=v;
    }
}
void dfs2(int u,int t){
    top[u]=t;id[u]=++cnt;rk[cnt]=u;
    if(!son[u])return;
    dfs2(son[u],t);
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v!=son[u]&&v!=fa[u])dfs2(v,v);
    }
}
int PathQuery(int x,int y){
    int ans=0;
    while(top[x]!=top[y]){
        if(deep[top[x]]<deep[top[y]]) swap(x,y);
        ans=max(ans,query(id[top[x]],id[x],1,n,1));
        x=fa[top[x]];
    }
    if(x==y)return ans;
    if(deep[x]>deep[y]) swap(x,y);
    ans=max(ans,query(id[son[x]],id[y],1,n,1));
    return ans;
}
void PathUpdate(int x,int y,int v){
    while(top[x]!=top[y]){
        if(deep[top[x]]<deep[top[y]]) swap(x,y);
        update(id[top[x]],id[x],v,1,n,1);
        x=fa[top[x]];
    }
    if(x==y)return;
    if(deep[x]>deep[y]) swap(x,y);
    update(id[son[x]],id[y],v,1,n,1);
}

for(int i=0;i<n-1;i++){
    if(deep[E[i].u]<deep[E[i].v]) swap(E[i].u,E[i].v);
    w[E[i].u]=E[i].w;   //边权放在下面结点上变为点权
}

LCA

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 deep[maxn],f[maxn],dis[maxn],p[maxn][30];
void dfs(int x,int pre,int d){
    deep[x]=d;
    f[x]=pre;
    for(int i=head[x];i;i=e[i].next){
        int to=e[i].to;
        if(to!=pre){
            dis[to]=dis[x]+e[i].w;
            dfs(to,x,d+1);
        }
    }
}
void init(){
    //p[i][j]表示i结点的第2^j祖先
    for(int j=0;(1<<j)<=n;j++)
        for(int i=1;i<=n;i++)
            p[i][j]=-1;
    for(int i=1;i<=n;i++)p[i][0]=f[i];
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i<=n;i++)
            if(p[i][j-1]!=-1)
            p[i][j]=p[p[i][j-1]][j-1];//i的第2^j祖先就是i的第2^(j-1)祖先的第2^(j-1)祖先
}
int LCA(int a,int b){
    int i,j;
    if(deep[a]<deep[b])swap(a,b);
    for(i=0;(1<<i)<=deep[a];i++);
    i--;
    //使a,b两点的深度相同
    for(j=i;j>=0;j--)
        if(deep[a]-(1<<j)>=deep[b])
        a=p[a][j];
    if(a==b)return a;
    //倍增法，每次向上进深度2^j，找到最近公共祖先的子结点
    for(j=i;j>=0;j--){
        if(p[a][j]!=-1&&p[a][j]!=p[b][j]){
            a=p[a][j];
            b=p[b][j];
        }
    }
    return f[a];
}

//树链剖分
int query_lca(int x,int y){
    while(top[x]!=top[y]){
        if(deep[top[x]]<deep[top[y]])swap(x,y);
        x=fa[top[x]];
    }return deep[x]<deep[y]?x: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
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
//有多少对点之间的距离小于等于k
#include<bits/stdc++.h>
using namespace std;
const int maxn=4e4+10;
int head[maxn],siz[maxn],dep[maxn],vis[maxn],f[maxn],o[maxn];
int rt,ans,ecnt,cnt,sum,n,k;
struct edge{
    int to,next,w;
}e[maxn<<1];
void init(){
    memset(head,0,sizeof head);
    memset(vis,0,sizeof vis);
    ecnt=0;
    cnt=0;
    ans=0;
}
void add(int x,int y,int w){
    e[++ecnt].to=y;
    e[ecnt].w=w;
    e[ecnt].next=head[x];
    head[x]=ecnt;
}
void getroot(int u,int fa){
    siz[u]=1;f[u]=0;
    for(int i=head[u]; i; i=e[i].next){
        int v=e[i].to;
        if(v==fa || vis[v]) continue;
        getroot(v,u);
        siz[u]+=siz[v];
        f[u]=max(f[u],siz[v]);
    }
    f[u]=max(f[u],sum-siz[u]);
    if(f[u] < f[rt]) rt=u;
}
void getdeep(int u,int fa){
    o[++cnt]=dep[u];
    for(int i=head[u]; i; i=e[i].next){
        int v=e[i].to;
        if(v==fa || vis[v]) continue;
        dep[v]=dep[u]+e[i].w;
        getdeep(v,u);
    }
}
int cal(int u,int d){
    cnt=0;
    dep[u]=d;
    getdeep(u,0);
    sort(o+1,o+1+cnt);
    int l=1,r=cnt,res=0;
    while(l < r){
        if(o[l]+o[r] <= k) res+=(r-l),l++;
        else r--;
    }
    return res;
}
void slove(int u){
    ans+=cal(u,0);
    vis[u]=1;
    for(int i=head[u]; i; i=e[i].next){
        int v=e[i].to;
        if(vis[v]) continue;
        ans-=cal(v,e[i].w);
        sum=siz[v];
        rt=0;
        getroot(v,0);
        slove(rt);
    }
}
int main(){
    while(~scanf("%d",&n)){
        init();
        for(int i=0; i<n-1; i++){
            int x,y,w;
            scanf("%d %d %d",&x,&y,&w);
            add(x,y,w);
            add(y,x,w);
        }
        scanf("%d",&k);
        rt=0;
        sum=f[0]=n;
        getroot(1,0);
        slove(rt);
        printf("%d\n",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
//n个数，滑动窗口为k，求每次的最大值和最小值
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
int qmax[maxn],idmin[maxn];
int qmin[maxn],idmax[maxn];
int ans[maxn];
int hmax,tmax,hmin,tmin;
int n,k;
int main(){
    scanf("%d %d",&n,&k);
    hmax=1,hmin=1;
    tmax=0,tmin=0;
    int cnt=0;
    for(int i=1; i<=n; i++){
        int a;
        scanf("%d",&a);
        while(hmax<=tmax && qmax[tmax]<=a){
            tmax--;
        }
        while(hmin<=tmin && qmin[tmin]>=a){
            tmin--;
        }
        qmax[++tmax]=a;
        qmin[++tmin]=a;
        idmax[tmax]=idmin[tmin]=i;
        while(idmax[hmax]<=i-k) hmax++;
        while(idmin[hmin]<=i-k) hmin++;
        if(i>=k) printf("%d%c",qmin[hmin],i<n?' ':'\n');
        if(i>=k) ans[cnt++]=qmax[hmax];
    }
    printf("%d",ans[0]);
    for(int i=1; i<cnt; i++) printf(" %d",ans[i]);
    puts("");
}

单调栈

最大全1矩阵问题

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
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 2009
int n,m;
int M[N][N];
int h[N][N];
int ans;
int s[N],L[N],R[N];

void fin(int row){//相同不出栈
    s[0]=0;int top=0;
    h[row][m+1]=0;//用于得到最后没出栈元素的R
    for(int i=1;i<=m+1;i++){
        int ar=s[top];
        while(h[row][i]<h[row][ar]){
            R[ar]=i;top--;
            ar=s[top];
        }
        L[i]=ar;s[++top]=i;
    }
    for(int i=1;i<=m;i++)
        if(h[row][i])
        ans=max(ans,h[row][i]*(R[i]-L[i]-1));
}

void fin_(int row){//相同出栈
    s[0]=0;int top=0;
    h[row][m+1]=0;
    for(int i=1;i<=m+1;i++){
        int ar=s[top];
        while(h[row][i]<=h[row][ar]){
            R[ar]=i;top--;
            if(top<0)break;//最后m+1的时候把s[0]也出栈了
            ar=s[top];
        }
        L[i]=ar;s[++top]=i;
    }
    for(int i=1;i<=m;i++)
        if(h[row][i])
        ans=max(ans,h[row][i]*(R[i]-L[i]-1));
}
/*
关于相同元素出栈
假设不出栈，h[s[2]]==h[4]==2，
本来这个点是可以延伸到的，但是我们不出栈，
所以第二个数的L不准确了，但是第一个数的R准确了，
那么第一个数因为遇到不相同的出栈了，得到的就是准确的

如果出栈的话，前面那个点的R就不准确了
但是接下来的相同的数的L是准确的，
只要遇到一个不相同的使任意一个出栈，
那么最后一个相同的数的R就是准确的了，
因此得到的还是一段准确的区间
*/
int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        memset(h,0,sizeof h);
        ans=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                scanf("%d",&M[i][j]);
                if(M[i][j])h[i][j]=h[i-1][j]+1;
            }
        }
        for(int i=1;i<=n;i++)fin(i);
        printf("%d\n",ans);
    }
}
/*
4 4
0 1 1 1
1 0 1 1
1 1 1 1
1 1 1 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
//求区间元素个数
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
const int maxn=1e6+10;
int a[maxn],n,m,cnt[maxn],ans=0,anss[maxn],block;
struct node{
    int L,R,i;
}q[maxn];
bool cmp(node x,node y){
    if(x.L/block != y.L/block) return x.L/block < y.L/block;
    return x.R < y.R;
}
void add(int p){
    cnt[a[p]]++;
    if(cnt[a[p]] == 1) ans++;
}
void del(int p){
    cnt[a[p]]--;
    if(cnt[a[p]] == 0) ans--;
}
int main(){
    scanf("%d",&n);
    block=sqrt(n);
    for(int i=1; i<=n; i++) scanf("%d",&a[i]);
    scanf("%d",&m);
    for(int i=1; i<=m; i++){
        scanf("%d %d",&q[i].L,&q[i].R);
        q[i].i=i;
    }
    sort(q+1,q+m+1,cmp);
    int cL=1,cR=0;
    for(int i=1; i<=m; i++){
        int L=q[i].L,R=q[i].R;
        while(cL < L) del(cL++);
        while(cL > L) add(--cL);
        while(cR < R) add(++cR);
        while(cR > R) del(cR--);
        anss[q[i].i]=ans;
    }
    for(int i=1; i<=m; i++) printf("%d\n",anss[i]);
}

hash

字符串hash
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
typedef unsigned long long ull;
//ull 会溢出取模
const ull base=233;
const int maxn=1e5+10;
char s[maxn];
ull hs[maxn],p[maxn];
ull geths(int l,int r){
    return (ull)hs[r]-p[r-l+1]*hs[l-1];
}
void init(){
    p[0]=1;
    for(int i=1; i<maxn; i++) p[i]=p[i-1]*base;
}
int main(){
    scanf("%s",s+1);
    int len=strlen(s+1);
    for(int i=1; i<=len; i++){
        hs[i]=hs[i-1]*base+s[i];
    }
}
手写hash
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct Hash{
    ll mod = 2908361;
    ll cnt = 0, Head[2908361], nxt[1000006];
    ll val[1000006], pos[1000006];
    void init(){
        memset(Head, -1, sizeof(Head)); cnt = 0;
    }
    void Insert(ll x, ll v){
        ll key = x % mod;
        pos[cnt] = x, val[cnt] = v, nxt[cnt] = Head[key];
        Head[key] = cnt++;
    }
    ll Find(ll x){
        ll key = x % mod;
        for(ll i = Head[key]; ~i; i = nxt[i]){
            if(pos[i] == x) return val[i];
        }
        return -1ll;
    }
}hs;

KMP

KMP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const int maxn=1e5+10;
char s[maxn];
char t[maxn];
int nex[maxn],len;
void cal(){
    int i,j;
    nex[0]=j=-1;
    i=0;
    while(i<m){ //m是t的长度
        while(j!=-1 && t[j]!=t[i]) j=nex[j];
        nex[++i] = ++j;
    }
}
int kmp(){
    int i=0,j=0;
    while(i<n){ //n是s的长度
        while(j!=-1 && s[i]!=t[j]) j=nex[j];
        i++;
        j++;
        if(j>=m) return i;//返回最后匹配的位置
    }
    return -1;
}
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
//给定字符串，对于整个串，求最短循环节的次数
#include<cstdio>
#include<cstring>
const int maxn = 1e6+10;
int nex[maxn],len;
char s[maxn];
void cal(){
    int i,j;
    nex[0]=j=-1;
    i=0;
    while(i<len){
        while(j!=-1 && s[j]!=s[i]) j=nex[j];
        nex[++i]=++j;
    }
}
int main(){
    while(~scanf("%s",s)){
        if(s[0] == '.') break;
        len=strlen(s);
        cal();
        int ans=1;
        if(len%(len-nex[len])==0) ans=len/(len-nex[len]);
        printf("%d\n",ans);
    }
}
扩展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
//next[i]表示t[i...m-1]与t[0...m-1]的最长公共前缀
//extend[i]表示s[i...n-1]与t[0...m-1]的最长公共前缀
int Next[maxn],extend[maxn];
void getNext(char t[],int m){
    Next[0]=m;
    int j=0;
    while(j+1<m&&t[j]==t[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&&t[i+j]==t[j]) j++;
            Next[i]=j;
            k=i;
        }
    }
}

void extendkmp(char t[],int m,char s[],int n){
    getNext(t,m);
    int j=0;
    while(j<n&&j<m&&t[j]==s[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&&s[i+j]==t[j]) j++;
            extend[i]=j;
            k=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
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
#include<bits/stdc++.h>
#define maxc 30
using namespace std;
const int maxn = 250000+10;
char str[maxn];
struct SAM{
    int len[maxn * 2], //最长子串的长度(该节点字串数量=len[x]-len[link[x]])
    link[maxn * 2],   //后缀链接(最短串前部减少一个字符所到达的状态)
    cnt[maxn * 2],    //被后缀连接的数
    nex[maxn * 2][maxc],  //状态转移(尾部加一个字符的下一个状态)(图)
    idx, //节点编号
    last;    //最后节点
    int epos[maxn * 2]; // enpos数（该状态子串出现数量）
    int a[maxn];		//长度为i的子串出现最大次数
    void init() {	//初始化
        last = idx = 1; //1表示root起始点 空集
        link[1] = len[1] = 0;
    }
    //SAM建图
    void add(int c){     //插入字符，为字符ascll码值
        c-='a';
        int x = ++idx; //创建一个新节点x;
        len[x] = len[last] + 1; //  长度等于最后一个节点+1
        epos[x] = 1;  //接受节点子串除后缀连接还需加一
        int p;  //第一个有C转移的节点;
        for(p = last; p && !nex[p][c]; p = link[p]) 
            nex[p][c] = x;//沿着后缀连接 将所有没有字符c转移的节点直接指向新节点
        if(!p) link[x] = 1, cnt[1]++;  //全部都没有c的转移 直接将新节点后缀连接到起点
        else{
            int q = nex[p][c];    //p通过c转移到的节点
            if (len[p] + 1 == len[q])    //pq是连续的
                link[x] = q, cnt[q]++; //将新节点后缀连接指向q即可,q节点的被后缀连接数+1
            else{
                int nq = ++idx;   //不连续 需要复制一份q节点
                len[nq] = len[p] + 1;   //令nq与p连续
                link[nq] = link[q];   //因后面link[q]改变此处不加cnt
                memcpy(nex[nq], nex[q], sizeof(nex[q]));  //复制q的信息给nq
                for (; p&&nex[p][c] == q; p = link[p])
                    nex[p][c] = nq;    //沿着后缀连接 将所有通过c转移为q的改为nq
                link[q] = link[x] = nq; //将x和q后缀连接改为nq
                cnt[nq] += 2; //  nq增加两个后缀连接
            }
        }
        last=x;  //更新最后处理的节点
    }
    void GetNpos(){	//求npos数，即该节点字串出现次数
        queue<int>q;
        for (int i = 1; i <= idx; i++)
            if (!cnt[i])q.push(i);   //将所有没被后缀连接指向的节点入队
        while (!q.empty()){
            int x = q.front();
            q.pop();
            epos[link[x]] += epos[x]; //子串数量等于所有后缀连接指向该节点的子串数量和+是否为接受节点
            if (--cnt[link[x]] == 0)q.push(link[x]);   //当所有后缀连接指向该节点的处理完毕后再入队
        }
    }
    int GetSubNum(){	//求不相同字串数量
        int ans = 0;
        for (int i = 2; i <= idx; i++) ans+=(len[i]-len[link[i]]);//一状态子串数量等于len[i]-len[link[i]]
        return ans;
    }
    void GetSubMax(){//求出所有长度为k的子串中出现次数最多的子串出现次数
        GetNpos();
        int n = strlen(str+1);
        //printf("%d\n",n);
        for (int i = 1; i <= idx; i++) 
            a[len[i]] = max(a[len[i]], epos[i]);	//长度≤k的子串中出现次数最多的子串出现次数的最小值
        for (int i = n - 1; i >= 1; i--) a[i] = max(a[i], a[i + 1]);//求一遍后缀最大值就是答案
        for (int i = 1; i <= n; i++) printf("%d\n", a[i]);
    }
}sam;
int main(){
	while(~scanf("%s",str+1)){
        sam.init();
        int len=strlen(str+1);
        for(int i=1; i<=len; i++) sam.add(str[i]);
        sam.GetSubMax();
	}
}

SA

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
//清巨那偷来的板子QAQ
struct SuffixArray{
    // S下标从1开始,S[n+1]为0，S[1...n]非零
    //sa:字典序中排第i位的起始位置在str中第sa[i]
    //rank:就是str第i个位置的后缀是在字典序排第几
    //height：字典序排i和i-1的后缀的最长公共前缀
    int s[N<<1],t[N<<1],ht[N],sa[N],rk[N],p[N],c[N],w[N];
    inline int trans(int n,const char* S){
        int m=*max_element(S+1,S+1+n);
        memset(rk,0,(m+1)<<2); //
        for(int i=1;i<=n;++i) rk[S[i]]=1;
        for(int i=1;i<=m;++i) rk[i]+=rk[i-1];
        for(int i=1;i<=n;++i) s[i]=rk[S[i]];
        return rk[m];
    }
    #define ps(x) sa[w[s[x]]--]=x
    #define pl(x) sa[w[s[x]]++]=x
    inline void radix(int* v,int* s,int* t,int n,int m,int n1){
    	memset(sa,0,(n+1)<<2); memset(c,0,(m+1)<<2);
        for(int i=1;i<=n;++i) ++c[s[i]];
        for(int i=1;i<=m;++i) w[i]=c[i]+=c[i-1];
        for(int i=n1;i;--i) ps(v[i]);
        for(int i=1;i<=m;++i) w[i]=c[i-1]+1;
        for(int i=1;i<=n;++i) if(sa[i]>1 && t[sa[i]-1]) pl(sa[i]-1);
        for(int i=1;i<=m;++i) w[i]=c[i];
        for(int i=n;i;--i) if(sa[i]>1 && !t[sa[i]-1]) ps(sa[i]-1);
    }
    inline void SAIS(int n,int m,int* s,int* t,int* p){
        int n1=0,ch=rk[1]=0,*s1=s+n; t[n]=0;
        for(int i=n-1;i;--i) t[i]=s[i]==s[i+1]?t[i+1]:s[i]>s[i+1];
        for(int i=2;i<=n;++i) rk[i]=t[i-1]&&!t[i]?(p[++n1]=i,n1):0;
        radix(p,s,t,n,m,n1);
        for(int i=1,x,y;i<=n;++i) if(x=rk[sa[i]]){
            if(ch<=1 || p[x+1]-p[x]!=p[y+1]-p[y]) ++ch;
            else for(int j=p[x],k=p[y];j<=p[x+1];++j,++k)
                if((s[j]<<1|t[j])^(s[k]<<1|t[k])){ ++ch; break; }
            s1[y=x]=ch;
        }
        if(ch<n1) SAIS(n1,ch,s1,t+n,p+n1);
        else for(int i=1;i<=n1;++i) sa[s1[i]]=i;
        for(int i=1;i<=n1;++i) s1[i]=p[sa[i]];
        radix(s1,s,t,n,m,n1);
    }
    inline void init(int n,const char* S){
        int m=trans(++n,S);	SAIS(n,m,s,t,p);
        for(int i=1;i<n;++i) rk[sa[i]=sa[i+1]]=i;
        for(int i=1,j,k=0;i<n;++i) if(rk[i]>1){
            for(j=sa[rk[i]-1];S[i+k]==S[j+k];++k);
            if(ht[rk[i]]=k) --k;
        }
    }
}SA;


char S[N];
int main(){
    //注意输入和传参
	while(scanf("%s",S+1)&&strcmp(S+1,".")!=0){
        int n=strlen(S+1);
        SA.init(n,S);
	}
}

//SA应用
int get_lcs(int n,int mid){ //mid为两串分隔位置，n为拼接后总长
    int ans=0;
    for(int i=2;i<=n;i++){
        if(ht[i]>ans){
            if(sa[i]>=1&&sa[i]<=mid&&sa[i-1]>=mid+1) ans=max(ans,ht[i]);
            if(sa[i-1]>=1&&sa[i-1]<=mid&&sa[i]>=mid+1) ans=max(ans,ht[i]);
        }
    }
    return ans;
}
ll get_subcnt(int n){ //不同子串个数
    ll ans=0;
    for(int i=1;i<=n;i++){
        ans += n-sa[i]+1-ht[i];
    }
    return ans;
}
int get_looplen(int n){ //循环节长度
    for(int i=1;i<=n;i++){
        if(n%i) continue; //不能整除的话，一定不能构成循环节
        if(rk[1] != rk[i+1]+1) continue; //rank数组必须要相邻才能构成循环节
        if(ht[rk[1]] != n-i) continue; //若第一个和第二个的最长公共前缀不符合条件
        return n/i;
    }
    return 1;
}
bool pd1(int k){
    int mx=SA.sa[1],mm=SA.sa[1];
    for(int i=2; i<=n; ++i){
        if(SA.ht[i]>=k){
            mm=min(mm,min(SA.sa[i],SA.sa[i-1]));
            mx=max(mx,max(SA.sa[i],SA.sa[i-1]));
            if(mx-mm>=k) return 1; //
        }else{
            mx=SA.sa[i],mm=SA.sa[i];
        }
    }
    return 0;
}
int get1(){ //不可重叠最长子串长度
    int l=1,r=n/2;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(pd1(mid)) l=mid;
        else r=mid-1;
    }
    return l;
}
bool pd2(int x){
    int cnt=1;
    for(int i=2; i<=n; ++i){
        if(SA.ht[i]>=x){
            cnt++;
            if(cnt==k) return 1;
        }
        else cnt=1;
    }
    return 0;
}
int get2(){ //可重叠 出现k次最长子串长度
    int l=0,r=n;
    while(l<r){
        int mid = (l+r+1)>>1;
        if(pd(mid)) l=mid;
        else        r=mid-1;
    }
    return l;
}
//可重叠最长子串长度 = max(ht[i])

PAM

HDU6599

求回文串

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
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull base=233;
const int maxn=3e5+10;
const int N=30;
ull ans[maxn];
ull hs[maxn],ba[maxn];
char s[maxn];
ull gethash(int l,int r){
    return hs[r]-hs[l-1]*ba[r-l+1];
}
bool check(int l,int r){
    int lenn=r-l+1;
    int mid=(l+r)>>1;
    if(lenn&1) return gethash(l,mid)==gethash(mid,r);
    return gethash(l,mid)==gethash(mid+1,r);
}
struct pam{
    /**
    int nex[maxn][N],fail[maxn];//在当前状态首尾添加字符的状态,失配跳到的状态
    int len[maxn],S[maxn],pos[maxn];//状态i表示的回文长度,缓存池,状态对应首次出现的位置
    int cnt[maxn],num[maxn];//状态出现次数,以状态末尾结尾但不包含本条路径的数目
    int last,n,p;//上个状态,总长度,当前状态编号
    p-2就是本质不同的回文串的个数
    **/
    int nex[maxn][N],fail[maxn];
    int len[maxn],S[maxn],pos[maxn];
    int cnt[maxn],num[maxn];
    int last,n,p;
    int newnode(int i){
        memset(nex[p],0,sizeof(nex[p]));
        cnt[p]=num[p]=0;
        len[p]=i;
        return p++;
    }
    void init(){
        p=0;
        newnode(0);
        newnode(-1);
        last=n=0;
        fail[0]=1;
        S[n]=-1;
    }
    int get_fail(int i){
        while(S[n-len[i]-1]!=S[n]) i=fail[i];
        return i;
    }
    void add(int i,int po){
        i-='a';
        S[++n]=i;
        int cur=get_fail(last);
        if(!nex[cur][i]){
            int now=newnode(len[cur]+2);
            pos[now]=po;
            fail[now]=nex[get_fail(fail[cur])][i];
            nex[cur][i]=now;
            num[now]=num[fail[now]]+1;
        }
        last=nex[cur][i];
        cnt[last]++;
    }
    void Count(){
        for(int i=p-1; i>=0; i--) cnt[fail[i]]+=cnt[i];
    }
}p;
int main(){
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    int len;
    ba[0]=1;
    for(int i=1; i<maxn; i++) ba[i]=ba[i-1]*base;
    while(~scanf("%s",s+1)){
        len=strlen(s+1);
        p.init();
        hs[0]=0;
        for(int i=1; i<=len; i++){
            p.add(s[i],i);
            ans[i]=0;
            hs[i]=hs[i-1]*base+s[i];
        }
        p.Count();
        for(int i=1; i<p.p; i++){
            int l=(p.pos[i]-p.len[i]+1);
            int r=p.pos[i];
            if(check(l,r)) ans[p.len[i]]+=p.cnt[i];
        }
        printf("%llu",ans[1]);
        for(int i=2; i<=len; i++) printf(" %llu",ans[i]);
        puts("");
    }
}

Manacher

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
#include <cstdio>  
#include <cstring>  
#define Min(a,b) a>b?b:a  
#define Max(a,b) a>b?a:b  
using namespace std;  
int Len[3000005];  
char str[3000005],s[3000005];  
int n,mx,id,len;  

void init(){  
    int k=0;  
    str[k++] = '$';  
    for(int i=0;i<len;i++){  
        str[k++]='#';  
        str[k++]=s[i];  
    }  
    str[k++]='#';  
    len=k;  
}  

int Manacher(){  
  Len[0] = 0;  
  int sum = 0;  
  mx = 0;  
  for(int i=1;i<len;i++){  
    if(i < mx) Len[i] = Min(mx - i, Len[2 * id - i]);  
    else Len[i] = 1;  
    while(str[i - Len[i]]== str[i + Len[i]]) Len[i]++;  
    if(Len[i] + i > mx){  
      mx = Len[i] + i;  
      id = i;  
      sum = Max(sum, Len[i]);  
    }  
  }  
  return (sum - 1);  
}  

int main()  
{  
  scanf("%d",&n);  
  while(n--){  
    memset(str,0,sizeof(str));
    scanf("%s",s);  
    len = strlen(s);  
    init();  
    int temp = Manacher();  
    printf("%d\n",temp);  
  }  
  return 0;  
}

数学

BSGS

当$gcd(y,p)=1$，在这种情况下，有可能给定$p$为质数。设$x=a * m - b$ ，$m= \lceil \sqrt p \rceil$，$ a \in [0,m+1)$，$b \in [0,m)$，那么原式变成$y^{a * m}=z * y^{b}$，先枚举$b$，计算$z * y^{b}(mod\ p)$，存到$map$中，再枚举$a$就好了。

SDOI2011

题意：给定$y,z,p$，计算1. $y^z (mod \ p)$；2. 满足$x * y \equiv z(mod \ p)$的最小非负整数的$x$；3.满足$y^x \equiv z\ (mod\ p)$的最小非负整数的$x$。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll y,z,p;
ll qpow(ll x,ll n,ll mod){
    ll res=1;
    while(n){
        if(n&1) res=res*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return res;
}
ll inv(ll x,ll mod){
    return qpow(x,mod-2,mod);
}
void nnot(){
    puts("Orz, I cannot find x!");
}
void BSGS(ll x,ll y){
    map<ll,ll>pw;
    if(y == 1){
        puts("0");
        return;
    }
    ll ans = -1, m = sqrt(p) + 1, xx, s = y;
    for(ll i = 0; i < m; i++){
        pw[s] = i;
        s = s * x % p;
    }
    xx = qpow(x, m, p), s = 1;
    for(ll i = 1; i <= m + 1; ++i){
        s = s * xx % p;
        if(pw.count(s)){
            ans = i * m - pw[s];
            break;
        }
    }
    if(ans < 0) nnot();
    else printf("%lld\n", ans);
}
int main(){
    ll t,op;
    scanf("%lld %lld",&t,&op);
    while(t--){
        scanf("%lld %lld %lld",&y,&z,&p);
        if(op == 1) printf("%lld\n",qpow(y,z,p));
        else if(op == 2){
            ll tm=y%p;
            if(tm==0 && z%p!=0){
                nnot();
                continue;
            }
            printf("%lld\n",z*inv(y,p)%p);
        }
        else{
            if(y%p) BSGS(y,z);
            else nnot();
        }
    }
}

当$gcd(y,p) \neq 1$时，就要用到$exgcd$理论。

将原式写成$y * y^{x-1}+k * p=z,k \in Z$，根据$exgcd$，当$d=gcd(y,p)$不是$z$的约数就不会有解，有：$$\frac{y}{d} * y^{x-1}+k * \frac{p}{d}=\frac{z}{d}$$

一直递归直到$d=1$，设之间的所有的$d$的乘积为$g$，递归$c$次，令$x’=x-c\ ,\ p’=\frac{p}{g}\ ,\ z=\frac{z}{g}$，$y^{x’} * \frac{y^c}{g} \equiv z’(mod \ p’)$

然后再用BSGS求解。

SPOJMOD Power Modulo Inverted
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
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
ll y,z,p;
ll qpow(ll x,ll n,ll mod){
    ll res=1;
    while(n){
        if(n&1) res=res*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return res;
}
ll gcd(ll x,ll y){
    return (y==0)?x:gcd(y,x%y);
}
ll exBSGS(){
    if(z==1) return 0;
    map<ll,ll>pw;
    ll cnt=0,mul=1;
    for(ll d=gcd(y,p); d!=1; d=gcd(y,p)){
        if(z%d) return -1;
        ++cnt,z/=d,p/=d,mul=(mul*y/d%p);
        if(z == mul) return cnt;
    }
    ll s=z,m=sqrt(p)+1;
    for(ll i=0; i<m; i++){
        pw[s]=i;
        s=s*y%p;
    }
    ll x=qpow(y,m,p);
    s=mul;
    for(ll i=1; i<=m; i++){
        s=s*x%p;
        if(pw.count(s)) return i*m-pw[s]+cnt;
    }
    return -1;
}
int main(){
    while(scanf("%lld %lld %lld",&y,&p,&z)&&(y||z||p)){
        y%=p;
        z%=p;
        ll ans=exBSGS();
        if(ans < 0) puts("No Solution");
        else printf("%lld\n",ans);
    }
}

欧拉降幂

求解$A^B \ mod\ C$，$B \leq 10^{1000000}$

若$a$和$n$为正整数并且互质

$a^{\varphi (n)} \equiv 1(mod \ n)$
$$
a^b \equiv
\begin{cases}
a^{b \ mod \ \varphi(p) } & \text{ gcd(a,p)=1} \newline
a^b & \text gcd(a,p) \neq 1 , b<\varphi(p) \newline
a^{ (b \ mod \ \varphi(p)) + \varphi(p)} & \text gcd(a,p) \neq 1 , b \geq \varphi(p)
\end{cases} \ \ \ \ \ \ \ \ \ \ (mod\ p)
$$

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

#include <bits/stdc++.h>
#define ll __int64
#define mod 10000000007
using namespace std;
char a[1000006];
ll x,z;
ll quickpow(ll x,ll y,ll z)
{
    ll ans=1;
    while(y)
    {
        if(y&1)
            ans=ans*x%z;
        x=x*x%z;
        y>>=1;
    }
    return ans;
}
ll phi(ll n)
{
    ll i,rea=n;
    for(i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            rea=rea-rea/i;
            while(n%i==0)
                n/=i;
         }
    }
    if(n>1)
        rea=rea-rea/n;
    return rea;
}
int main()
{
    while(scanf("%lld %s %lld",&x,a,&z)!=EOF)
    {
        ll len=strlen(a);
        ll p=phi(z);
        ll ans=0;
        for(ll i=0;i<len;i++)
            ans=(ans*10+a[i]-'0')%p;
        ans+=p;
        printf("%lld\n",quickpow(x,ans,z));
    }
    return 0;
}

中国剩余定理

求解
$$
\begin{cases}
x \equiv a_1 (mod\ b_1) \newline
x \equiv a_2 (mod\ b_2) \newline
… \newline
x \equiv a_n (mod\ b_n)
\end{cases}
$$

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
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long lt;

lt read()
{
    lt f=1,x=0;
    char ss=getchar();
    while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
    while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
    return f*x;
}

const int maxn=100010;
int n;
lt ai[maxn],bi[maxn];

lt mul(lt a,lt b,lt mod)
{
    lt res=0;
    while(b>0)
    {
        if(b&1) res=(res+a)%mod;
        a=(a+a)%mod;
        b>>=1;
    }
    return res;
}

lt exgcd(lt a,lt b,lt &x,lt &y)
{
    if(b==0){x=1;y=0;return a;}
    lt gcd=exgcd(b,a%b,x,y);
    lt tp=x;
    x=y; y=tp-a/b*y;
    return gcd;
}

lt excrt()
{
    lt x,y,k;
    lt M=bi[1],ans=ai[1];//第一个方程的解特判
    for(int i=2;i<=n;i++)
    {
        lt a=M,b=bi[i],c=(ai[i]-ans%b+b)%b;//ax≡c(mod b)
        lt gcd=exgcd(a,b,x,y),bg=b/gcd;
        if(c%gcd!=0) return -1; //判断是否无解，然而这题其实不用

        x=mul(x,c/gcd,bg);
        ans+=x*M;//更新前k个方程组的答案
        M*=bg;//M为前k个m的lcm
        ans=(ans%M+M)%M;
    }
    return (ans%M+M)%M;
}

int main()
{
    n=read();
    for(int i=1;i<=n;++i)
    bi[i]=read(),ai[i]=read();
    printf("%lld",excrt());
    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
import java.util.*;
import java.math.BigInteger;
public class Main{
    static BigInteger ai[]=new BigInteger[11000];
    static BigInteger bi[]=new BigInteger[11000];
    static BigInteger lp[]=new BigInteger[150];
    static int n;
    static BigInteger m;
    static String tem;
    static BigInteger rt;
    static BigInteger cr;
    static BigInteger zero=new BigInteger("0");
    static BigInteger one=new BigInteger("1");
    static BigInteger two=new BigInteger("2");
    static BigInteger fuone=new BigInteger("-1");
    static BigInteger maxnt=new BigInteger("1000000000000000");
    static BigInteger x=zero;
    static BigInteger y=zero;
    public static void main(String args[])
    {
        Scanner cin=new Scanner(System.in);
        n=cin.nextInt();
        for (int i=1;i<=n;i++)
        {
            tem=cin.next();
            bi[i]=new BigInteger(tem);
            tem=cin.next();
            ai[i]=new BigInteger(tem);
        }
        rt=excrt();
        lp[0]=zero;
    	lp[1]=one;
    for(int i=2;i<=100;i++) 
        lp[i]=lp[i-1].add(lp[i-2]);
    if(rt.compareTo(one)<=0||rt.compareTo(maxnt)>0){
        System.out.println("Tankernb!");
    }
    else{
        int fg=0;
        for(int i=2;i<=100;i++){
            if(lp[i].compareTo(rt)==0) fg=1;
        }
        if(fg==1)System.out.println("Lbnb!");
        else System.out.println("Zgxnb!");
    }
    }
  
    public static BigInteger exgcd(BigInteger a,BigInteger b)
    {
        if(b.compareTo(zero)==0)
        {
            x=one;
            y=zero;
            return a;
        }
        BigInteger gcd=exgcd(b,a.mod(b));
        BigInteger tp=x;
        x=y;
        y=tp.subtract((a.divide(b)).multiply(y));
        return gcd;
    }
    public static BigInteger excrt()
    {
        BigInteger xx=zero,yy=zero,k;
        BigInteger mo=bi[1],ans=ai[1];//第一个方程的解特判
        for(int i=2;i<=n;i++)
        {
            BigInteger a=mo,b=bi[i];
            BigInteger t=ans.mod(b);
            t=ai[i].subtract(t);
            t=t.add(b);
            BigInteger c=t.mod(b);
            y=yy;x=xx;
            BigInteger gcd=exgcd(a,b),bg=b.divide(gcd);
            xx=x;yy=y;
            if((c.mod(gcd)).compareTo(zero)!=0)
                return fuone; //判断是否无解，然而这题其实不用
            xx=xx.multiply(c.divide(gcd)).mod(bg);  
            ans=ans.add(xx.multiply(mo));//更新前k个方程组的答案
            mo=mo.multiply(bg);//M为前k个m的lcm
            ans=((ans.mod(mo)).add(mo)).mod(mo);
        }
        return ((ans.mod(mo)).add(mo)).mod(mo);
    }
}

线性同余方程

1、方程$ax+by=c$与方程$ax \equiv c (mod \ b)$等价，有整数解的充要条件是$gcd(a,b) % c=0$。

2、若$gcd(a,b)=1$，且$x_0,y_0$为方程$ax+by=c$的一组解，该方程的任意解可表示为：$x=x_0+bt$，$y=y_0+at$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int ex_gcd(int a, int b, int& x, int& y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  int d = ex_gcd(b, a % b, x, y);
  int temp = x;
  x = y;
  y = temp - a / b * y;
  return d;
}
bool liEu(int a, int b, int c, int& x, int& y) {
  int d = ex_gcd(a, b, x, y);
  if (c % d != 0) return 0;
  int k = c / d;
  x *= k;
  y *= k;
  return 1;
}

二次剩余

求解$x \equiv \sqrt{y} \mod p$

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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long long ll;
#define random(a,b) (rand()%(b-a+1)+a)
LL quick_mod(LL a, LL b, LL c){
    LL ans = 1; while (b){ 
    	if (b % 2 == 1) ans = (ans*a) % c; b /= 2; a = (a*a) % c; 
	}
 	return ans;
}
 
LL p;
LL w;//二次域的D值
bool ok;//是否有解
 
struct QuadraticField//二次域
{
    LL x, y;
    QuadraticField operator*(QuadraticField T)//二次域乘法重载
    {
        QuadraticField ans;
        ans.x = (this->x*T.x%p + this->y*T.y%p*w%p) % p;
        ans.y = (this->x*T.y%p + this->y*T.x%p) % p;
        return ans;
    }
    QuadraticField operator^(LL b)//二次域快速幂
    {
        QuadraticField ans;
        QuadraticField a = *this;
        ans.x = 1;
        ans.y = 0;
        while (b)
        {
            if (b & 1)
            {
                ans = ans*a;
                b--;
            }
            b /= 2;
            a = a*a;
        }
        return ans;
    }
};
 
LL Legender(LL a)//求勒让德符号
{
    LL ans=quick_mod(a, (p - 1) / 2, p);
    if (ans + 1 == p)//如果ans的值为-1，%p之后会变成p-1。
        return -1;
    else
        return ans;
}
 
LL Getw(LL n, LL a)//根据随机出来a的值确定对应w的值
{
    return ((a*a - n) % p + p) % p;//防爆处理
}
 
LL Solve(LL n)
{
    LL a;
    if (p == 2)//当p为2的时候，n只会是0或1，然后0和1就是对应的解
        return n;
    if (Legender(n) == -1)//无解
        ok = false;
    srand((unsigned)time(NULL));
    while (1)//随机a的值直到有解
    {
        a = random(0, p - 1);
        w = Getw(n, a);
        if (Legender(w) == -1)
            break;
    }
    QuadraticField ans,res;
    res.x = a;
    res.y = 1;//res的值就是a+根号w
    ans = res ^ ((p + 1) / 2);
    if (ans.x==0) return -1;
    return ans.x;
}
int main()
{
    int T;
    ll b,c;
    p=1000000007;
    ll t1,t2,t3;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%lld%lld",&b,&c);
        if (b*b-4ll*c==0)
        t1=0;
        else
        t1=Solve(b*b-4ll*c);
        if (t1==-1)
        {
            puts("-1 -1");
            continue;
        }
        t2=((b+t1)*quick_mod(2,p-2,p))%p;
        t3=((b-t1+p)%p*quick_mod(2,p-2,p))%p;
        printf("%lld %lld\n",min(t2,t3),max(t2,t3));
    }
 
}

约瑟夫环

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
#include<bits/stdc++.h>
using namespace std;
void joseph(int count, int doom) {
    int alive = count;				// 幸存人数
	int number = 0;				// 报数的数
	int curIndex = 0;			// 当前人下标
	int preIndex = count - 1;   // 前一个人下标
	int index;
	int *circle = NULL;
	circle = (int *) malloc (sizeof(int) * count);
	//对circle数组进行初始化
	for(index = 0; index < count; index++) {
		circle[index] = (index + 1) % count;
	}

	while(alive > 0) {
		number++;
		if(number == doom) {
			alive == 1 ? printf("%d", curIndex+1) : printf("%d,", curIndex+1);
			alive--;
			number = 0;
			circle[preIndex] = circle[curIndex];	//出圈操作
		} else {
			preIndex = curIndex;	//处理下一个人
		}
		curIndex = circle[curIndex];
	}

	free(circle);

}
int main(){
	int n,m;
	cin>>n>>m;
	joseph(n,m);
   	puts("");
}

杜教递推

杜教线性递推

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
#include<bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define pb push_back
#define sz(x) ((int)(x).size())
using namespace std;
typedef long long ll;
typedef vector<ll> VI;
const ll mod=1e9+7;
ll fastpower(ll a, ll b) {
    ll res = 1;
    a %= mod;
    assert(b >= 0);
    for (; b; b >>= 1) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}
namespace linear_seq {
const int N = 10010;
ll res[N], base[N], _c[N], _md[N];
vector<int> Md;
void mul(ll *a, ll *b, int k) {
    rep(i, 0, k + k) _c[i] = 0;
    rep(i, 0, k) if (a[i]) rep(j, 0, k) _c[i + j] =
        (_c[i + j] + a[i] * b[j]) % mod;
    for (int i = k + k - 1; i >= k; i--)
        if (_c[i])
            rep(j, 0, sz(Md)) _c[i - k + Md[j]] =
                (_c[i - k + Md[j]] - _c[i] * _md[Md[j]]) % mod;
    rep(i, 0, k) a[i] = _c[i];
}
int solve(ll n, VI a, VI b) {  // a 系数 b 初值 b[n+1]=a[0]*b[n]+...
                               //        printf("%d\n",sz(b));
    ll ans = 0, pnt = 0;
    int k = sz(a);
    assert(sz(a) == sz(b));
    rep(i, 0, k) _md[k - 1 - i] = -a[i];
    _md[k] = 1;
    Md.clear();
    rep(i, 0, k) if (_md[i] != 0) Md.push_back(i);
    rep(i, 0, k) res[i] = base[i] = 0;
    res[0] = 1;
    while ((1ll << pnt) <= n) pnt++;
    for (int p = pnt; p >= 0; p--) {
        mul(res, res, k);
        if ((n >> p) & 1) {
            for (int i = k - 1; i >= 0; i--) res[i + 1] = res[i];
            res[0] = 0;
            rep(j, 0, sz(Md)) res[Md[j]] =
                (res[Md[j]] - res[k] * _md[Md[j]]) % mod;
        }
    }
    rep(i, 0, k) ans = (ans + res[i] * b[i]) % mod;
    if (ans < 0) ans += mod;
    return ans;
}
VI BM(VI s) {
    VI C(1, 1), B(1, 1);
    int L = 0, m = 1, b = 1;
    rep(n, 0, sz(s)) {
        ll d = 0;
        rep(i, 0, L + 1) d = (d + (ll)C[i] * s[n - i]) % mod;
        if (d == 0)
            ++m;
        else if (2 * L <= n) {
            VI T = C;
            ll c = mod - d * fastpower(b, mod - 2) % mod;
            while (sz(C) < sz(B) + m) C.pb(0);
            rep(i, 0, sz(B)) C[i + m] = (C[i + m] + c * B[i]) % mod;
            L = n + 1 - L;
            B = T;
            b = d;
            m = 1;
        } else {
            ll c = mod - d * fastpower(b, mod - 2) % mod;
            while (sz(C) < sz(B) + m) C.pb(0);
            rep(i, 0, sz(B)) C[i + m] = (C[i + m] + c * B[i]) % mod;
            ++m;
        }
    }
    return C;
}
int gao(VI a, ll n){
    VI c = BM(a);
    c.erase(c.begin());
    rep(i, 0, sz(c)) c[i] = (mod - c[i]) % mod;
    return solve(n, c, VI(a.begin(), a.begin() + sz(c)));
}
};  // namespace linear_seq
//使用linear_seq::gao(ve,n),ve是一个vector变量,n是递推的个数

辗转相除法

求解满足$\frac{lb}{la} < \frac{y}{x} < \frac{rb}{ra}$，最小的$x$和$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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
// b/a  y/x
void cal(ll la, ll lb, ll ra, ll rb, ll &x, ll &y){
	ll m = lb/la + 1;
	if(m <= rb/ra){
		y = m;
		x = 1;
		return ;
	}
	m --;
	lb -= m*la, rb -= m*ra;
	cal(rb, ra, lb, la, y, x);
	y += m*x;//回溯
	return ;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        ll la,lb;
        ll ra,rb;
        ll x,p,k,b;
        scanf("%lld %lld",&p,&x);
        la=x;
        lb=p;
        ra=x-1;
        rb=p;
        cal(la,lb,ra,rb,k,b);
        printf("%lld/%lld\n",b*x-k*p,b);
    }
}

Miller_Pabin 素数判定

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
ll qmul(ll a,ll b,ll mod){
    ll ans = 0;
    while(b){
        if(b&1) ans = (ans+a)%mod;
        a = (a+a)%mod;   //相当于a*1、a*2、a*4、a*8的增加
        b = b>>1;
    }
    return ans;
}
ll qpow(ll x,ll n,ll mod){
    ll ans=1;
    while(n){
        if(n&1) ans=(ans*x)%mod;
        x=x*x%mod;
        n>>=1;
    }
    return ans;
}
ll prime[6] = {2, 3, 5, 233, 331};
bool Miller_Rabin(ll p){
    if(p < 2) return 0;
    if(p != 2 && p % 2 == 0) return 0;
    ll s = p - 1;
    while(! (s & 1)) s >>= 1;
    for(int i = 0; i < 5; ++i) {
        if(p == prime[i]) return 1;
        ll t = s, m = qpow(prime[i], s, p);
        while(t != p - 1 && m != 1 && m != p - 1) {
            m = qmul(m, m, p);
            t <<= 1;
        }
        if(m != p - 1 && !(t & 1)) return 0;
    }
    return 1;
}

大数分解质因数

Forbechenko v Rodvsky

求使得$\frac{A}{B}$变成有限分数的$k$进制的最小的$k$。

结论：最小的$k$就是$\frac{\frac{A}{gcd(A,B)}}{\frac{B}{gcd(A,B)}}$中$\frac{B}{gcd(A,B)}$的所有质因数相乘的积$ans$，答案就是$\beta = min(2,ans)$。

$pollard _ rho$模板

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
namespace pollard_rho {
    const int C = 2307;
    const int S = 10;
    mt19937 rd(time(0));
    vector<ll> ve;

    ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

    ll qmul(ll a, ll b, ll mod) {
        ll ans = 0;
        a %= mod;
        while (b) {
            if (b & 1)
                ans = (ans + a) % mod;
            b >>= 1;
            a = (a << 1) % mod;
        }
        return ans;
    }

    ll mul(ll a, ll b, ll mod) {
        return a * b % mod;
    }

    ll power(ll a, ll b, ll mod) {
        ll res = 1;
        a %= mod;
        while (b) {
            if (b & 1)res = qmul(res, a, mod);
            a = qmul(a, a, mod);
            b >>= 1;
        }
        return res;
    }

    bool check(ll a, ll n) {
        ll m = n - 1, x, y;
        int j = 0;
        while (!(m & 1))m >>= 1, j++;
        x = power(a, m, n);
        for (int i = 1; i <= j; x = y, i++) {
            y = qmul(x, x, n);
            if (y == 1 && x != 1 && x != n - 1)return 1;
        }
        return y != 1;
    }

    bool miller_rabin(ll n) {
        ll a;
        if (n == 1)return 0;
        if (n == 2)return 1;
        if (!(n & 1))return 0;
        for (int i = 0; i < S; i++)if (check(rd() % (n - 1) + 1, n))return 0;
        return 1;
    }

    ll pollard_rho(ll n, int c) {
        ll i = 1, k = 2, x = rd() % n, y = x, d;
        while (1) {
            i++;
            x = (qmul(x, x, n) + c) % n, d = gcd(y - x, n);
            if (d > 1 && d < n)return d;
            if (y == x)return n;
            if (i == k)y = x, k <<= 1;
        }
    }

    void findfac(ll n, int c) {
        if (n == 1)return;
        if (miller_rabin(n)) {
            ve.push_back(n);
            return;
        }
        ll m = n;
        while (m == n)m = pollard_rho(n, c--);
        findfac(m, c);
        findfac(n / m, c);
    }

    vector<pli> solve(ll n) {
        vector<pli> res;
        ve.clear();
        findfac(n, C);
        sort(ve.begin(), ve.end());
        for (auto x:ve) {
            if (res.empty() || res.back().first != x)res.push_back({x, 1});
            else res.back().second++;
        }
        return res;
    }
}
ll solve(ll a,ll b){
    ll tmp=__gcd(a,b);
    a/=tmp;
    b/=tmp;
    vector<pli>ans;
    ans=pollard_rho::solve(b);
    ll res=1;
    for(auto x:ans){
        res*=x.first;
    }
    return res;
}
int main(){
    ll a,b;
    scanf("%lld %lld",&a,&b);
    printf("%lld\n",max(2ll,solve(a,b)));
}

阶乘素因子出现的次数

$$
cnt(x)=\left \lfloor \frac{n}{x^1} \right \rfloor+\left \lfloor \frac{n}{x^2} \right \rfloor+…+\left \lfloor \frac{n}{x^i} \right \rfloor if(x^i<=n)
$$

1
2
3
4
5
6
7
8
9
10
11
12
ll now=prime[i],sum=0;
while(now<=n){
	sum+=n/now;
	now=now*prime[i];
}
//or
ll cnt=0;
ll tmp=n;
while(tmp/pr[i]){
  	cnt+=(tmp/pr[i]);
	tmp/=pr[i];
}

原根

如果 ${ r * 2 ^ k + 1 }$ 是个素数，那么在 $ {mod \ r * 2 ^ k+1} $ 意义下，可以处理 $ 2^k $以内规模的数据。

记录一下 $a ∗ 2^k+1$型素数的原根 $g$。

$a * 2^k + 1$ $a$ $k$ $g$
3 1 1 2
5 1 2 2
17 1 4 3
97 3 5 5
193 3 6 5
257 1 8 3
7681 15 9 17
12289 3 12 11
40961 5 13 3
65537 1 16 3
786433 3 18 10
5767169 11 19 3
7340033 7 20 3
23068673 11 21 3
104857601 25 22 3
167772161 5 25 3
469762049 7 26 3
998244353(常见) 119 23 3
1004535809 479 21 3
1998585857 953 21 3
2013265921 15 27 31
2281701377 17 27 3
3221225473 3 30 5
75161927681 35 31 3
77309411329 9 33 7
206158430209 3 36 22
2061584302081 15 37 7
2748779069441 5 39 3
6597069766657 3 41 5
39582418599937 9 42 5
79164837199873 9 43 5
263882790666241 15 44 7
1231453023109121 35 45 3
1337006139375617 19 46 3
3799912185593857 27 47 5
4222124650659841 15 48 19
7881299347898369 7 50 6
31525197391593473 7 52 3
180143985094819841 5 55 6
1945555039024054273 27 56 5
4179340454199820289 29 57 3

勾股定理构造

$(\frac{n^2}{4}-1)^2+n^2=(\frac{n^2}{4}+1)^2$

$(\frac{n^2-1}{2})^2+n^2=(\frac{n^2+1}{2})^2$

几何

二维几何

三维几何

求两个平面的最短距离
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 <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
 
struct Point {
  double x, y, z;
  Point operator-(const Point& p) const { return {x-p.x, y-p.y, z-p.z}; }
  Point operator+(const Point& p) const { return {x+p.x, y+p.y, z+p.z}; }
  Point operator*(double c) const { return {x*c, y*c, z*c}; }
  Point operator/(double c) const { return {x/c, y/c, z/c}; }
  double lensqr() const { return x*x+y*y+z*z; }
  double len() const { return sqrt(x*x+y*y+z*z); }
  friend ostream& operator<<(ostream& out, const Point& p) {
    out << '(' << p.x << ',' << p.y << ',' << p.z << ')'; return out;
  }
};
 
Point crossP(const Point& a, const Point& b) {
  return {a.y*b.z-a.z*b.y, a.z*b.x-a.x*b.z, a.x*b.y-a.y*b.x};
}
 
double dotP(const Point& a, const Point& b) {
  return a.x*b.x + a.y*b.y + a.z*b.z;
}
 
int main() {
  int T, prob=1;
  for (cin >> T; T--;) {
    vector<Point> t1(3), t2(3);
    for (int i = 0; i < 3; i++) cin >> t1[i].x >> t1[i].y >> t1[i].z;
    for (int i = 0; i < 3; i++) cin >> t2[i].x >> t2[i].y >> t2[i].z;
    double ret = 1e9;
    for (int swp = 0; swp < 2; swp++) {
      swap(t1, t2);
      for (int rot1 = 0; rot1 < 3; rot1++) {
        rotate(t1.begin(), t1.begin()+1, t1.end());
        for (int rot2 = 0; rot2 < 3; rot2++) {
          rotate(t2.begin(), t2.begin()+1, t2.end());
 
          // Vertex-vertex
          ret = min(ret, (t2[0]-t1[0]).len());
 
          // Vertex-edge
          double dist = dotP(t2[0]-t1[0], t1[1]-t1[0]) / (t1[1]-t1[0]).lensqr();
          if (dist > 0 && dist < 1) {
            Point p = t1[0]*(1-dist) + t1[1]*dist;
            ret = min(ret, (t2[0]-p).len());
          }
 
          // Vertex-triangle
          Point normal = crossP(t1[1]-t1[0], t1[2]-t1[0]);
          normal = normal / normal.len();
          double h = dotP(normal, t2[0]-t1[0]);
          Point base = t2[0] - normal*h;
          if (dotP(normal, crossP(t1[1]-t1[0], base-t1[0])) > 0 &&
              dotP(normal, crossP(t1[2]-t1[1], base-t1[1])) > 0 &&
              dotP(normal, crossP(t1[0]-t1[2], base-t1[2])) > 0) {
            ret = min(ret, fabs(h));
          }
 
          // Edge-edge
          normal = crossP(t1[1]-t1[0], t2[1]-t2[0]);
          double cp1 = dotP(normal, crossP(t2[1]-t2[0], t1[0]-t2[0]));
          double cp2 = dotP(normal, crossP(t2[1]-t2[0], t1[1]-t2[0]));
          double cp3 = dotP(normal, crossP(t1[1]-t1[0], t2[0]-t1[0]));
          double cp4 = dotP(normal, crossP(t1[1]-t1[0], t2[1]-t1[0]));
          if (cp1*cp2 < 0 && cp3*cp4 < 0) {
            Point p1 = (t1[1]*cp1 - t1[0]*cp2) / (cp1-cp2);
            Point p2 = (t2[1]*cp3 - t2[0]*cp4) / (cp3-cp4);
            ret = min(ret, (p2-p1).len());
          }
 
          // Edge-triangle (and triangle-triangle)
          normal = crossP(t1[1]-t1[0], t1[2]-t1[0]);
          normal = normal / normal.len();
          cp1 = dotP(normal, t2[0]-t1[0]);
          cp2 = dotP(normal, t2[1]-t1[0]);
          if (cp1*cp2 < 0) {
            Point p = (t2[1]*cp1 - t2[0]*cp2) / (cp1-cp2);
            if (dotP(normal, crossP(t1[1]-t1[0], p-t1[0])) > 0 &&
                dotP(normal, crossP(t1[2]-t1[1], p-t1[1])) > 0 &&
                dotP(normal, crossP(t1[0]-t1[2], p-t1[2])) > 0) {
              ret = 0.0;
            }
          }
        }
      }
    }
    printf("%.12lf\n", ret);
  }
}
thanks!