Reincarnation

正因为梦易碎，才格外美好。

ZROI - 20连测day5

发表于 更新于 分类于 ，
本文字数： 14k 阅读时长 ≈ 13 分钟

挂分最多的一集。

比赛链接：http://zhengruioi.com/contest/1471

A. 于是我栽种玫瑰

题目简介

给定一个有 个结点的无向图，其中对于 ，如果 ，那么有边 ，求出这个图的最大独立集。

数据范围：

你考虑 ，然后下一条边是 ，然后是 ……

所以实际上这个图是由很多个链组成的，所以我们考虑每个链独立做，其答案同样也是独立的。

然后我们考虑选择 ，那么 就不能被选，然后 又可以选，而 又不能选。

所以我们考虑容斥，每次算出 ，即 ，注意这里的 是转移之后的系数，也就是 。

这样做的时间复杂度是 ，然后你发现在 的时候就直接寄了，所以我们特判 ，此时链有 个，然后考虑这些链有些长度为 ，有些则要 。然后对于其我们分别求出其最大独立集求和即可。

AC Code
 
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
// ----- Eternally question-----
// Problem: A. 【noip赛前20天冲刺集训 day5】于是我栽种玫瑰
// Contest: ZROI - 23noip赛前20天冲刺 day5
// URL: http://zhengruioi.com/contest/1471/problem/2736
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-10-16 08:57:44
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
ll N,A,B;
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,A,B);
	if(A==1)
	{
		if(N/B%2==0) write(B*((N/B+1)/2)+(N-(N/B)*B));
		else write(B*((N/B+1)/2));
		return 0;
	}
	ll sumA=A,sumB=B,ans=N,delta=-1;
	while(true)
	{
		if(sumA+sumB>N) break;
		ans+=((N-sumB)/sumA)*delta;
		delta*=-1;
		sumA*=A,sumB=sumB*A+B;
	}
	write(ans);
	return 0;
}
/*

*/

B. 只因为后面的一切已早早被确定下来

题目简介

给定一个长度为 的序列 ，其中 ，对于确定的序列 ，存在一个值域在 的不可重集 ，此时对于二元组 的权值为：

那么这个确定序列 就是所有 的权值和。

现在请求出所有序列的权值和，对 取模。

数据范围：

考虑如果 确实给定，那么这个问题十分好做。这个集合很麻烦，所以我们考虑所有集合统一计算，直接得到序列的答案，然后你发现总权值就是 。

然后我们发现这个思路可以推广，记状态为 表示 时的答案，但是这个直接做是 的，其中 。

但实际上我们只关心 的值，但这样并不会减少状态数，但是你发现这三者成倍数关系，所以我们预处理状态，那么后三维的有效状态只有 。所以我们就可以直接 直接做，空间寄了 维滚动一下即可。

AC Code
 
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
// ----- Eternally question-----
// Problem: B. 【noip赛前20天冲刺集训 day5】只因为后面的一切已早早被确定下来
// Contest: ZROI - 23noip赛前20天冲刺 day5
// URL: http://zhengruioi.com/contest/1471/problem/2737
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-10-16 11:36:14
// ----- Endless solution-------

#pragma GCC optimize("O2")

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
using Pir=std::pair<int,int>;
using Node=std::pair<std::pair<int,int>,int>;
#define fir first
#define sec second
#define Mkr std::make_pair
const int MAXN=2e2+10,MAXM=1e2+10;
const int Mod=1e9+7;
template<class T1,class T2>
inline void add(T1 &x,T2 y){ x=x+y>=Mod?x+y-Mod:x+y; }
int N,M=100,L[MAXN],R[MAXN],Gcd[MAXM][MAXM];
int gcd(int a,int b){ return !b?a:gcd(b,a%b); }
std::vector<int>vec[MAXM];
int Dp[2][MAXM][MAXM][MAXM];
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N);
	for(int i=1;i<=N;++i) read(L[i],R[i]);
	for(int i=1;i<=M;++i) for(int j=1;j<=M;++j) Gcd[i][j]=gcd(i,j);
	for(int i=1;i<=M;++i) for(int j=i;j<=M;j+=i) vec[j].push_back(i);
	for(int i=L[1];i<=R[1];++i)
		for(int j=L[2];j<=R[2];++j)
			for(int k=L[3];k<=R[3];++k)
				++Dp[1][k][Gcd[j][k]][Gcd[Gcd[i][j]][k]];
	for(int i=4;i<=N;++i)
	{
		bool op=i&1;
		std::memset(Dp[op],0,sizeof(Dp[op]));
		for(int j=L[i-1];j<=R[i-1];++j)
			for(int k:vec[j]) for(int l:vec[k])
				for(int p=L[i];p<=R[i];++p)
					add(Dp[op][p][Gcd[p][j]][Gcd[p][k]],(ll)Dp[op^1][j][k][l]*(Gcd[p][l]+1)%Mod);
	}
	ll ans=0;
	for(int i=L[N];i<=R[N];++i)
		for(int x:vec[i]) for(int y:vec[x])
			add(ans,Dp[N&1][i][x][y]);
	write(ans);
	return 0;
}
/*

*/

