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

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


Part1. 游记

果不其然还是做模拟赛……习惯就好……

莫名感觉今天是数学专场,进门就一道期望题,还好知道套路,最后忘了写线性求逆元,被卡了;

有一些奇怪的数学结论忘了,像中国剩余定理之类的?估计回去要恶补数论了……(为什么我记得之前也说过要补数论,还学了一下中国剩余定理和扩展中国剩余定理?)

最后有一道 DAG 最长反链 等于 二分图最大匹配 的题,反正我是没有见过这个套路,还被一个 dalao 喷了“这不是基本常识吗?”

得出结论“My vegetable has explosed…”

Tab. 这篇博客也是 Day7 补的,之前的一篇因为计算机 D盘蜜汁清空了……

又及,用Typora写博客的时候换了一个主题,莫名快乐


Part2. Solution

T1. 锻造(forging)

- Experience

你看这是一道期望题,显然我们要 Dp……

于是非常轻松(或许吧)地推导出了转移方程,最后不知道直接求逆元会被卡,就没有预处理逆元,结果就出锅了……

- Solution

可以得到一个显然的 Dp 状态:f[i] 表示锻造出 i 级剑的期望花费。

我们考虑从 f[i-1],f[i-2] 推导出 f[i],设 i 级剑锻造成功的概率为 p[i]

我们需要一把 i-1 级剑和一把 i-2 级剑锻造出 i 级剑,即 f[i]=f[i-1]+f[i-2]

但是假如失败了呢,有 (1-p[i]) 的概率?我们会得到一把 i-2 级剑,要再锻造 i 级剑,我们需要锻造一把 i-1 级剑,即 f[i]=f[i-1]+f[i-2]+(1-p[i])f[i-1]

假如又失败了?我们仍然需要一把 i-1 级剑,即 f[i]=f[i-1]+f[i-2]+(1-p)(f[i-1]+(1-p)f[i-1])……

假如一直失败,则有 f[i]=f[i-1]+f[i-2]+(1-p)(f[i-1]+(1-p)(f[i-1]....))

定义 g[i]=f[i-1]+(1-p)g[i] ,解一下方程,可得 g[i]=f[i-1]/p ;由于 f[i]=g[i]+f[i-2],则 f[i]=f[i-1]/p+f[i-2]

于是我们就得到了一个状态转移方程式。

显然这里的除以 $p$ 我们需要逆元,不过这道题直接算逆元是会 TLE 的……于是我们需要预处理逆元,线性筛即可。(因为 inv(x) 是积性函数)

Q:这里的 $p$ 可能很大啊,怎么储存它的逆元呢?

A: 根据题意我们可以知道,$p=\frac {\min(c_{i-1},b_{i-2})}{c_{i-1}}$ ,把这个式子代回转移方程式:

所以我们并不是真正预处理 $p$ 的逆元,而是预处理 $\min(c_{i-1},b_{i-2})$ 的逆元,实际规模只有 $10^7$,所以是可以储存的。

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

typedef long long ll;
const ll MOD=998244353;
const int LIMIT=int(1e7);

int inv[LIMIT+3],prn[LIMIT/2+3];
bool vis[LIMIT+3];
int n,m,Tbx,Tby,Tcx,Tcy,Tp,nprn;
int QPow(int A,int B){
int ret=1;
while(B){
if(B&1) ret=int(1ll*ret*A%MOD);
A=(int)(1ll*A*A%MOD);
B>>=1;
}
return ret;
}
void Process(){
inv[1]=1;
for(int i=2;i<=LIMIT;i++){
if(!vis[i]){
prn[++nprn]=i;
inv[i]=QPow(i,MOD-2);
}
for(int j=1;j<=nprn && 1ll*i*prn[j]<=LIMIT;j++){
vis[i*prn[j]]=true;
inv[i*prn[j]]=(int)(1ll*inv[i]*inv[prn[j]]%MOD);
if(i%prn[j]==0) break;
}
}
}
int f[10],b[10],c[10];
int main(){
freopen("forging.in","r",stdin);
freopen("forging.out","w",stdout);
Process();
scanf("%d%d%d%d%d%d%d",&n,&m,&Tbx,&Tby,&Tcx,&Tcy,&Tp);
f[0]=m;
b[0]=Tby+1;c[0]=Tcy+1;
for(int i=1;i<=n;i++){
int I=i%3,J=(i-1)%3,K=(i-2)%3;
b[I]=int((1ll*b[J]*Tbx+Tby)%Tp+1);
c[I]=int((1ll*c[J]*Tcx+Tcy)%Tp+1);
if(i==1)
f[1]=int(f[0]+1ll*f[0]*c[0]%MOD*inv[min(c[0],b[0])]%MOD)%MOD;
else
f[I]=int(f[K]+1ll*f[J]*c[J]%MOD*inv[min(c[J],b[K])]%MOD)%MOD;
}
printf("%d\n",f[n%3]);
return 0;
}

