前言

侧边栏炸了

短期的目标

笛卡尔树

容斥

带标号联通无向图计数

带标号欧拉图计数

dp套dp

斜率优化dp

树剖换根

很多数据结构

数据结构

树剖

实质

是一个重链剖分，寻找lcalca的时候每次规模减半，故时间复杂度O(nlogn)O(nlogn)

用处

求lcalca或者水LCTLCT的部分分

操作

dfs1dfs1 得到深度关系以及重儿子，父子关系

dfs2dfs2 进行剖分，得到重链

换根 本质上并不需要换根，我们完全可以用之前求得的id序列来描述这个树，因为重新换根来重建这棵树是完全没必要的(在复杂度上面不太占优势)

首先我们考虑换根后怎么求得lcalca，显然是可以

线段树

主席树

beautiful pair

题意就是找到满足 形如 al∗ar<=max⁡i=lraia_l*a_r<=\max\limits_{i=l}^{r}a_i 的个数

题面的确挺简洁，然而想了好久也不知道怎么做，因为要考虑 ai,aj,amaxa_i,a_j,a_{max} 的其中两个

[^1]: 如果枚举 aia_i 与 amaxa_{max} 那么需要找到 maxmax 到 nn 的所有小于等于 ⌊amaxai⌋\lfloor\frac{a_{max}}{a_i}\rfloor aja_j 的个数 或者我们枚举ai,aja_i,a_j 看他们中的最大值是某满足

，而且还要一种数据结构（能查最值，或者能查大于/小于某个数的个数 ），在怎么都优化不下去了

然而这题分治的做法很巧妙，不过太难想出来了，我们把原序列看做一颗笛卡尔树，每一个节点变成了一段区间，依据笛卡尔树的结构，很显然我们找到了所有最值，此时我们把每个区间从最值部分划开，我们只要贪心地处理长度较小的那段区间，对每个数求小于等于 ⌊amaxai⌋\lfloor\frac{a_{max}}{a_i}\rfloor 的 aja_j 的数量就行了，不难发现每个点最多被计算 log⁡2n\log_2n 次（本题是分治小的区间，如果这个点在小的区间统计次数超过了 log⁡2n\log_2n 次，那大的区间已经超过了 nn 这显然是不成立的）

因此复杂度就分析出来了 O(nlog⁡2n)O(n\log^2n)

但是你要注意的是虽然所有点贡献 nlog⁡nn\log n 次，但并不代表区间长度是这么多，如果你暴力求区间最大值的话只能拿到 9090 分，所以你得用 stst 表来做一做

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
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

#define ls(i) t[i].l
#define rs(i) t[i].r
#define int long long

using namespace std;

const int maxn=200010;

int a[maxn],b[maxn],n,rt[maxn],tot,ans,cnt;
int stb[maxn][18],l2[maxn];

struct segment_tree{ //板子部分，不多讲
	
	struct tree{
		int l,r,sum;
	}t[maxn*30];
	
	void change_tree(int &i,int looker,int l,int r,int x)
	{
		if(!i) i=++tot; 
		t[i]=t[looker];
		t[i].sum++;
		if(l==r) return ;
		int mid=(l+r)>>1;
		if(x<=mid) change_tree(ls(i)=++tot,ls(looker),l,mid,x);
		else change_tree(rs(i)=++tot,rs(looker),mid+1,r,x);
	} 
	
	int ask_sum_tree(int i,int l,int r,int x,int y)
	{
		if(y<x) return 0;
		if(x>r||y<l) return 0;
		int ans=0;
		if(l>=x&&r<=y) return t[i].sum;
		int mid=(l+r)>>1;
		if(x<=mid) ans+=ask_sum_tree(ls(i),l,mid,x,y);
		if(y>mid) ans+=ask_sum_tree(rs(i),mid+1,r,x,y);
		return ans;
	}
	
}st;

void getans(int l,int r)
{
	if(l>r) return ;
	if(l==r)
	{
		if(a[l]==1||a[l]==0) ans++;
		return ;
	}
	int i,mmx;
	int t1=stb[l][l2[r-l+1]];
	int t2=stb[r-(1<<(l2[r-l+1]))+1][l2[r-l+1]];
	if(a[t1]>=a[t2]) mmx=t1; else mmx=t2;
	int sz1=(mmx-l+1),sz2=(r-mmx+1);
	if(sz1<sz2)
	{
		for(i=l;i<=mmx;i++) 
		ans+=st.ask_sum_tree(rt[r],1,cnt,1,a[mmx]/a[i])-st.ask_sum_tree(rt[mmx-1],1,cnt,1,a[mmx]/a[i]);
	}
	else
	{
		for(i=mmx;i<=r;i++) 
		ans+=st.ask_sum_tree(rt[mmx],1,cnt,1,a[mmx]/a[i])-st.ask_sum_tree(rt[l-1],1,cnt,1,a[mmx]/a[i]);
	}
	getans(l,mmx-1);
	getans(mmx+1,r);
}

signed main()
{
	ios::sync_with_stdio(false);
	register int i,j;
	cin>>n;
	l2[0]=-1;
	for(i=1;i<=n;i++) cin>>a[i],b[i]=a[i],stb[i][0]=i,l2[i]=l2[i>>1]+1;  //预处理
	for(j=1;j<=17;j++)
	for(i=1;i<=n;i++) 
	stb[i][j]=(a[stb[i][j-1]]<a[stb[i+(1<<(j-1))][j-1]])?(stb[i+(1<<(j-1))][j-1]):(stb[i][j-1]);
	cnt=1e9;
	for(i=1;i<=n;i++) st.change_tree(rt[i],rt[i-1],1,cnt,a[i]);
	getans(1,n);
	cout<<ans<<endl;
	return 0;
}

dp部分

笛卡尔树

P5854

粗看一眼题面范围发现n≤107n\leq 10^7,果断考虑单调栈

说一下单调栈思路

首先我们要保证编号满足二叉搜索树，所以只需要考虑维护这个树的右子链（这里插入才能有可能不改变这个树的中序遍历）

我们再来看看这个树，而且新插入的弟这个点ii一定没有左子树，我们保持这个栈的单调性（因为必须保证一个方向上的路径单调递增），所以我们一定可以得到一个位置pp（pp就是当前单调栈的栈顶），我们把pp的右儿子给当前节点ii作为左儿子（显然不会出问题）,因此正确性显然，而且时间复杂度也可以得到是O(N)O(N)(因为单调栈)

同时发现这道题没有负数，所以我们可以把读写简单一点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<touwenjian.h>

#define int long long
 
using namespace std;

const int maxn=10001000;
int l[maxn],r[maxn],a[maxn],s[maxn],stp;
int n,m;
int ans1,ans2;

inline void qread(int &ans)
{
	ans=0; static char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) {ans=ans*10+c-'0';c=getchar();}
	return ;
} 

signed main()
{
	register int i;
	qread(n);
	for(i=1;i<=n;i++)qread(a[i]);
	s[++stp]=0;
	for(i=1;i<=n;i++)
	{
		while(stp&&a[i]<a[s[stp]]) l[i]=s[stp--];
		if(stp) r[s[stp]]=i;
		s[++stp]=i;
	}
	for(i=1;i<=n;i++)
	{
		ans1=ans1^(1ll)*(i*(l[i]+1));
		ans2=ans2^(1ll)*(i*(r[i]+1));
	}
	printf("%lld %lld",ans1,ans2);
	return 0;
}