C. Deliver Me

题目简介

给定一个有 的结点的图，其中 存在一条长度为 的边，以及一个初始为空的可重集 ，给定 次操作：

  • 将点对 加入 ；
  • 连接 ，长度为 ，然后求出 中所有点对的最短路的长度和。

注意操作二中连接边的操作独立，即答案求出后这个边就会被断掉。

数据范围：

我们首先设定 。

那么每次的答案就是：

但是这个是 的暴力。

然后考虑拆贡献，我们将 分为 三段，其中 。

然后在每一段中再分类讨论 的贡献：

  • 若 ：
    • 若 ，那么贡献为 ；
    • 若 ，那么贡献为 ；
    • 若 ，那么贡献为 ；
  • 若 ，这里设 ：
    • 若 ，那么贡献为 ；
    • 若 ，那么贡献为 ；
    • 若 ，那么贡献为 ；
  • 若 ，那么贡献为 。

然后你发现这个可以用 维护，时间复杂度 。

然后可以通过一些转化让这些公式可以用二维 维护，以做到 的复杂度，但是我不太会（实际上会了，和下面的代码实现类似，但是我不太想写），所以我们考虑一个更加暴力的做法。

我们直接用数组静态维护二维前缀和，然后暴力记录点对，如果当前点对超过 个，则直接 暴力重构静态二维前缀和。

那么最后可以做到 ，那么 时得到 的做法。

代码中保留了 的树状数组，可以直接通过一些细节修改变成 。

