专栏文章

题解：P9590 「PFLOI R1」PFL 团主的 PFL 操作

wwallace_QwQ
P9590题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio7uvli
此快照首次捕获于
2025/12/02 14:47
3 个月前
此快照最后确认于
2025/12/02 14:47
3 个月前
查看原文
首先，每个成员的操作是互不影响的，所以序列的顺序都是不重要的，所以我们只在乎每个成员要进行多少次操作，设 cic_i 表示成员的操作次数。
Subtask1,2,3 可以直接枚举得到 cic_i，考虑如何处理 Subtask4。
观察式子：ai=(ai−1×p+p) mod q+1a_i=(a_{i-1}\times p+p)\bmod q+ 1 (i≥1) (i \geq 1)
由于 aia_i 只与 ai−1a_{i-1} 有关，只要 aia_i 在 a1∼i−1a_{1\sim i-1} 出现过，那么后面的数一定与前面的某一段是相同的，所以这是一个循环节。
又由于对 qq 进行取模，所以根据鹊巢原理，其循环节长度一定不超过 qq，那么完全可以暴力枚举直到找到循环节。
然后就可以求出 cic_i。
现在考虑如何求出答案，根据期望的可加性，答案等于每一位成员最终是管理员的期望值之和。
显然每个成员成为管理员的期望只与操作次数有关，而与本身无关。
那么设 fi,0/1/2f_{i,0/1/2} 表示第 ii 次操作时，不在团队内/在团队内且是成员/在团队内且是管理员的期望。
那么有转移：
  • fi,0=34fi−1,0+14fi−1,1f_{i,0}=\frac{3}{4}f_{i-1,0}+\frac{1}{4}f_{i-1,1}
  • fi,1=14fi−1,0+24fi−1,1+14fi−1,2f_{i,1}=\frac{1}{4}f_{i-1,0}+\frac{2}{4}f_{i-1,1}+\frac{1}{4}f_{i-1,2}
  • fi,2=14fi−1,1+34fi−1,2f_{i,2}=\frac{1}{4}f_{i-1,1}+\frac{3}{4}f_{i-1,2}
初始：f0,0=1f_{0,0}=1
ans=∑i=1nfci,2ans=\sum_{i=1}^nf_{c_i,2}
又注意到 n≤1018n\le10^{18}。
自然可以想到矩阵快速幂优化dp。
[fi−1,0fi−1,1fi−1,2]×[3414014121401434]=[fi,0fi,1fi,2]\begin{gathered} \begin{bmatrix} f_{i-1,0} \\ f_{i-1,1} \\ f_{i-1,2} \end{bmatrix} \times \begin{bmatrix} \frac{3}{4} & \frac{1}{4} & 0\\ \frac{1}{4} & \frac{1}{2} & \frac{1}{4}\\ 0 & \frac{1}{4} & \frac{3}{4} \end{bmatrix} = \begin{bmatrix} f_{i,0} \\ f_{i,1} \\ f_{i,2} \end{bmatrix} \end{gathered}
初始：
[100]\begin{gathered} \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} \end{gathered}
代码（细节还是很多的，记得开long long）：
CPP
struct matrix{
	int t[3][3];
	matrix(){memset(t,0,sizeof t);}
}f0,trans;
matrix operator*(const matrix &x, const matrix &y) {
    matrix res;
    for1(i,0,2) for1(j,0,2) for1(k,0,2)
    	madd(res.t[i][j],1ll*x.t[i][k]*y.t[k][j]);
    return res;
}
matrix qpow(matrix x,LL y,LL Mod=mod) {
	if(y==0) return f0;
	matrix res=x; y--; /*y%=(mod-1);*/
	for(;y;y>>=1,x=x*x)
		if(y&1) res=res*x;
	return res;
}
 
LL n,a0,p,q,ed;
int opt,ans;
int a[N],b[N],c[N];
map<int,int> ma;
void solve(){
	int init[3][3]={{249561089,748683265,0},
					{748683265,499122177,748683265},
					{0,748683265,249561089}};
	memcpy(trans.t,init,sizeof init);
	f0.t[0][0]=1;
	cin>>opt>>n;
	if(opt==1){
		for1(i,1,n) cin>>a[i],b[i]=a[i];
		sort(b+1,b+1+n); int nn=unique(b+1,b+1+n)-b-1;
		for1(i,1,n) a[i]=lower_bound(b+1,b+1+nn,a[i])-b,c[a[i]]++;
		for1(i,1,n) {
			matrix tmp=qpow(trans,c[i]);
			tmp=tmp*f0;
			madd(ans,tmp.t[2][0]);
		}
	}else{
		cin>>a0>>p>>q; a0=(a0*p+p)%q+1;
		do{ma[a0]=++ed,a[ed]=a0,a0=(a0*p+p)%q+1;
		}while(ma.find(a0)==ma.end());
		int st=ma[a0];
		for1(i,1,st-1) c[a[i]]++;
		n-=st-1,ed-=st-1;
		int tim=n/ed;
		for1(i,st,ed+st+1) c[a[i]]+=tim;
		int left=n%ed;
		for1(i,st,st+left-1) c[a[i]]++;
		for1(i,1,q){
			matrix tmp=qpow(trans,c[i]);
			tmp=tmp*f0;
			madd(ans,tmp.t[2][0]);
		}
	}
	return cout<<ans,void();
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...