CF1626F题解

· · 题解

CF1626F

题意简述

对一个给定的长度为 n，下标为 0\sim n-1 的数列执行以下代码：

long long ans = 0; // create a 64-bit signed variable which is initially equal to 0
for(int i = 1; i <= k; i++)
{
  int idx = rnd.next(0, n - 1); // generate a random integer between 0 and n - 1, both inclusive
                                // each integer from 0 to n - 1 has the same probability of being chosen
  ans += a[idx];
  a[idx] -= (a[idx] % i);
}

求 ans 的期望值 E 与 n^k 的乘积对 998244353 取模的结果。

### 题目分析 因为求的是 $E\times n^k$，所以其实只要求每种情况 $ans$ 的和。 发现 $k$ 很小，尝试分析性质。因为 $a_i\gets a_i-a_i\bmod x$ 等价于 $a_i\gets x\times\lfloor\frac{a_i}{x}\rfloor$，所以，设 $X=\operatorname{lcm}(1,2,\dots,k)$，则一个数 $a_i$ 在变换的过程中不会变得小于 $X\times\lfloor\frac{a_i}{X}\rfloor$。 因此，我们可以将所有的 $a_i$ 都表示为 $X\times\lfloor\frac{a_i}{X}\rfloor+a_i\bmod X$ 的形式。则我们可以直接先把 $ans$ 加上 $\displaystyle\sum_{i=1}^n X\times\lfloor\frac{a_i}{X}\rfloor\times k\times n^{k-1}$。因为在所有情况之和中，每个数会被选 $k\times n^{k-1}$ 次，而它们又不会小于 $X\times\lfloor\frac{a_i}{X}\rfloor$，所以可以直接加上上式，然后对剩余的 $a_i\bmod X$ 作出的贡献进行讨论。下面我们的 $a_i$ 都代指 $a_i\bmod X$。 此时所有的 $a_i$ 都小于 $X$ 了。这允许我们在值域上 dp。定义 $dp_{i,j}$ 表示数 $i$ 在仅考虑前 $j$ 次操作的情况下，在所有情况中的出现次数。 对于 $dp_{i,0}$，显然 $dp_{i,0}=cnt_i$。$cnt_i$ 表示 $i$ 在原序列 $a$ 中的出现次数。 考虑怎么转移，有两种情况： - 第 $j+1$ 次操作选到了 $i$，则 $dp_{i-(i\bmod j+1),j+1}\gets dp_{i-(i\bmod j+1),j+1}+dp_{i,j}$。 - 第 $j+1$ 次操作没有选到 $i$，则有另外的 $n-1$ 种选择。所以 $dp_{i,j+1}\gets dp_{i,j+1}+(n-1)\times dp_{i,j}$。 最后考虑怎么计算答案。因为在第 $j+1$ 次操作中，我们选择 $i$ 的情况数量是 $dp_{i,j}$，而在之后的操作中把这里的每一种情况衍生出的情况数是 $n^{k-j-1}$，所以对于 $dp_{i,j}$，它对答案的贡献是 $i\times n^{k-j-1}\times dp_{i,j}$。 所以答案即为 $\displaystyle\sum_{i=0}^{X-1}\sum_{j=0}^{k-1} i\times n^{k-j-1}\times dp_{i,j}+ans$。$ans$ 是刚刚的 $\displaystyle\sum_{i=1}^n X\times\lfloor\frac{a_i}{X}\rfloor\times k\times n^{k-1}$。 设 $SIZE=\operatorname{lcm}(1,2,\dots,17)$，则该算法的时间复杂度为 $O(k \cdot SIZE)$，对常数要求过高。我们还可以做一个小优化：只计算 $X=\operatorname{lcm}(1,2,\dots,k-1)$。因为我们并不关心最后一次操作变化之后的 $a'_i$（它对答案没有贡献）。 现在 $SIZE$ 就可以降到 $\operatorname{lcm}(1,2,\dots,16)=720720$ 了，可以接受。 Code： ```cpp #include<bits/stdc++.h> using namespace std; const int mod=998244353; int n,a[10000010],x,y,k,m,lcm=1,ans; int power(int p,int q) { int t=1; while(q) { if(q&1)t=1ll*t*p%mod; p=1ll*p*p%mod; q>>=1; } return t; } int dp[1000010][20]; int main() { scanf("%d%d%d%d%d%d",&n,&a[1],&x,&y,&k,&m); for(int i=2;i<=n;i++)a[i]=(1ll*a[i-1]*x%m+y)%m; for(int i=1;i<k;i++)lcm=lcm/__gcd(lcm,i)*i; int fac=power(n,k-1); for(int i=1;i<=n;i++)ans=(ans+1ll*k*fac%mod*(a[i]/lcm)%mod*lcm%mod)%mod,dp[a[i]%=lcm][0]++; for(int j=0;j<k;j++) { for(int i=0;i<lcm;i++) { dp[i-(i%(j+1))][j+1]=(dp[i-(i%(j+1))][j+1]+dp[i][j])%mod; dp[i][j+1]=(dp[i][j+1]+1ll*dp[i][j]*(n-1)%mod)%mod; } } for(int j=0;j<k;j++) { fac=power(n,k-j-1); for(int i=0;i<lcm;i++) ans=(ans+1ll*i*dp[i][j]%mod*fac%mod)%mod; } printf("%d",ans); return 0; } ```