AC Code
 
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
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
// ----- Eternally question-----
// Problem: C. 【noip赛前20天冲刺集训 day5】Deliver Me
// Contest: ZROI - 23noip赛前20天冲刺 day5
// URL: http://zhengruioi.com/contest/1471/problem/2738
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-10-16 10:28:24
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
template<class T>
inline T abs(T x){ return x<0?-x:x; }
using Pir=std::pair<int,int>;
#define fir first
#define sec second
#define Mkr std::make_pair
const int MAXN=5e2+10;
int N,Q,Tot;
Pir Oper[MAXN];
int pre[MAXN][MAXN],pres[MAXN][MAXN],prec[MAXN][MAXN];
int val[MAXN][MAXN],vals[MAXN][MAXN],valc[MAXN][MAXN];
std::map<Pir,int>Hash;
struct BIT
{
	int Tre[MAXN],Cnt[MAXN],Siz;
	inline void build(int n){ Siz=n;for(int i=1;i<=n;++i) Tre[i]=Cnt[i]=0; }
	inline int lowbit(int x){ return x&(-x); }
	inline void add(int x,int v)
	{ for(;x<=Siz;x+=lowbit(x)) Tre[x]+=v,++Cnt[x]; }
	inline Pir query(int x)
	{
		int tr=0,cn=0;
		for(;x;x-=lowbit(x)) tr+=Tre[x],cn+=Cnt[x];
		return {tr,cn};
	}
	inline Pir get(int l,int r)
	{
		if(l>r) return {0,0};
		auto _l=query(l-1),_r=query(r);
		return {_r.fir-_l.fir,_r.sec-_l.sec};
	}
}Tre[MAXN];
inline void rebuild()
{
	for(int i=1;i<=Tot;++i)
	{
		auto p=Oper[i];
		val[p.fir][p.sec]+=p.sec;
		vals[p.fir][p.sec]+=p.fir;
		++valc[p.fir][p.sec];
		Tre[p.fir].add(p.sec,p.sec);
	}
	for(int i=1;i<=N;++i)
		for(int j=1;j<=N;++j)
		{
			pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+val[i][j];
			pres[i][j]=pres[i-1][j]+pres[i][j-1]-pres[i-1][j-1]+vals[i][j];
			prec[i][j]=prec[i-1][j]+prec[i][j-1]-prec[i-1][j-1]+valc[i][j];
		}
	Tot=0;
}
inline int getSum(int x,int y,int l,int r)
{
	if(x>y||l>r) return 0;
	return pre[y][r]-pre[x-1][r]-pre[y][l-1]+pre[x-1][l-1];
}
inline int getStum(int x,int y,int l,int r)
{
	if(x>y||l>r) return 0;
	return pres[y][r]-pres[x-1][r]-pres[y][l-1]+pres[x-1][l-1];
}
inline int getCnt(int x,int y,int l,int r)
{
	if(x>y||l>r) return 0;
	return prec[y][r]-prec[x-1][r]-prec[y][l-1]+prec[x-1][l-1];
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,Q);
	for(int i=1;i<=N;++i) Tre[i].build(N);
	for(int opt,x,y;Q--;)
	{
		read(opt,x,y);
		if(x>y) std::swap(x,y);
		if(opt==1)
		{
			if(x==y) continue;
			// Tre[x].add(y,y);
			Oper[++Tot]=Mkr(x,y);
			if(Tot>N) rebuild();
		}
		else
		{
			ll ans=0;
			int mid=(x+y)>>1;
			ans+=getSum(1,x,1,N)-2*getSum(1,x,mid+1,y)-getStum(1,x,1,N);
			ans+=getCnt(1,x,mid+1,y)*(x+y);
			ans+=getCnt(1,x,y+1,N)*(x-y);
			// for(int st=1;st<=x;++st)
			// {
				// auto tmp=Tre[st].get(st,mid);ans+=tmp.fir-st*tmp.sec;
				// tmp=Tre[st].get(mid+1,y);ans+=(x+y-st)*tmp.sec-tmp.fir;
				// tmp=Tre[st].get(y+1,N);ans+=tmp.fir+(x-y-st)*tmp.sec;
				// ans+=Tre[st].get(st,mid)-st*Cnt[st].get(st,mid);
				//b in [1,mid]
				// ans+=Abs[st].get(mid+1,y)+(x+y-st)*Cnt[st].get(mid+1,y);
				//b in (mid,y]
				// ans+=Tre[st].get(y+1,N)+(x-y-st)*Cnt[st].get(y+1,N);
				//b in (y,n]
			// }
			// write(ans,' ');
			//a in [1,x]
			for(int st=x+1;st<=mid;++st)
			{
				int newmid=st+mid-x;
				ans+=getSum(st,st,st,N)-2*getSum(st,st,newmid+1,y);
				ans+=2*getStum(st,st,newmid+1,N)-getStum(st,st,st,N);
				ans+=(y-x)*getCnt(st,st,newmid+1,y)-(x+y)*getCnt(st,st,y+1,N);
				// auto tmp=Tre[st].get(st,newmid);ans+=tmp.fir-st*tmp.sec;
				// tmp=Tre[st].get(newmid+1,y);ans+=(y+st-x)*tmp.sec-tmp.fir;
				// tmp=Tre[st].get(y+1,N);ans+=tmp.fir+(st-x-y)*tmp.sec;
				// ans+=Tre[st].get(st,newmid)-st*Cnt[st].get(st,newmid);
				//b in [a,newmid]
				// ans+=Abs[st].get(newmid+1,y)+(y+st-x)*Cnt[st].get(newmid+1,y);
				//b in (newmid,y]
				// ans+=Tre[st].get(y+1,N)+(st-x-y)*Cnt[st].get(y+1,N);
				//b in (y,n]
			}
			// write(ans,' ');
			//a in (x,mid]
			ans+=getSum(mid+1,N,1,N)-getStum(mid+1,N,1,N);
			// for(int st=mid+1;st<=N;++st)
			// {
				// auto tmp=Tre[st].get(st,N);
				// ans+=tmp.fir-st*tmp.sec;
				// ans+=Tre[st].get(st,N)-st*Cnt[st].get(st,N);
			// }
			for(int i=1;i<=Tot;++i)
			{
				auto p=Oper[i];
				ans+=std::min(p.sec-p.fir,abs(p.sec-y)+abs(p.fir-x));
			}
			write(ans,'\n');
		}
	}
	return 0;
}
/*

*/

D. 分道扬镳

题目简介

有 种颜色，以及 个格子，进行若干次以下操作：

  • 将第 个格子染成颜色 ，其中 ；
  • 将第 个格子染成当前格子 的颜色，其中 ；
  • 将第 个格子染成当前格子 的颜色，其中 。

求出最终所有格子都有颜色的方案数。给定 ，你需要求出 的所有答案。

数据范围：

然后你发现这个 很麻烦，设最后格子 的颜色为 ，那么我们连有向边 ，最后可以得到一个基环树森林，那么状态合法的充分必要条件为所有连通块不全为环，或存在自环。

然后考虑 的状态，如果最后 的颜色是当前还没有的一个颜色，那么一定需要连接一条自环（自染色后染到 去），所以我们讨论一下：

  • 若存在自环，那么 的颜色任取，或当前图是一条链或若干个环，此时链头颜色不可取。
  • 若不存在自环，那么 的方案数为 减去叶子数量。

首先考虑有自环，那么基环树森林不合法的情况数为所有连通块都是非自环的纯环，是错排数，即 。

所以最后有自环的答案为 。

然后考虑统计叶结点，枚举叶结点并删除，那么剩下的图一定是没有自环的任意基环树森林，方案数为 。

所以最后答案为 ，前者线性维护，后者快速幂可以做到 。

考虑优化快速幂，按照线性筛的流程：

  • 质数快速幂暴力维护，时间复杂度 。
  • 对于合数 ，其中 为质数， 为任意数，计算 ，前者光速幂 预处理， 查询，后者递归处理，这种情况显然在之前已被处理。

其中 为 ，是 ，暴力预处理时间复杂度 。

线性解决。

相关文章