T2. 整除(division)

- Experience

说起来也只怪自己的数学太菜了……

推出来了前大半的结论,得到了一个非常优秀的 $O(ct)\approx10^6$ 的预处理;结果不知道最后怎么统计答案(其实把那个结论推出来,就可以得到最后的答案就是把我预处理出来的所有答案乘起来),只能把算法复杂度退化到 $O(cn)$ ,相当于一个暴力……

ei……

- Solution

= P1. 第一个结论

显然,对于一个质数 $p$ :

若 $x\equiv r\pmod p$;
则有 $(x+p)\equiv r\pmod p$;

再推广一下,若 $x^m\equiv r\pmod p$;
则有 $(x+p)^m\equiv r\pmod p$;

= P2. 第二个结论

大概是不需要证明的……

= P3. 求解

知道上面两个结论我们能干什么呢?

先分析题目,发现题目其实是要让我们求解同余方程:

由于 $p_1,p_2,…,p_c$ 互不相同,所以可以改为:

即同余方程组的求解,可以用中国剩余定理

但是还可以简化一下:

对于第一个结论,概括一下就是方程 $x^m\equiv r\pmod p$ 的解以 $p$ 为循环节(即如果 $x$ 是解,则 $(x+p)$ 也是解)。所以我们只要枚举 $x\in[1,p]$ ,判断是否是同余方程的解即可。

因为 $p_1,p_2,…p_c$ 都是互不相同的质数,所以它们两两互质。故设 $x^m\equiv x\pmod p_i$ 在 $[1,p_i]$ 内的解的个数为 $h_i$,则根据第二个结论,可以知道最后的答案即 $h_1h_2…h_c$ 。

处理出 $h_i$ 只需要枚举 $1$ 到 $p_i$ ,暴力判断是否是同余方程的解即可。但是注意要预处理 $x^m\bmod p$ 。

- 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
/*Lucky_Glass*/
#pragma GCC optimize(2)
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MOD=998244353,T=1e4;
int tex,cas,n,m,nprn;
int p[55],cnt[55],prn[T+5],inv[T+5];
bool vis[T+5];
int QPow(int A,int B,int C){
int ret=1;
while(B){
if(B&1) ret=ret*A%C;
A=A*A%C;
B>>=1;
}
return ret;
}
void Process(){
for(int i=2;i<=T;i==2? 3:i+2){
if(!vis[i]) prn[++nprn]=i;
for(int j=1;j<=nprn && 1ll*i*prn[j]<=T;j++){
vis[i*prn[j]]=true;
if(i%prn[j]==0) break;
}
}
}
int QRead(){
int ret=0;char ch=getchar();
while(ch<'0' || '9'<ch) ch=getchar();
while('0'<=ch && ch<='9') ret=(ret<<1)+(ret<<3)+ch-'0',ch=getchar();
return ret;
}
int main(){
freopen("division.in","r",stdin);
freopen("division.out","w",stdout);
Process();
tex=QRead();cas=QRead();
while(cas--){
n=QRead();m=QRead();
int ans=0;
for(int i=1;i<=n;i++){
p[i]=QRead();
for(int j=1;j<=nprn && prn[j]<p[i];j++){
inv[prn[j]]=QPow(prn[j],m,p[i]);
}
inv[1]=1;cnt[i]=2;
for(int j=2;j<p[i];j==2? 3:j+2){
if(!vis[j]){
if(inv[j]==j)
cnt[i]++;
}
for(int k=1;prn[k]<=j && k<=nprn && 1ll*j*prn[k]<p[i];k++){
inv[j*prn[k]]=inv[j]*inv[prn[k]]%p[i];
if(inv[j*prn[k]]==j*prn[k]) cnt[i]++;
if(j%prn[k]==0) break;
}
}
}
ans=cnt[1];
for(int i=2;i<=n;i++)
ans=int(1ll*ans*cnt[i]%MOD);
printf("%d\n",ans);
}
return 0;
}

T3. 欠钱(money)

- Experience

emm……这道题考试的时候看漏了一句话:“每只企鹅只会借一次钱”,错以为这道题是动态维护网络流……

最后回宿舍跟室友们交流才发现,这原来是一棵树 QwQ ,所以就从网络流简化为求链上最小值了~

听神犇讲题、看题解,然后发现,这是一道 LCT 的板子题。(板子又怎样,LCT 我没学啊)

然后 Day4 这天就没改出来这道题,Day5 因为听到讲课要讲 LCT,心血来潮就把 LCT 自学了一下,打了一道版题。于是来看这道题,但还是没有写出来(可能我对 LCT 理解不够深刻)。