P3592 [POI2015]MYJ

题意就是确定每个人会在[l,r][l,r]这个区间挑一家最便宜的喜洗车店洗车，但是如果这些最便宜的洗车店价格也大于cic_i的话，那么这人就不洗车了，花费为00

现在问你怎样安排洗车店价格使总的消费最多

胡乱分析一下，首先答案应该由区间最小值贡献

我们考虑一个区间dpdp，设dp[l][r][k]dp[l][r][k]表示区间[l,r][l,r]最小值为kk能得到的最多消费

这东西我们就要考虑怎么转移，首先合并的式子应该写的出来

dp[l][r][k]=max{dp[i][pos−1][x]+dp[pos+1][r][y]+ctr(pos)}dp[l][r][k]=max \{dp[i][pos-1][x]+dp[pos+1][r][y]+ctr(pos)\}这里的ctr(pos)ctr(pos)表示pospos对答案的贡献，显然有

x≥k,y≥k,pos∈[l,r]x\geq k,y\geq k,pos \in[l,r]

至于为啥这个断点在l,rl,r可以取，是因为我们也要考虑它的最小值

现在的难点就到了计算贡献

考虑设置一个g[pos][k]g[pos][k]表示经过pospos并且最低价值大于等于kk的数量

看来ctr(pos)=c[pos]∗g[pos][k]ctr(pos)=c[pos]*g[pos][k]

不过到这里还没完，这道题要求输出方案数，所以我们还需要记录一下转移的顺序

f[i][j][k]f[i][j][k]记录dp[i][j][k]dp[i][j][k]中kk的位置

p[i][j][k]p[i][j][k]记录dp[i][j][k]dp[i][j][k]中k的大小

