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

相比前几篇游记,这一篇可能很短,因为我 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 ,欢迎提问!

0%