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

· · 题解

首先，每个成员的操作是互不影响的，所以序列的顺序都是不重要的，所以我们只在乎每个成员要进行多少次操作，设 c_i 表示成员的操作次数。

Subtask1,2,3 可以直接枚举得到 c_i，考虑如何处理 Subtask4。

观察式子：a_i=(a_{i-1}\times p+p)\bmod q+ 1 (i \geq 1)

由于 a_i 只与 a_{i-1} 有关，只要 a_i 在 a_{1\sim i-1} 出现过，那么后面的数一定与前面的某一段是相同的，所以这是一个循环节。

又由于对 q 进行取模，所以根据鹊巢原理，其循环节长度一定不超过 q，那么完全可以暴力枚举直到找到循环节。

然后就可以求出 c_i。

现在考虑如何求出答案，根据期望的可加性，答案等于每一位成员最终是管理员的期望值之和。

显然每个成员成为管理员的期望只与操作次数有关，而与本身无关。

那么设 f_{i,0/1/2} 表示第 i 次操作时，不在团队内/在团队内且是成员/在团队内且是管理员的期望。

那么有转移：

初始：f_{0,0}=1

ans=\sum_{i=1}^nf_{c_i,2}

又注意到 n\le10^{18}。

自然可以想到矩阵快速幂优化dp。

\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}

初始：

\begin{gathered} \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} \end{gathered}

代码（细节还是很多的，记得开long long）：

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();
}