题解：CF1626F A Random Code Problem
AC_Lover
·
·
题解
CF1626F A Random Code Problem
注意到每次选择的随机序列 $[idx_1,\dots,idx_k]$ 都是独立的，所以考虑在每个操作上统计贡献。定义 $f_{i,j}$ 表示考虑前 $i$ 次修改操作，在所有情况下 $j$ 的出现次数的总和。钦定第 $(i+1)$ 次选择到的数是 $j$，则前面方案数贡献就是 $f_{i,j}$，后面有 $(k-i-1)$ 次选择，方案数是 $n^{k-i-1}$，因此有贡献 $j\times f_{i,j}\times n^{k-i-1}$。
分析 $f_{i,j}$ 的转移，考虑第 $(i+1)$ 次操作。随便拉一个序列出来，假设其中有 $t$ 个 $j$。如果这次操作了其中的一个 $j$，有 $t$ 种选法，每种选法都会对应新的一个序列，每个新的序列都有 $(t-1)$ 个 $j$，换言之，对所有情况个数和的贡献为 $t(t-1)$。如果不选 $j$，有 $(n-t)$ 种选法，搞完还剩下 $t$ 个 $j$，总贡献为 $(n-t)t$，所以这个序列对 $f_{i+1,j}$ 的贡献就是 $t(t-1)+(n-t)t=t(n-1)$，根据定义 $\sum t=f_{i,j}$，因此我们得到转移：
$$
f_{i+1,j}\leftarrow f_{i,j}\times (n-1)
$$
并且如果我们选择一个 $j$ 操作，那么 $j\leftarrow j-(j\bmod i+1)$，对新的 $j$ 个数会有贡献，有转移：
$$
f_{i+1,j-(j\bmod i+1)}\leftarrow f_{i,j}
$$
直接按原值域操作，时间复杂度 $O(n+kA)$，不能接受。考虑用数论优化。
观察操作 $x\leftarrow x-(x\bmod [1\sim k])$，如果 $x$ 是 $1\sim k$ 的公倍数，即令 $M=\mathrm{lcm}(1\sim k)$，如果 $M\mid x$，那这些操作对 $x$ 是没有任何影响的。同理，对于数 $x=pM+q(q<M)$，$(pM)$ 部分在取模中是没有变化的，所以操作只会影响 $q=x\bmod M$，因此在求解前，先把所有 $a_i$ 对 $M$ 取模，而对于 $\left\lfloor\frac{a_i}{M}\right\rfloor\times M$ 的部分，提前计算出对答案的贡献即可。
取 $\mathrm{lcm}(1\sim k)$ 搞不好会被卡常，不过注意到最后一次操作，即 $\bmod k$ 的操作并没有意义，因为后面没有查询了，所以直接取 $M=\mathrm{lcm}(1\sim k-1)$ 即可。时间复杂度 $O(n+Mk)$，可以通过。
**另一种更简洁的思考方式：** 先考虑一个数的情况怎么做，定义 $f_{i,j}$ 表示考虑前 $i$ 次修改操作，原来的数变成了 $j$ 的操作序列个数。转移是简单的，如果不修改当前数，有 $f_{i+1,j}\leftarrow f_{i,j}\times (n-1)$，否则 $f_{i+1,j-(j\bmod i+1)}\leftarrow f_{i,j}$。对于多个数，发现直接放在一起做即可，即赋初值时放在一起，显然不影响统计。
代码：
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int mod=998244353;
inline int Mod(int x) { return x<0 ? x+mod : (x>=mod ? x-mod : x); }
inline void adm(int &x,int y) { x=Mod(x+y); }
const int N=10000010,MAXM=720725,K=20;
int n,k;
int a[N];
int pw[K];
int f[2][MAXM];
int main()
{
int x,y,m;
cin >> n >> a[1] >> x >> y >> k >> m;
for (int i=2;i<=n;i++) a[i]=(1ll*a[i-1]*x+y)%m;
pw[0]=1;
for (int i=1;i<=k;i++) pw[i]=1ll*pw[i-1]*n%mod;
int M=1;
for (int i=1;i<k;i++) M=M*i/__gcd(M,i);
int ans=0;
for (int i=1;i<=n;i++)
{
int ls=(a[i]/M)*M;
adm(ans,1ll*k*pw[k-1]%mod*ls%mod);
a[i]%=M;
}
for (int i=1;i<=n;i++) f[0][a[i]]++;
for (int i=0;i<k;i++)
{
int now=(i&1),nxt=(now^1);
memset(f[nxt],0,sizeof(f[nxt]));
for (int j=0;j<M;j++)
{
adm(f[nxt][j],1ll*f[now][j]*(n-1)%mod);
adm(f[nxt][j-j%(i+1)],f[now][j]);
}
for (int j=0;j<M;j++) adm(ans,(ll)j*f[now][j]%mod*pw[k-i-1]%mod);
}
cout << ans << "\n";
return 0;
}
```