Loading... ## 题意 给定长度为 $n$ 一个数组 $A,A_0=0,A_n\gt 0$，并且有一个长度为 $n$ 数组 $B$，初始全 $0$，重复执行下面动作直到每一个 $i$ 都有 $B_i\geq A_i$： - 随机选择一个下标 $i$，$B_i\leftarrow 0,\forall j\not= i, B_j\leftarrow B_j+1$ 求期望操作次数 范围： - $ 2\leq\ N\leq\ 2\times\ 10^5 $ - $ 0=A_1\leq\ A_2\leq\ \cdots\ \leq\ A_N\leq\ 10^{18} $ - $ A_N\ >\ 0 $ ## 题解 发现正常的状态不太好记，但是发现有用的只有 $\max\left\{A_i-B_i\right\}$，记为 $x$。假如选到了 $i$ 那么有 $x\leftarrow\max\left\{x-1,A_i\right\}$，这样就非常好做了。按照套路设计dp，$dp_i$ 表示 $x=i$ 时，剩余操作步数期望，为了方便书写，记 $cnt_i$ 表示小于等于 $i$ 的 $A$ 个数。 $$ \begin{align} dp_i&=\sum_{j=1}^n dp_{\max\left\{i-1,A_j\right\}}\\ &=\frac{1}{n}\left(cnt_i\times dp_{i-1}+\sum_{j=cnt_i+1}^{n}dp_{A_j}\right)+1\\ dp_i&=\frac{1}{cnt_i}\left(n\left(dp_i-1\right)-\sum_{j=cnt_i+1}^{n}dp_{A_j}\right) \end{align} $$ 已知 $dp_0=0$，但是转移是从大到小，可以设未知数解决，但是可以考虑另一个巧妙的解法设 $f_i=A_n-dp_i$ 那么把已知转化成了 $f_n=0$，即可计算。但是值域很大，所以分段求解，由于每次当 $i=A_j$ 时，转移才会发生本质变化，所以中间部分矩阵搞一搞就好。 ```cpp #include<bits/stdc++.h> // #define ONLINE_JUDGE #define INPUT_DATA_TYPE long long #define OUTPUT_DATA_TYPE int inline __attribute((always_inline)) INPUT_DATA_TYPE read(){register INPUT_DATA_TYPE x=0;register char f=0,c=getchar();while(c<'0'||'9'<c)f=(c=='-'),c=getchar();while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+(c&15),c=getchar();return f?-x:x;}void print(OUTPUT_DATA_TYPE x){if(x<0)x=-x,putchar('-');if(x>9)print(x/10);putchar(x%10^48);return;} const long long mod=998244353; #include<cstring> #define MATRIX_MOD %mod #define MATRIX_DATA_TYPE long long const int MATRIX_MAX_N=2; const int MATRIX_MAX_M=2; struct MATRIX{ int n,m; MATRIX_DATA_TYPE matrix[MATRIX_MAX_N][MATRIX_MAX_M]; MATRIX operator + (const MATRIX &a) const { register int i,j; MATRIX ans; ans.n=n; ans.m=m; for(i=0;i<n;++i) for(j=0;j<m;++j) ans.matrix[i][j]=(matrix[i][j]+a.matrix[i][j])MATRIX_MOD; return ans; } MATRIX operator * (const MATRIX &a) const { register int i,j,k; MATRIX ans; ans.n=n; ans.m=a.m; for(i=0;i<n;++i) for(j=0;j<a.m;++j){ ans.matrix[i][j]=0; for(k=0;k<m;++k) ans.matrix[i][j]=(ans.matrix[i][j]+matrix[i][k]*a.matrix[k][j]MATRIX_MOD)MATRIX_MOD; } return ans; } friend MATRIX operator ^ (MATRIX base,register MATRIX_DATA_TYPE exponential){ register int i,j; MATRIX ans; ans.n=base.n; ans.m=base.n; for(i=0;i<ans.n;++i) for(j=0;j<ans.m;++j) ans.matrix[i][j]=(i==j); while(exponential){ if(exponential&1) ans=ans*base; base=base*base; exponential>>=1; } return ans; } void clear(){ register int i,j; for(i=0;i<n;++i) for(j=0;j<m;++j) matrix[i][j]=0; return; } }base,trans; #define INV_DATA_TYPE long long void getinv(INV_DATA_TYPE *invs,const INV_DATA_TYPE p,int n){ register int i; for(invs[0]=0,invs[1]=1,i=2;i<=n;++i) invs[i]=p-p/i*invs[p%i]%p; return; } long long arr[200010],inv[200010]; int main(){ #ifndef ONLINE_JUDGE freopen("name.in", "r", stdin); freopen("name.out", "w", stdout); #endif register int i; register long long sum=0; int n=read(); for(i=1;i<=n;++i) arr[i]=read(); getinv(inv,mod,n); base.n=base.m=2; trans=base; base.matrix[0][1]=1; for(i=n-1;i;--i){ trans.matrix[0][0]=inv[i]*n%mod, trans.matrix[0][1]=0; trans.matrix[1][0]=inv[i]*(n+mod-sum)%mod,trans.matrix[1][1]=1; base=base*(trans^(arr[i+1]-arr[i])); (sum+=base.matrix[0][0])%=mod; } print(base.matrix[0][0]); #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif return 0; } ``` 最后修改：2024 年 04 月 27 日 © 允许规范转载 打赏 赞赏作者 赞 如果觉得我的文章对你有用，请随意赞赏