游记&OI - 广州纪中游记 Day7 | Lucky_Glass's Blog

以心为名，名为爱惜

0%

游记&OI - 广州纪中游记 Day7

发表于 更新于 分类于 Valine：

相比前几篇游记，这一篇可能很短，因为我 T3 还没有做出来……

但是 T3……不如放飞象征和平的？鸽子？？

<题面链接> 提取码：7puf

Part1. 游记

（糟了，我忘了 Day7 发生了啥怎么办！！）

Tab. 此篇游记补于 Day11 晚……所以我是真的忘了

所以……咕

Part2. Solution

T1. 小L的数列(seq)

[Experience]

突然觉得一句话很有道理：“特别害怕那种特别简短的题面”

题意非常清晰，数据规模也让我一眼看出矩阵快速幂……But……我还是没有想到把指数拿来快速幂……

[Solution]

定义函数 $g(i,j)$ ，表示：

en……应该能够理解吧……

于是我们最后的答案就是求：

也就是要求出 $g(n,1…k)$ 。这个可以用矩阵快速幂！

可以知道对于 $i\in[1,k]$ ，有：

于是我们可以初始化出一个 $k\times 1$ 的初始矩阵。

考虑转移：由于 $(x^a)^b=x^{ab}$，$x^a\cdot x^b=ab$ ， 所以：

然后就可以构造矩阵了！

一些细节就看 reader 们能否自己想到了，实在碰到问题可以参考一下代码。

[Source]

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
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;
const int M=200;
const ll MOD=998244353;

struct MATRIX{
	ll mat[M+3][M+3];
	int rol,col;
	void Make(int Rol,int Col,int val){
		rol=Rol;col=Col;
		for(int i=1;i<=Rol;i++)
			for(int j=1;j<=Col;j++)
				if(val && i==j) mat[i][j]=1;
				else mat[i][j]=0;
	}
	MATRIX operator *(MATRIX curb){
		MATRIX ret;ret.Make(rol,curb.col,0);
		for(int i=1;i<=ret.rol;i++)
			for(int j=1;j<=ret.col;j++)
				for(int k=1;k<=col;k++)
					ret.mat[i][j]=(ret.mat[i][j]+mat[i][k]*curb.mat[k][j])%(MOD-1);
		return ret;
	}
	MATRIX QPow(int curb){
		MATRIX ret,cura=*this;
		ret.Make(rol,col,1);
		while(curb){
			if(curb&1) ret=ret*cura;
			cura=cura*cura;
			curb>>=1;
		}
		return ret;
	}
	void Print(){
		for(int i=1;i<=rol;i++){
			for(int j=1;j<=col;j++){
				printf("%lld",mat[i][j]);
				if(j==col) printf("\n");
				else printf(" ");
			}
		}
	}
}Mfir,Mmid,Mres;

int n,m;
int f[M+3],b[M+3];

ll QPow(ll cura,ll curb){
	ll ret=1;
	while(curb){
		if(curb&1) ret=ret*cura%MOD;
		cura=cura*cura%MOD;
		curb>>=1;
	}
	return ret;
}

int main(){
	freopen("seq.in","r",stdin);
	freopen("seq.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) scanf("%d",&b[i]);
	for(int i=1;i<=m;i++) scanf("%d",&f[i]);
	if(n<=m){
		printf("%d\n",f[n]);
		return 0;
	}
	Mmid.Make(m,m,0);
	for(int i=1;i<=m;i++)
		Mmid.mat[1][i]=b[i];
	for(int i=2;i<=m;i++)
		Mmid.mat[i][i-1]=1;
	ll ans=1;
	Mmid=Mmid.QPow(n-m); //转移矩阵的快速幂放外面！
	for(int i=1;i<=m;i++){
		Mfir.Make(m,1,0);
		Mfir.mat[m-i+1][1]=1;
		Mres=Mmid*Mfir;
//		printf("[%d]\n",i);
//		Mres.Print();
		ans=ans*QPow(f[i],Mres.mat[1][1])%MOD;
	}
	printf("%lld\n",ans);
	return 0;
}

T2. 梦境

[Experience]

非常显然的贪心，不知道为什么会有同学做成二分图匹配……虽然确实很像……

不想吐槽自己，考试完过后换了两行代码的顺序就 AC 了 QwQ（不换爆零）。

[Solution]

把所有点从左到右排序、区间按左端点从左到右排序。

从左到右枚举一个点，希望找到一个和它匹配的区间，于是用优先队列维护：左端点在该点左边（或就是该点）且没有匹配过的区间，为什么要用优先队列？我们要优先匹配右端点靠左的区间！

[Proof]

首先，证明如果当前点能够匹配，就一定先给它匹配：

考虑将点 i 匹配到区间 [l,r]；如果不匹配 i ，而将 [l,r] 与另一个在 i 右边的 j 匹配，这样显然不优。

  1. 如果 j 只有区间 [l,r] 能和它匹配，则不管将 [l,r] 匹配到 i 还是 j ，都只能产生 1 的贡献。
  2. 如果 j 还有另一个区间 [l1,r1] 和它匹配，则把 [l,r] 匹配给 i，[l1,r1] 匹配给 j ，这样产生最大的贡献 2。

这样至少能够证明，优先给 i 匹配不会比优先给 j 匹配差。

再证明优先给右端点靠左的区间匹配：

如果 [l1,r1],[l2,r2] 和点 i,j 满足 i<=r1<j<=r2，显然先把 [l1,r1] 匹配 i 更优。

仍然可以证明其他情况下，先匹配 [l1,r1] 不会更差。

[Source]

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
/*Lucky_Glass*/
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=2e5;
int QRead(){
	int ret=0;char c=getchar();
	while(c<'0' || '9'<c)
		c=getchar();
	while('0'<=c && c<='9')
		ret=(ret<<3)+(ret<<1)+c-'0',
		c=getchar();
	return ret;
}
struct GDREAM{int lef,rig;}drm[N+3];
bool cmp(const GDREAM cp1,const GDREAM cp2){return cp1.lef<cp2.lef;}
bool operator <(const GDREAM cp1,const GDREAM cp2){return cp1.rig>cp2.rig;}

int n,m;
int tim[N+3];
priority_queue< GDREAM > que;
int main(){
	freopen("dream.in","r",stdin);
	freopen("dream.out","w",stdout);
	n=QRead();m=QRead();
	for(int i=1;i<=n;i++)
		drm[i].lef=QRead(),
		drm[i].rig=QRead();
	for(int i=1;i<=m;i++)
		tim[i]=QRead();
	sort(tim+1,tim+1+m);
	sort(drm+1,drm+1+n,cmp);
	int pos=1,ans=0;
	for(int i=1;i<=m;i++){
		while(pos<=n && drm[pos].lef<=tim[i]) que.push(drm[pos++]);
		while(!que.empty() && que.top().rig<tim[i]) que.pop();
		if(!que.empty()){
			que.pop();
			ans++;
		}
	}
	printf("%d\n",ans);
	return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com ，欢迎提问！