最后看了题解,发现另一种解法,才终于 AC 了这道题。

(你们猜我是什么时候改的这道题?)

- Solution

=P1. 一些初始思路

动态倍增!!!

其实这是我考试的时候的想法……但是我不知道怎么更新倍增数组,然后就爆零了 TAT

思路很简单:

  • 修改(0操作)就看作连一条从儿子a到父亲b(这里不能换方向)的边;不难发现,只有当 b 是 a 的祖先时,a 获得钱,b 才会获得钱,且数量为 a 到 b 的链上的最小值;
  • 询问(1操作)首先判断 b 是否是 a 的祖先,再倍增求 a 到 b 的链上的最小值即可。
=P2. 倍增

根据这个思路,我们可以定义出倍增数组 pre[u][i] 表示 $u$ 的第 $2^i$ 个祖先,mn[u][i] 表示 $u$ 到 pre[u][i] 的链上的最小边权。

当我们连一条从 儿子u 到 父亲v 的边权为 c 的边时,我们需要更新:

1
pre[u][0]=v;mn[u][0]=c;

这个时候我们不更新其他的倍增数组,因为可能有很多更新的信息用不到,就浪费了时间。当我们要用到 pre[u][i]mn[u][i] 时,我们用函数 Update(u,i) 更新:

1
2
3
4
5
6
7
void Update(int u,int x){
for(int i=1;i<=x;i++){
Update(pre[u][i-1],i-1); //因为之后会用到 pre[u][i-1] 和 mn[u][i-1]
pre[u][i]=pre[pre[u][i-1]][i-1];
mn[u][i]=min(mn[u][i-1],mn[pre[u][i-1]][i-1]);
}
}

但是我们发现,这样还是太浪费了,因为倍增数组只可能扩展出新的值,而不会修改原来的值(即如果我们计算过 pre[u][i]mn[u][i],这两个值在之后就不会被修改了)。

我们对于每个 u ,储存 upd[u] 表示我们已经计算过 pre[u][0~upd[u]]mn[u][0~upd[u]] ;于是 Update(u,i) 变为了:

1
2
3
4
5
6
7
8
void Update(int u,int x){
for(int i=upd[u]+1;i<=x;i++){
Update(pre[u][i-1],i-1); //因为之后会用到 pre[u][i-1] 和 mn[u][i-1]
pre[u][i]=pre[pre[u][i-1]][i-1];
mn[u][i]=min(mn[u][i-1],mn[pre[u][i-1]][i-1]);
}
upd[u]=x;
}

现在我们解决了动态倍增及其更新的问题了。

=P3. 并查集

但是还有一个问题——维护每个节点的深度(以便求 LCA 并进一步判断出 b 是否是 a 的祖先),于是我们想到可以用并查集!还可以顺带维护每个节点所在树的根节点。

但是需要注意并查集合并时是有顺序的,比如我们连了一条从 儿子u 到 父亲v 的边,就只能在并查集中把 u 合并到 v,道理非常显然(毕竟这是一棵有根树)。

维护深度……只能具体看代码了……(咕)

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

const int N=1e5;

int n,m,ans;
int pre[N+3][20],mn[N+3][20],upd[N+3];
int mfa[N+3],mdep[N+3];

int MFa(int x){
if(mfa[x]==x) return x;
int res=MFa(mfa[x]);
mdep[x]+=mdep[mfa[x]];
return mfa[x]=res;
}
void Update(int u,int x){
for(int i=upd[u]+1;i<=x;i++){
Update(pre[u][i-1],i-1);
pre[u][i]=pre[pre[u][i-1]][i-1];
mn[u][i]=min(mn[u][i-1],mn[pre[u][i-1]][i-1]);
}
upd[u]=x;
}
int LCAMin(int u,int v){
int del=mdep[u]-mdep[v],res=(1<<29);
for(int i=19;i>=0;i--)
if(del&(1<<i))
del^=(1<<i),
Update(u,i),
res=min(res,mn[u][i]),
u=pre[u][i];
if(u==v) return res;
return 0;
}
int main(){
freopen("money.in","r",stdin);
freopen("money.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) mfa[i]=i;
for(int h=1;h<=m;h++){
int tmp,u,v;
scanf("%d%d%d",&tmp,&u,&v);
u=(u+ans)%n+1;v=(v+ans)%n+1;
if(tmp){
if(MFa(u)!=MFa(v) || mdep[u]<=mdep[v]) ans=0;
else ans=LCAMin(u,v);
printf("%d\n",ans);
}
else{
int val;scanf("%d",&val);
val=(val+ans)%n+1;
pre[u][0]=v;mn[u][0]=val;
mfa[u]=v;mdep[u]=1;
}
}
return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com ,欢迎提问!

0%