实际上上面这东西我们发现每个点只有一个是最优的，考虑mx[i][j][k]mx[i][j][k]表示[l,r][l,r]最小值大于等于kk能取到的位置，发现转移仅仅多了个和dp[i][j][k+1]dp[i][j][k+1]比较，所以直接维护mx[i][j][k]mx[i][j][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
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
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxn=55;
const int maxm=8040;

int lef[maxm],rig[maxm],looker[maxm],c[maxm];
int n,m;
int f[maxn][maxn][maxm];
int g[maxn][maxm];
int p[maxn][maxn][maxm];
int mx[maxn][maxn][maxm];
int nl;
int ta[maxm]; 
void getpla(int l,int r,int cos)
{
	if(l>r) return ;
	int ppla=f[l][r][cos=p[l][r][cos]];
	ta[ppla]=looker[cos];
	getpla(l,ppla-1,cos); getpla(ppla+1,r,cos); 
} 
int main()
{
	ios::sync_with_stdio(false);
	register int i,j,k,l;
	cin>>n>>m;
	for(i=1;i<=m;i++) cin>>lef[i]>>rig[i]>>c[i],looker[i]=c[i];
	sort(looker+1,looker+m+1);
	nl=unique(looker+1,looker+m+1)-looker-1;
	for(i=1;i<=m;i++) c[i]=lower_bound(looker+1,looker+nl+1,c[i])-looker;
	for(i=n;i;i--)
	for(j=1;j<=n;j++)
	{
		for(k=i;k<=j;k++) for(l=0;l<=nl;l++) g[k][l]=0;
		for(k=1;k<=m;k++) if(lef[k]>=i&&rig[k]<=j) for(l=lef[k];l<=rig[k];l++) g[l][c[k]]++;
		for(k=i;k<=j;k++) for(l=nl-1;l;l--) g[k][l]+=g[k][l+1];
		for(k=nl;k;k--)
		{
			int mmx=0,ma=0;
			for(l=i;l<=j;l++) {mmx=mx[i][l-1][k]+mx[l+1][j][k]+g[l][k]*looker[k]; if(ma<=mmx) ma=mmx,f[i][j][k]=l;}
			if(ma>=mx[i][j][k+1]) mx[i][j][k]=ma,p[i][j][k]=k;
			else mx[i][j][k]=mx[i][j][k+1],p[i][j][k]=p[i][j][k+1];
		}
	}
	getpla(1,n,1);
	cout<<mx[1][n][1]<<endl;
	for(i=1;i<=n;i++) cout<<ta[i]<<" "; 
}

普通但是思维难度大的dp

CF568E Longest Increasing Subsequence

一个普通(指不用很多优化)但是思维难度大的dp

首先题目要求我们找最大的一个上升子序列，因此对其他不会出现在lislis的−1-1的点没有要求（除了每个点只能被选一次）

换句话说我们只需要着重处理在LISLIS的aia_i就好了

首先我们并不知道这东西在哪里，所以我们把n+1n+1位设成一个极大的数，这样就能保证这个点是LISLIS的末尾

我们现在的难点就是在怎么回溯找出这个LIS了

我们假设现在数组已经没有−1-1了

回溯就比较好办了

g[i]g[i]表示长度为ii的上升子序列最大元素的下标

p[i]p[i]表示a[i]a[i]可以接在的最长上升序列的最大元素下标

另外题面（似乎）还有个隐藏条件，就是保证必须有解

另外虽然题面不保证可以填的mm个数字不相等，但是这东西似乎是在诱导你去重，但是去重说不定就能被hack了（

要回溯的话我们先找到i=g[len[n+1]]i=g[len[n+1]]然后不断i=p[i]i=p[i]到i=0i=0就跳出去即可

但是实际上我们已经知道最大元素的下标了i=n+1i=n+1作为起始就可以了

好了现在我们想一下有−1-1的情况

因为填−1-1也要满足m≥km\geq k，所以我们可以让每个可以用来填的数贡献一下f[i],g[i]f[i],g[i]（因为我们只需要找到答案，答案中这些数每个也只能出现一次，但是我们要改很多次，这个时候每个都二分时间复杂度基本炸了，不难发现我们用两个双指针就可以解决这个问题）

但是这做法显然是甩锅给回溯，所以我们回溯也要来解决一下，首先我们的回溯记录当前的值vv(因为我们不能确定a[i]=−1a[i]=-1的点的取值)

回溯的时候这个点ii和前面那个点p[i]p[i]对应的aa都不是00的话，那我们不管（记得刷新v）

如果a[p[i]]=0a[p[i]]=0那么我们显然是从那边转移了，此时贪心地填最大的比a[i]a[i]小的数即可

如果a[i]为-1的话由于我们并没有维护p[i]p[i]，所以我们要先找到，怎么找呢，我们令len[i]len[i]表示以a[i]a[i]结尾的LISLIS长度，很容易就发现这东西也可以在a=−1a=-1的时候维护，所以我们用这个来比较，如果len[k]==len[i]−1len[k]==len[i]-1那么下一个地方我们跳到kk即可

但是如果两个点都是−1-1的话，我们不可能直接跳，因为我们还得维护当前的值，所以我们还要找出来那个−1-1的位置并且二分，如果有多个kk的话显然这不一定是等价的，所以我们贪心地找到最接近的一个。

好了大概就这么多情况了，由于每个数只能被填一次(a=ba=b这种大概可以算两次？)，所以我们记录一个visvis数组让他来标记，剩下的−1-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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxn=100600;

int n,m;
int a[maxn],f[maxn],st[maxn],ed[maxn],p[maxn],b[maxn],len[maxn],g[maxn]; 
int vis[maxn];
int ans[maxn];

inline void getans()
{
	int i,j;
	memset(f,0x3f,sizeof(f));
	f[0]=0; 
	for(i=1;i<=n;i++)
	{
		if(a[i]!=-1)
		{
			int pla=lower_bound(f+1,f+n+1,a[i])-f-1;
		    len[i]=pla+1; p[i]=g[pla]; g[pla+1]=i; f[pla+1]=a[i];
		}
		else
		{
			int l1,l2; 
			for(l1=m,l2=n;l1;l1--)
			{
				while(f[l2]>=b[l1]) l2--;
				f[l2+1]=b[l1],g[l2+1]=i;
			}
		}
	}

	int l,v;
	for(i=n,v=a[n],l=len[n];l;l--)
	{
		if(a[i]!=-1)
		{
			if(a[p[i]]!=-1) i=p[i],v=a[i];
			else 
			{
				int target=lower_bound(b+1,b+m+1,a[i])-b-1;
				vis[target]=1;i=p[i],v=ans[i]=b[target];				
			}
		}
		else 
		{
			int bj=0;
			for(int k=i-1;k;k--) if(a[k]>=0&&a[k]<v&&len[k]==l-1) {i=k,v=a[k];bj=1; break;}
			if(bj) continue;
			for(int k=i-1;k;k--) if(a[k]==-1) {int target=lower_bound(b+1,b+m+1,v)-b-1;	vis[target]=1; i=k,v=ans[i]=b[target]; break;}
		}
	}
	for(i=1,j=m;i<=n;i++) 
	{
		if(a[i]!=-1) ans[i]=a[i];
		else if(!ans[i])
		{
			while(vis[j]) j--; 
			vis[j]=1; ans[i]=b[j];
		}
	}
}


inline void printans()
{
	for(int i=1;i<n;i++) cout<<ans[i]<<" ";
}

int main()
{
	ios::sync_with_stdio(false);
	register int i,j;
	cin>>n; for(i=1;i<=n;i++) 
	{
		cin>>a[i];
		//if(a[i]==-1) a[i]=0; 这是一个不读题带来的血的教训
	}
	a[++n]=0x3f3f3f3f;
	cin>>m; for(i=1;i<=m;i++) cin>>b[i];
	sort(b+1,b+m+1);
	getans();
	printans();
}

CF704C

题目大意给定nn个变量mm个形如$x_i \or x_j 或者或者x_i的表达式，不保证的表达式，不保证i\not=j，也不保证每个变量都会出现一次，问他们异或值为1的方案书（输入中的，也不保证每个变量都会出现一次，问他们异或值为1的方案书（输入中的x_{-i}表示表示x_i取反,每个取反,每个x_i$都为0或者1）

首先这东西考虑有可能相互影响，我们先分出来一些互不影响的，然后c[i]c[i]表示这群互不影响的东西对答案的贡献

考虑这里似乎是一个有限状态自动机，而且也是markovmarkov链，那是不是直接在图上跑dpdp就行了啊

这样我们就相当于能构造一张图，xix_i与xjx_j相互影响就体现在xi,xjx_i, x_j有一条无向边，现在我们先写出来这张图。

然后我们描述每个连通分量状态，发现只需要描述这几个

c[i]c[i]表示这个连通块为0,1的方案数

f[i][j]f[i][j]表示前ii(包含ii)的异或值为ii且当前为jj的方案数

这东西转移很好想，f[i][1]f[i][1]就是上次异或值为$0 \times $这次为11的方案数目++上次异或值为11这次为00的方案数,f[i][0]f[i][0]类似

现在考虑算cc

优先考虑连通块大小为11的情况

如果这个连通块大小为11，并且表达式大小为11，那就是显然的c[0]=c[1]=1c[0]=c[1]=1

如果表达式大小为22，如果表达式相同的话i=ji=j那么有c[0]=c[1]=1c[0]=c[1]=1

如果他们表达式不满足∣i∣=∣j∣|i|=|j|那么显然c[1]=3,c[0]=1c[1]=3,c[0]=1

最后剩下一种情况，就是∣i∣=∣j∣|i|=|j|,此时c[1]=2,c[0]=0c[1]=2,c[0]=0

好了我们解决了连通块大小为1的情况了，现在我们加大力度

我们把每个表达式都看作大小为2

x_i \or x_j允许xj=0x_j=0

首先我们处理是一条链的情况(这个连通块最多是一条链)

然而目前这是一张无向图，我们得给他定向

好在每个点度最大为22，我们虽然只知道一个方向，但是剩下的那个方向不言而喻

定向完了后我们就相当于在DAGDAG上面dpdp，由于我们已经知道拓扑序了，所以我们不用再跑一次图了

对于环，我们只需要破环成链

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

#define int long long

using namespace std;

const int maxn=100100;
const int modp=1e9+7;

int f[maxn][2];
int g[maxn][2][2];
int c[2];
int n,m,ind[maxn],size,head[maxn];
int vis[maxn];
int cnt=0,ans=1;

vector <int> a[maxn],b[maxn],s;

struct edge{
	int next,to,dis;
}e[maxn*2];

inline void addedge(int next,int to)
{
	e[++size].to=to;
	e[size].next=head[next];
	head[next]=size;
}

inline void getxl(int t,int fat)
{
	int i,j;
	s.push_back(t);
	vis[t]=1;
	for(i=head[t];i;i=e[i].next)
	{
		j=e[i].to;
		if(j==fat||vis[j]) continue;
		getxl(j,t);
	}
}

inline void clr(int x)
{
	int i,j,k;
	for(i=0;i<=x;i++)
	for(j=0;j<=1;j++)
	for(k=0;k<=1;k++)
	g[i][j][k]=0;
 } 

inline void dp(int l1,int l2,int r1,int r2)
{
	int i,j,k,l; 
	int non=s.size();
	clr(non);
	for(i=l1;i<=r1;i++) g[0][0][i]=1;
	if(!a[s[0]][1]||(abs(a[s[0]][1])!=abs(a[s[1]][0])&&abs(a[s[0]][1])!=abs(a[s[1]][1]))) swap(a[s[0]][1],a[s[0]][0]);
	for(i=1;i<non;i++) if(abs(a[s[i]][0])!=abs(a[s[i-1]][1])) swap(a[s[i]][0],a[s[i]][1]);
	for(i=1;i<=non;i++)
	{
		int looker=s[i-1];
		for(j=0;j<=1;j++)
		for(k=0;k<=1;k++)
		for(l=0;l<=1;l++)
		{
			g[i][(((a[looker][0]<0)^j)|((a[looker][1]<0)^k))^l][k]+=g[i-1][l][j];
			g[i][(((a[looker][0]<0)^j)|((a[looker][1]<0)^k))^l][k]%=modp;
		}
	}
	for(i=0;i<=1;i++)
	for(j=l2;j<=r2;j++)
	c[i]+=g[non][i][j],c[i]%=modp;
}

inline void getans()
{
	if(s.size()==1)
	{
		int looker=s[0];
		if(a[looker].size()==1) {c[1]=1,c[0]=1; return ;}
		if(abs(a[looker][1])!=abs(a[looker][0])) {c[1]=3,c[0]=1;return ;}
		if(a[looker][0]==a[looker][1]) {c[1]=c[0]=1; return ;}
		if(a[looker][0]!=a[looker][1]) {c[1]=2; c[0]=0; return ;}
	}
	int i,target=0;
	c[0]=c[1]=0;
	int sz=s.size();
	for(i=0;i<sz;i++) if(ind[s[i]]==1) target=s[i];
	if(target)
	{
		for(i=0;i<sz;i++) vis[s[i]]=0;
		s.clear(); getxl(target,target);
		int l1,l2,r1,r2;
		r1=r2=1; l1=l2=0;
		int looker=s[0];if(a[looker].size()==1) a[looker].push_back(0),r1=0;
		looker=s.back();if(a[looker].size()==1) a[looker].push_back(0),r2=0;
		dp(l1,l2,r1,r2);
		return ;
	}
	dp(0,0,0,0); dp(1,1,1,1);
	return ;
}

signed main()
{
	ios::sync_with_stdio(false);
	cin>>n>>m;
	int opt,t,t1,t2;
	register int i,j;
	for(i=1;i<=n;i++)
	{
		cin>>opt;
		while(opt--) cin>>t,a[i].push_back(t),b[abs(t)].push_back(i);
	}
	for(i=1;i<=m;i++)
	{
		if(b[i].size()==1) continue;
		if(b[i].size()==0){ans*=2; ans%=modp;  continue;}
		t1=b[i][0],t2=b[i][1];
		addedge(t1,t2);addedge(t2,t1);
		ind[t1]++; ind[t2]++;
	}
	f[0][0]=1;
	for(i=1;i<=n;i++)
	{
		if(!vis[i])
		{
			if(!s.empty()) s.clear();
			cnt++;
			getxl(i,i);
			getans();
			for(j=0;j<=1;j++)
			f[cnt][j]=(f[cnt-1][j]*c[0]+f[cnt-1][j^1]*c[1])%modp;
		}
	}
	ans=ans*f[cnt][1];
	ans%=modp;
	cout<<ans<<endl;
}

P4229 某位歌姬的故事

容斥

[HAOI2008]硬币购物

大意

有四种硬币，面值分别为c1,c2,c3,c4c_1,c_2,c_3,c_4并且这个人第ii种硬币带了ii个，问他买价值为ss的东西付款方法有多少种

一看根本看不出来是容斥dpdp

但是他就是（

对单个硬币来说,fs−fs−ci∗(d+1)f_s-f_{s-c_i*(d+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
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

#define int long long

using namespace std;

const int maxn=100100;

int n,m;
int f[maxn];
int c[5],d[5];

signed main()
{
	ios::sync_with_stdio(false);
	register int i,j;
	cin>>c[1]>>c[2]>>c[3]>>c[4];
	cin>>m;
	f[0]=1;
	for(j=1;j<=4;j++) for(i=1;i<=maxn;i++) if(i-c[j]>=0) f[i]+=f[i-c[j]];
	while(m--)
	{
		cin>>d[1]>>d[2]>>d[3]>>d[4];
		cin>>n;
		int tmp=0;
		for(i=0;i<=15;i++)
		{
		    int t=n,cnt=0;
			for(j=1;j<=4;j++) if(i&(1<<(j-1))) t-=c[j]*(d[j]+1),cnt++;
			if(t<0) continue;
			tmp+=f[t]*((cnt&1)?-1:1);
		}
		cout<<tmp<<endl;
	}
}

斜率优化

P3195 [HNOI2008]玩具装箱

貌似有个套路，设f[i]f[i]表示已经处理好了前ii个的最小花费

然后能够列出这个式子

f[i]=min⁡j<i(f[j]+(sum[i]−sum[j]+i−j−l−1)2)f[i]=\min_{j<i} \limits(f[j]+(sum[i]-sum[j]+i-j-l-1)^2)

令s[i]=i+sum[i]s[i]=i+sum[i]

有
min⁡j<i(f[j]+(s[i]−s[j]−(l+1))2)\min_{j<i}\limits(f[j]+(s[i]-s[j]-(l+1))^2)

令l++l++，懒得写minmin于是可以变成

f[i]=f[j]+(s[i]−s[j]−l)2f[i]=f[j]+(s[i]-s[j]-l)^2

拆开括号

f[i]=f[j]+s[i]2+(s[j]+l)2−2∗s[i]∗(s[j]+l)f[i]=f[j]+s[i]^2+(s[j]+l)^2-2*s[i]*(s[j]+l)

考虑斜率优化一般形式，有y=kx+by=kx+b

一般来说bb与斜率无关，我们考虑最难去化的，并且把答案无关的也丢进去

b=f[i]−s[i]2b=f[i]-s[i]^2

y,xy,x分别是与决策与有关的点和决定决策的点，显然有y=(s[j]+l)2+f[j]2y=(s[j]+l)^2+f[j]^2

x=s[j]+lx=s[j]+l

kk就是2∗s[i]2*s[i]

显然我们斜率优化就是优化掉不可能进答案的，目前我们是要找最小值，换句话说就是斜率要单调递增的才可以

由于我们枚举过程中xx是单调上升的，所以我们可以用一个单调对垒来维护我们的决策

数据结构

fhq treap​

基于两个操作 splitsplit 和 mergemerge

split​

1
2
3
4
5
6
7
void split(int t,int target,int &x,int &y)
{
	if(!t) return void (x=y=0);
	if(v[t]>target) y=t,split(ls(t),target,x,ls(t));  \\换句话说，y保留了剩下的部分，x和ls(t)在以后不断被拆分
	else x=t,split(rs(t),target,rs(t),y);
	pushup(t);
}

顾名思义就是就是按照权值分裂成[−∞,target],(target,∞][-\infty,target],(target,\infty]两颗子树（大概是像线段树那样划分 xx是左边 yy是右边）

注意有一些细节，target≥val[t]target \geq val[t]的时候就说明左边子树全全部被划到了 x 里面，所以只要递归地处理右子树

左子树同理，传参的时候同时维护一下左右子树

merge​

1
2
3
4
5
6
7
8
9
10
   int merge(int x,int y)
{
	if(!x||!y) return x+y;
	if(rnd[x]<rnd[y]) {rs(x)=merge(rs(x),y); pushup(x); return x;}
	else {ls(y)=merge(ls(y),x); pushup(y); return y;}
}
   
   把x和y合并，注意合并之后x跑到了左边y跑到了右边

原理：已知 xx 与 yy，由于任意 xx 满足 xi<yix_i<y_i ，要满足堆的性质，只需要确定 xx 与 yy 的父子关系即可

衍生操作

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 ins(int target)
{
       //插入操作，从target分离，然后把它放在taregt右边，然后在合并剩下的，注意每次合并要考虑会不会改变根
	split(rt,target,x,y);
	return rt=merge(merge(x,ctw(target)),y);
}

int del(int target)
{
       //因为每个节点都只存了一个数（没有cnt=2）的说法，删一个y的时候要看看是不是不止一个y，不过我们每个节点只存一个，所以就这样用咯
	split(rt,target,x,z);
	split(x,target-1,x,y);
	y=merge(ls(y),rs(y));
	return rt=merge(merge(x,y),z);
 } 

int kth(int t,int target)
{
       //这里貌似不和split和merge有关，就是BST的性质
	while(target)
	{
		if(target>sz[ls(t)]+1) target-=sz[ls(t)]+1,t=rs(t);
		else if(target==sz[ls(t)]+1) return v[t];
		else t=ls(t);
	}
}

int rk(int target)
{
       //x就是比target小的所有东西构成的树，size+1即为所求
	int ans=0;
	split(rt,target-1,x,y); 
	ans=sz[x]+1;
	rt=merge(x,y);
	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
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<iostream>
#include<cstdio>
#include<cstring>
#include<cstring>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#include<map>
#include<cstdlib>
#include<ctime>
#include<algorithm>

#define ls(x) c[(x)][0]
#define rs(x) c[(x)][1]

using namespace std;

const int maxn=100100;

int n,m,rnd[maxn];
int v[maxn],sz[maxn];
int rt,x,y,z;
int c[maxn][2];
int cnt;

struct fhqtreap{
	
	inline void pushup(int i) { sz[i]=sz[ls(i)]+sz[rs(i)]+1; }
	
	inline int ctw(int x)
	{
		sz[++cnt]=1;
		v[cnt]=x;
		rnd[cnt]=rand();
		return cnt;
	}
	
	void split(int t,int target,int &x,int &y)
	{
		if(!t) return void (x=y=0);
		if(v[t]>target) y=t,split(ls(t),target,x,ls(t));
		else x=t,split(rs(t),target,rs(t),y);
		pushup(t);
	}
	
    int merge(int x,int y)
	{
		if(!x||!y) return x+y;
		if(rnd[x]<rnd[y]) {rs(x)=merge(rs(x),y); pushup(x); return x;}
		else {ls(y)=merge(x,ls(y)); pushup(y); return y;}
	}

	int ins(int target)
	{
		split(rt,target,x,y);
		return rt=merge(merge(x,ctw(target)),y);
	}
	
	int del(int target)
	{
		split(rt,target,x,z);
		split(x,target-1,x,y);
		y=merge(ls(y),rs(y));
		return rt=merge(merge(x,y),z);
	 } 
	
	int kth(int t,int target)
	{
		while(target)
		{
			if(target>sz[ls(t)]+1) target-=sz[ls(t)]+1,t=rs(t);
			else if(target==sz[ls(t)]+1) return v[t];
			else t=ls(t);
		}
	}
	
	int rk(int target)
	{
		int ans=0;
		split(rt,target-1,x,y); 
		ans=sz[x]+1;
		rt=merge(x,y);
		return ans;
	} 
	/* 
	itn kth(int target)
	{
		return v[rk(target)];
	}
	*/
}fht;

int main()
{
	srand((unsigned)time(NULL));
	ios::sync_with_stdio(false);
	register int i,j;
	cin>>n;
	int opt,target;
	for(i=1;i<=n;i++)
	{
		cin>>opt>>target;
		if(opt==1)
		{
			fht.ins(target);
		}
		if(opt==2)
		{
			fht.del(target);
		}
		if(opt==3)
		{
			cout<<fht.rk(target)<<endl;
		}
		if(opt==4)
		{
			cout<<fht.kth(rt,target)<<endl;
		}
		if(opt==5)
		{
			fht.split(rt,target-1,x,y);
			cout<<fht.kth(x,sz[x])<<endl;
			rt=fht.merge(x,y);
		}
		if(opt==6)
		{
			fht.split(rt,target,x,y);
			cout<<fht.kth(y,1)<<endl;
			rt=fht.merge(x,y);
		}
	}
	return 0;
}

线段树合并

复杂度这东西我只能证明到O(nlog⁡2n)O(n\log^2n) 但是据说实际是 O(nlog⁡n)O(n\log n) 不过是复杂度能和o(nlog⁡2n)o(n\log^2 n) 有的一拼 而且空间也比较大。

目前看来一般保证复杂度的套路是先转化成差分问题 (需要注意有四个点，空间四倍) ，目前没看到过普通的线段树合并（似乎是因为比暴力还慢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

#define ls(i) t[i].l
#define rs(i) t[i].r

using namespace std;

const int maxn=100100;
const int mmxz=1e5;

int n,m,dep[maxn],head[maxn],sz[maxn],size,top[maxn],f[maxn],id[maxn],cnt,son[maxn],ans[maxn];
int rt[maxn],tot;

struct edge{
	int next,to;
}e[maxn*2];

struct seg_tree{
	
	struct tree{
		int l,r,mmx,pla;
	}t[maxn*4*17];
	
	inline void pushup(int i)
	{
		if(t[ls(i)].mmx>=t[rs(i)].mmx) t[i].pla=t[ls(i)].pla,t[i].mmx=t[ls(i)].mmx;
		else t[i].mmx=t[rs(i)].mmx,t[i].pla=t[rs(i)].pla;
	}
	
	void change_tree(int &i,int l,int r,int x,int target)
	{
		if(!i) i=++tot;
		if(l==r)
		{
			t[i].mmx+=target;
			t[i].pla=x;
			return ;
		}
		int mid=(l+r)>>1;
		if(x<=mid) 
		{
			//if(!t[i].l) t[i].l=++tot;
			change_tree(ls(i),l,mid,x,target);
		}
		else
		{
			//if(!t[i].r) t[i].r=++tot;
			change_tree(rs(i),mid+1,r,x,target);
		}
		pushup(i);
	}
	
	int merge_tree(int looker,int i,int l,int r)
	{
		if(looker==0||i==0) return looker+i;
		if(l==r)
		{
			t[looker].mmx+=t[i].mmx;
			t[looker].pla=l;
			return looker;
		}
		int mid=(l+r)>>1;
		ls(looker)=merge_tree(ls(looker),ls(i),l,mid);
		rs(looker)=merge_tree(rs(looker),rs(i),mid+1,r);
		pushup(looker);
		return looker;
	}
	
}st;


inline void addedge(int next,int to)
{
	e[++size].to=to;
	e[size].next=head[next];
	head[next]=size;
}

void dfs1(int t,int fat)
{
	dep[t]=dep[fat]+1;
	f[t]=fat;
	sz[t]=1;
	int i,j;
	for(i=head[t];i;i=e[i].next)
	{
		j=e[i].to;
		if(j==fat) continue;
		dfs1(j,t);
		sz[t]+=sz[j];
		if(sz[j]>sz[son[t]]) son[t]=j;
	}
}

void dfs2(int t,int topt)
{
	id[++cnt]=t;
	top[t]=topt;
	if(!son[t]) return ;
	dfs2(son[t],topt);
	int i,j;
	for(i=head[t];i;i=e[i].next)
	{
		j=e[i].to;
		if(j==son[t]||j==f[t]) continue;
		dfs2(j,j);
	}
}

inline int getlca(int x,int y)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		x=f[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	return x;
}

void getans(int t)
{
	int i,j;
	for(i=head[t];i;i=e[i].next)
	{
		j=e[i].to;
		if(j==f[t]) continue;
		getans(j);
		rt[t]=st.merge_tree(rt[t],rt[j],1,mmxz);
	}
	if(st.t[rt[t]].mmx) ans[t]=st.t[rt[t]].pla;
}

int main()
{
	ios::sync_with_stdio(false);
	register int i,j;
	cin>>n>>m;
	int t1,t2,x;
	for(i=1;i<n;i++) cin>>t1>>t2,addedge(t1,t2),addedge(t2,t1);
	dfs1(1,0);
	dfs2(1,1);
	for(i=1;i<=m;i++)
	{
		cin>>t1>>t2>>x;
		int lca=getlca(t1,t2);
		int llca=f[lca];
		st.change_tree(rt[t1],1,mmxz,x,1);
		st.change_tree(rt[t2],1,mmxz,x,1);
		st.change_tree(rt[lca],1,mmxz,x,-1);
		if(llca) st.change_tree(rt[llca],1,mmxz,x,-1);
	}
	getans(1);
	for(i=1;i<=n;i++) cout<<ans[i]<<endl;
	return 0;
}

莫队

把询问按照某个块长BB分组，左端点在[kB,(k+1)B][kB,(k+1)B]的在一组，这里面右端点按照从小到大排序

分析复杂度：

每次询问向右拓展大概是NN级别，同时每一个询问向左拓展的和最大为m×Bm \times B次，当B=NB=\sqrt{N}时，复杂度上限最低为MNM\sqrt{N}

其实这个东西挺显然的(

改进：部分莫队可以做奇偶性排序，大概能节约一半复杂度（实测20∼30%20\sim30\%左右）

带修莫队

顾名思义增加时间线操作，一般来说是单点修改（没见过区间的），这个时候询问左右端点都要分块，并且时间线从小到大（大概也能奇偶性排序），比如数颜色

特别要注意修改对答案造成的影响。

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

using namespace std;

int len,n,m;
int col[maxn];
int cnt,p[maxn*7],looker[maxn],qn,target[maxn];
int a[maxn];

struct que{
	int l,r,t,bl;
}q[maxn];

struct chg{
	int nx,pr,pla;
}c[maxn];

inline int getpla(int l,int r,int t)
{
	return (((l-1)/len+1)*(n/len+1)+(r-1)/len+1)&1;
}

int cmp(que a,que b)
{
	if(a.l/len!=b.l/len) return a.l<b.l;
	if(a.r/len!=b.r/len) return a.r<b.r;
	if(getpla(a.l,a.r,a.t)==1) return a.t<b.t;
	else return a.t>b.t; 
	//return a.t<b.t;
}

int ans=0;

inline void qread(int &x)
{
	x=0; static char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) x=x*10+c-'0',c=getchar();
	return ;
}

int main()
{
	//ios::sync_with_stdio(false);
	register int i;
	qread(n); qread(m);
	for(i=1;i<=n;i++) qread(a[i]),looker[i]=a[i];
	int l,r,t;
	char opt;
	for(i=1;i<=m;i++)
	{
		scanf("%c",&opt);
		if(opt=='R')
		{
			qread(l); qread(r);
			c[++cnt].nx=r;
			c[cnt].pr=a[l];
			a[l]=r;
			c[cnt].pla=l;
		}
		else 
		{
			qread(l); qread(r);
			q[++qn].l=l; q[qn].t=cnt; q[qn].r=r; q[qn].bl=qn;
		}
	}
	len=exp((log(n)+log(qn))/3);
	sort(q+1,q+qn+1,cmp);
	for(i=1;i<=n;i++) a[i]=looker[i];
	l=1,r=0,t=0;
	for(i=1;i<=qn;i++)
	{
		while(q[i].l<l) ans+=!p[a[--l]]++;
		while(q[i].r<r) ans-=!--p[a[r--]];
		while(q[i].r>r) ans+=!p[a[++r]]++;
		while(q[i].l>l) ans-=!--p[a[l++]];
		while(q[i].t>t)
		{
			int targetp=c[++t].pla;
			if(targetp>=l&&targetp<=r) ans-=!(--p[a[targetp]]);
			a[targetp]=c[t].nx;
			if(targetp>=l&&targetp<=r) ans+=!p[a[targetp]]++;
		}
		while(q[i].t<t)
		{
			int targetp=c[t].pla;
			if(targetp>=l&&targetp<=r) ans-=!(--p[a[targetp]]);
			a[targetp]=c[t].pr;
			if(targetp>=l&&targetp<=r) ans+=!p[a[targetp]]++;
			t--;
		}
		target[q[i].bl]=ans;
	}
	for(i=1;i<=qn;i++)
	{
		printf("%d\n",target[i]);
	}
}

回滚莫队

顾名思义就是不需要删除（删除变成了暴力地还原数组）

就在这里看吧

字符串

后缀数组

本质上是根据rk[sa[i]]=irk[sa[i]]=i和sa[rk[i]]=isa[rk[i]]=i 不断推导求得后缀排名，每次双关键字化成了一个关键字，等价于倍增

后缀自动机

不太理解，爬力

数学

FFT

比如求两个向量的卷积

具体操作：

F=f∗gF=f*g 先把f,gf,g转化成2n−12n-1个点值表示，然后通过O(N)O(N)地点值相乘并且O(nlogn)O(nlogn)快速傅里叶逆变换，然后即可得到FF

limitlimit必须是22的整数倍，不然可能点值相乘的时候两边不均匀分配导致一些点值乘不到一起(也会掉精度)

傅里叶逆变换还有一个1n\frac{1}{n}不要漏掉

这东西单独写了个博客

高斯消元

就是把一个方程组通过行列式的变换然后让只有对角线和最后一列有值，做法O(n3)O(n^3)

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
#include<iostream>
#include<cmath>
#include<stdio.h>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<iomanip> 
#include<algorithm>

using namespace std;

const int maxn=110;
const int eps=1e-7;


double a[maxn][maxn];
int n,m;


int main()
{
	//ios::sync_with_stdio(false);
	register int i,j,k;
	cin>>n; m=n+1;
	for(i=1;i<=n;i++) for(j=1;j<=m;j++) cin>>a[i][j];
	for(i=1;i<=n;i++)
	{
		int mmx=i;
		for(j=i+1;j<=n;j++) if(a[mmx][i]-a[j][i]<eps) mmx=j;
		if(fabs(a[mmx][i])<=eps) 
		{
			cout<<"No Solution"<<endl;
			return 0;
		}
		for(j=1;j<=m;j++) swap(a[mmx][j],a[i][j]);
		for(j=1;j<=n;j++) 
		{
			if(i==j) continue;
			double tmp=a[j][i]/a[i][i];
 			for(k=i+1;k<=m;k++)
			{
				a[j][k]-=a[i][k]*tmp;
			}
		}
	}
	for(i=1;i<=n;i++) printf("%.2lf\n",(a[i][m]/a[i][i]));
	return 0;
}

拉格朗日插值

很巧妙，既然n个点能确定一个多项式，那么我们就找到这nn个多项式，让每个g(xi)g(x_i)的值中只有gi(xi)g_i(x_i)有值，这样几个多项式加起来一定过这n个点，正确性显然。

怎么来构造这个多项式呢？只需要用这个式子就可以了

gi(x)=yiΠi≠jx−xjxi−xjg_i(x)=y_i \Pi_{i\neq j}\frac{x-x_j}{x_i-x_j}

这个式子满足在ii的时候只有g(i)≠0g(i)\neq 0

然后把这一些式子加起来，相当于求m点的点值表示，对每个gig_i都求一下值然后加起来即可

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

#define int long long 
using namespace std;

const int maxn=5050;
const int modp=998244353;

int h[maxn],y[maxn]; 
int n,m,ans;

inline int ksm(int x,int y)
{
	int ans=1;
	while(y)
	{
		if(y&1) ans=(ans*x)%modp;
		x=(x*x)%modp;
		y>>=1;
	}
	return ans;
}

int getg(int i)
{
	int ans=y[i];
	int s1=1,s2=1;
	for(int j=1;j<=n;j++)
	{
		if(j==i) continue;
		s1=s1*(m-h[j])%modp;
		s2=s2*(h[i]-h[j])%modp;
	}
	ans=ans*(s1*ksm(s2,modp-2)%modp)%modp;
	return ans;
}

signed  main()
{
	ios::sync_with_stdio(false);
	register int i,j;
	cin>>n>>m;
	for(i=1;i<=n;i++)
	{
		cin>>h[i]>>y[i];
	}
	for(i=1;i<=n;i++)
	{
		ans+=getg(i);
		ans%=modp;
	}
	ans=(ans+modp)%modp;
	cout<<ans<<endl;
	return 0;
}

线性代数

行列式的一些性质

行列式的值

二维 主对角线-副对角线

三维 三个从左到右的对角线-三个从右到左的对角线（循环移位）

更高维：D=∑(−1)tai,pjD=\sum{(-1)^ta_{i,p_{j}}}

定义：tt为逆序对数 pjp_j为一个排列

一些推论

1.如果行列式某两行值相等或者互成比例，行列式的值为零

2.排列中两个数对换，奇偶性改变

3.D(i,j)=a+bD(i,j)=a+b那么D=A+B,A(i,j)=a,B(i,j)=bD=A+B,A(i,j)=a,B(i,j)=b其余位置三个都一样

4.行列式的某一行和某一列对换，要变号（变换了ii行jj列，那么D′=(−1)i+jDD'=(-1)^{i+j}D）

5.行列式与转置行列式相同

6.行列式的某一行ii加上jj行的kk倍，行列式的值也不会变，符号表示D =ri+krjD′D\ \xlongequal{r_{i}+kr_{j}}D'

7.余子式和代数余子式

8.行列式等于任意一行(列)的各元素与对应的代数余子式相乘得到的和，特别的，如果不是与自己对应的行（列）相乘，得到的结果为0

9.行列式某一行（列）如果有个公因数k,D’k,D’看作是这一行提出kk的行列式，那么有D=kD′D=kD'

二次剩余

定义

$x^2 \equiv a\pmod p $

其中 aa 不是 pp 的倍数并且模同余于某个数的平方称 aa 为模 pp 的二次剩余，若非 pp 的倍数且模 pp 不同余与任何数的平方的数 bb 称为 模 pp 的非二次剩余

本质即为求一个数在模意义下的平方根

其中 aa 有 p−12\frac{p-1}{2} 个（对于奇素数），证明考虑(p−x)2≡x2(modp)(p-x)^2\equiv x^2\pmod p 即可，因此期望找到满足/不满足二次剩余次数是22

换句话说，对于 φ(p)=p−1\varphi(p)=p-1 个数，有 $ \frac{p-1}{2}$ 对数模意义下平方根相同，剩下的数没有平方根

勒让德符号

(np)={1，1,2−120(\frac{n}{p})=\begin{cases}1，&1,2\\-1&2\\0\end{cases}

pp 为 nn 的二次剩余 条件 11

p∤np\nmid n 记做条件 22

欧拉判别准则

(np)≡np−12(modp)\left( \frac{n}{p}\right) \equiv n^{\frac{p-1}{2}}\pmod p

证明：

np−1≡1(modp)(np−12+1)(np−12−1)≡0(modp)\begin{aligned} n^{p-1}&\equiv1\pmod p \\ (n^{\frac{p-1}{2}}+1)(n^{\frac{p-1}{2}}-1)&\equiv0\pmod p \end{aligned}

即其中一个必为 pp 的倍数，并且 最后的结果为 ±1\pm1

先考虑11

我们用原根表示 n=ajn=a^j

那么np−12≡ajp−12≡ap−1≡1(modp)n^{\frac{p-1}{2}} \equiv a^{j\frac{p-1}{2}}\equiv a^{p-1} \equiv1\pmod p

那么2∣j2\mid j 意即(aj2)2≡n(modp)\left(a^{\frac{j}{2}}\right)^2\equiv n\pmod p

然后考虑−1-1

显然就是同余变成了不同余

Cipolla算法

主要步骤:

1.随机选取一个数 aa 看是否 不满足二次剩余

2.建立一个复数域，用 Ax+BiAx+Bi 来表示一个数，其中 i2=a∗a−ni^2=a*a-n

3.解即为 (Ax+Bi)p+12(Ax+Bi)^{\frac{p+1}{2}}

正确性证明

引理:

1.(a+b)p≡ap+bp(modp)(a+b)^p\equiv a^p+b^p\pmod p

二项式定理展开即可

ip≡−i(modp)ip≡ip−1∗i≡(i2)p−12∗i≡(a2−n)p−12∗i≡−1∗i(modp)\begin{aligned} i^p &\equiv-i\pmod p \\ \\ \\ i^p&\equiv i^{p-1}*i \\ &\equiv (i^2)^{\frac{p-1}{2}}*i \\ &\equiv (a^2-n)^{\frac{p-1}{2}}*i \\ &\equiv -1*i \pmod p \end{aligned}

3.ap≡a(modp)a^p\equiv a\pmod p

即为费马小定理两边同时乘 aa

于是我们就可以得到这个式子：

x≡n12(modp)≡(a2−(a2−n))12≡(a2−i2)12≡((a−i)∗(a+i))12≡((ap+ip)∗(a+i))12≡((a+i)p+1)12≡(a+i)p+12(modp)\begin{aligned} x&\equiv n^{\frac{1}{2}}\pmod p \\ &\equiv (a^2-(a^2-n))^{\frac{1}{2}} \\ &\equiv(a^2-i^2)^{\frac{1}{2}} \\ &\equiv((a-i)*(a+i))^{\frac{1}{2}} \\ &\equiv((a^p+i^p)*(a+i))^{\frac{1}{2}} \\ &\equiv((a+i)^{p+1})^{\frac{1}{2}} \\ &\equiv(a+i)^{\frac{p+1}{2}} \pmod p \end{aligned}

（注意此时我们不能直接认为答案是 ap+12+ip+12(modp)a^{\frac{p+1}{2}}+i^{\frac{p+1}{2}}\pmod 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
#include<touwenjian.h>

using namespace std;

long long n,modp,looker;

struct comp{
	long long x,y;
	comp (long long xx=0,long long yy=0){ x=xx; y=yy; return ;}
};

comp operator *(comp a,comp b){return comp((a.x*b.x+a.y*b.y%modp*looker)%modp,(a.x*b.y+a.y*b.x)%modp);}

inline long long ksm(long long x,int y)
{
	long long ans=1;
	while(y)
	{
		if(y&1) ans=(ans*x)%modp;
		x=(x*x)%modp;
		y>>=1;
	}
	return ans;
}

inline long long kksm(comp x,int y)
{
	comp ans=comp(1,1);
	while(y)
	{
		if(y&1) ans=ans*x;
		x=x*x;
		y>>=1;
	}
	return ans.y; 
    //return ans.x;
    //这地方输出实部虚部都可以
}

inline void cipolla(long long n)
{
	long long a,i;
	n%=modp;
	if(n==0)
	{
		cout<<0<<endl; 
        //注意还要满足这东西不是p的倍数
		return ;
	}
	if(ksm(n,(modp-1)/2)==modp-1)
	{
		cout<<"Hola!"<<endl;
		return ;
	}
	while(1)
	{
		a=abs(rand()*rand())%modp;
		if(ksm((a*a-n+modp)%modp,(modp-1)/2)==modp-1) break;
	}
	long long ans1,ans2;
	looker=(a*a+modp-n)%modp;
	ans1=kksm(comp(a,1),(modp+1)/2); 
	ans2=modp-ans1;//如果你看懂了上面的东西的话，就知道解最多只有两个·
	if(ans1>ans2) swap(ans1,ans2);
	cout<<ans1;
	if(ans1!=ans2) cout<<" "<<ans2<<endl;
	else cout<<endl;
	return ;
}

int main()
{
	ios::sync_with_stdio(false);
	register int i,j;
	srand(time(NULL));
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n>>modp;
		cipolla(n); 
	}
	return 0;
}

图论

网络流

设 GG 是一个平面图，那么有对偶图 GG，原图的每个面替换成点，点替换成面，边对应为新的边，此时原图最大流=原图最小割=原图最短路

prufer编码

cayleycayley公式[n][n]含有nn−2n^{n-2}棵树

pruferprufer编码，f(T)=(a1,a2,...,an−2)f(T)=(a_1,a_2,...,a_{n-2}),aia_i表示编号最小的叶节点相邻节点（动态拆树）

显然这这东西对应回去的树一一对应，因此nn−2n^{n-2}恰好对应了cayleycayley公式（实际上这东西就是用来证明cayleycayley的）

这东西证明cayleycayley要证明一一对应的关系（双射）

考虑如何构造，发现当前位置的pruferprufer序列是最小的叶子节点，我们把叶子节点都先丢进一个堆，然后每次取堆首的时候顺便把他的父亲放进堆里面，时间复杂度O(nlogn)O(nlogn)事实证明本题的瓶颈还是在读入上面，所以把读入整好了也是能过的（

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

inline void getpprufer()
{
	int i;
	for(i=1;i<=n-1;i++) d[a[i]]++;
	priority_queue <int> q;
	for(i=1;i<=n-1;i++) if(!d[i]) q.push(-i);
	int cnt=0;
	while(!q.empty())
	{
		if(cnt==n-2) break;
		int t=q.top();
		t=-t;
		q.pop();
		prufer[++cnt]=a[t];
		d[a[t]]--;
		if(!d[a[t]]) q.push(-a[t]);		
	}
	int ans=0;
	for(i=1;i<=n-2;i++) ans^=(i*prufer[i]);
	cout<<ans<<endl;
}

考虑还原这棵树，不难发现不在pruferprufer序列上面的点一定是叶子节点（度为1），我们每次就找到最小的叶子节点，然后就可以根据pruferprufer序列来还原（得到父亲）

这样时间复杂度太高了，实际上我们每次找第一个的时候就只有两种情况，第一个更小和更大，更大的话很好做，直接用一个指针扫，变小就直接一个while循环到变大或者结束，时间复杂度是O(N)O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
inline void getfat()
{
    //a为prufer序列
	int lok=1; //lok相当于一个指针
	int i;
	for(i=1;i<=n-2;i++) d[a[i]]++; //这里的算度的时候不考虑自己与父亲的连边
	a[n-1]=n; //体面给了，n是根
	for(i=1;i<=n-2;i++)
	{
		while(d[lok]) lok++;
		f[lok]=a[i];
		vis[lok]=1;
		while(i<n&&!--d[a[i]]&&lok>=a[i])  //注意循环顺序
		{
			i++;
			f[a[i-1]]=a[i];
		}
		lok++;
	}
	int ans=0;
	for(i=1;i<=n-1;i++) ans^=(i*f[i]);
	cout<<ans<<endl;
}

然后接着想你就会发现，这东西不仅可以用来做pruferprufer还原ff，同理还可以用来构造pruferprufer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
inline void getprufer()
{
	int i;
	int lok=1;
	for(i=1;i<=n-1;i++) d[a[i]]++; //还是一样的，找到每个点的度
	for(i=1;i<=n-2;i++)
	{
		while(d[lok]) lok++; //依旧是扫一下
		prufer[i]=a[lok];//a[]记录的是父亲节点
		while(i<n-1&&!--d[prufer[i]]&&prufer[i]<lok) //这里的条件要变一下
		{
			i++;
			prufer[i]=a[prufer[i-1]];
		}
		lok++; 
	}
	int ans=0;
	for(i=1;i<=n-2;i++) ans^=(i*prufer[i]);
	cout<<ans<<endl;
}

群论

入门知识

（这貌似是离散数学的基础？）

设有集合 A,B,φA,B,\varphi 称为由 AA 到 BB 的一个映射，对于任意的一个 α∈A\alpha \in A 都存在唯一的 BB 中的元素 φ(α)\varphi(\alpha) 与之对应，此时称 φ(α)\varphi(\alpha) 为 α\alpha （在 φ\varphi 下） 的像，称 α\alpha 为 φ(α)\varphi(\alpha) 下的原像或反像

设A⊂SA\subset S 则{φ(α)∣a∈A}\{\varphi(\alpha)|a\in A\} 称为 AA 在 SS 的像 记做φ(S)\varphi(S)

设a∈A∣φ(a)∈T{a\in A|\varphi(a)\in T} 称 TT 为(在 φ\varphi 下) 的反像，记做φ−1(T)\varphi^{-1}(T)

与此同时我们给满射和单射下定义：在 BB 集合中任意一个元素在AA 内都有原像，称 φ\varphi 为满射 ，若 AA 的任意两个元素在 BB 在 φ\varphi 下的像不同，称为单射，既单又满的，称为双射，或者一一对应

集合到自身的映射称为置换，比如一张置换图，可以用矩阵快速幂快速求什么的…

集合 AA 到 BB 的直积（亦称作笛卡尔积） 指的是 AA 的元素 与BB 的 元素构成的有序数对的集合 {(a,b)∣(a∈A,b∈B)}\{(a,b)|(a\in A,b\in B)\} 记做 A×BA \times B

集合 AA 的二元运算， 即是A×AA\times A 到 AA 的映射

AA 上的一个二元关系 RR 定义为A×AA\times A 的一个子集，若(a1,a2)∈R(a_1,a_2)\in R 称 a1,a2a_1,a_2 有关系a1Ra2a_1Ra_2

如果 RR 有这些性质的话

反身性，即aRa(∀a∈A)aRa(\forall a\in A)

对称性，即a1Ra2a_1Ra_2 已经蕴含了 a2Ra1a_2Ra_1

传递性，即a1Ra2,a2Ra3a_1Ra_2,a_2Ra_3 蕴含了a1Ra3a_1Ra_3 a1,a2,a3∈Aa_1,a_2,a_3\in A

那么称 RR 为 AA上的一个等价关系，此时 AA 中互相等价的元素组成的子集称为等价类，根据定义我们显然能够知道任意两个不同的等价类的交集为空集，整个集合 AA 等于所有元素的无交并，等价关系通常用"~"来表示，AA 的所有等价类的集合称为 A/ A\text{/~}

如果RR的"对称性"变成了"反对称性"

反对称性，即a1Ra2,a2Ra1a_1Ra_2,a_2Ra_1已经蕴含了a1=a2a_1=a_2

那么称 RR 为 AA 上的偏序关系或者序关系，具有偏序关系的集合称为偏序集，如果一个偏序集中任意两个元素都有偏序关系，则称此偏序集为全序集，偏序关系通常用符号≤\leq 表示

显然上面的理解太抽象了，我们换一种理解方式，用哈斯图来描述这种偏序关系

哈斯图是用来表示有限偏序集的数字图标，对于偏序集合(S,≤)(S,\leq) 把 SS 的每个元素表示成平面上的顶点，并且绘制从xx 到 yy 的向上的线段到 yy 覆盖xx