CF1842G Tenzing and Random Operations题目描述又一道随机问题。Tenzing 有一个长度为nnn的数组aaa和一个整数vvv。Tenzing 将进行mmm次如下操作每次等概率随机选择一个整数iii满足1≤i≤n1 \leq i \leq n1≤i≤n。对所有满足i≤j≤ni \leq j \leq ni≤j≤n的jjj将aja_jaj赋值为ajva_j vajv。Tenzing 想知道经过mmm次操作后∏i1nai\prod_{i1}^n a_i∏i1nai的期望值是多少结果对109710^971097取模。形式化地设M1097M 10^97M1097。可以证明答案可以表示为最简分数pq\frac{p}{q}qp其中ppp和qqq是整数且q≢0(modM)q \not\equiv 0 \pmod{M}q≡0(modM)。请输出等于p⋅q−1 mod Mp \cdot q^{-1} \bmod Mp⋅q−1modM的整数。换句话说输出一个整数xxx满足0≤xM0 \le x M0≤xM且x⋅q≡p(modM)x \cdot q \equiv p \pmod{M}x⋅q≡p(modM)。输入格式输入的第一行包含三个整数nnn、mmm和vvv1≤n≤50001\leq n\leq 50001≤n≤50001≤m,v≤1091\leq m,v\leq 10^91≤m,v≤109。第二行包含nnn个整数a1,a2,…,ana_1,a_2,\ldots,a_na1,a2,…,an1≤ai≤1091\leq a_i\leq 10^91≤ai≤109。输出格式输出∏i1nai\prod_{i1}^n a_i∏i1nai的期望值对109710^971097取模的结果。输入输出样例 #1输入 #12 2 5 2 2输出 #184输入输出样例 #2输入 #25 7 9 9 9 8 2 4输出 #2975544726说明/提示经过所有mmm次操作后数组aaa有三种可能的情况a12,a212a_12,a_212a12,a212概率为14\frac{1}{4}41。a1a212a_1a_212a1a212概率为14\frac{1}{4}41。a17,a212a_17,a_212a17,a212概率为12\frac{1}{2}21。因此a1⋅a2a_1\cdot a_2a1⋅a2的期望值为14⋅(24144)12⋅8484\frac{1}{4}\cdot (24144) \frac{1}{2}\cdot 848441⋅(24144)21⋅8484。由 ChatGPT 4.1 翻译思路考虑如何使其时间复杂度和m无关。发现可以考虑设计一个链i-i1有a[i]条路可以每次给所有的增加v条路径。发现总共经过的增加的路径最多只有n种考虑设f[i][j]表示到第i条路总共经过了j种不同的时刻增加的路径集合指所有增加中其经历了j种增加的路径f[i1][j](f[i][j]a[i1]原本路径f[i][j]jv之前走过的新路)f[i1][j1](f[i][j](m-j)未被选的路径数)v增加的路径数(i1)选择其开始地点最初第一个所在地)最终答案为所有f[n][i]*n^(m-i) 其他随便/n^m总数代码#includebits/stdc.husingnamespacestd;constlonglongmod1e97;longlongn,m,v,a[5005],f[5005][5005],op0;longlongpow2(longlonga1,longlongb1){longlongc11;while(b11){if(b1%21){c1c1*a1%mod;}a1a1*a1%mod;b1/2;}returnc1;}intmain(){cinnmv;for(inti1;in;i){cina[i];}f[0][0]1;for(inti0;in-1;i){for(intj0;jmin((longlong)i,m);j){f[i1][j](f[i1][j]f[i][j]*(a[i1](longlong)j*v%mod))%mod;f[i1][j1](f[i1][j1]f[i][j]*(i1)*1ll%mod*(m-j)*1ll%mod*v)%mod;}}for(inti0;imin(n,m);i){op(opf[n][i]*pow2(pow2(n,mod-2),i))%mod;}coutopendl;return0;}//AKIOI//
CF1842G Tenzing and Random Operations题解
发布时间：2026/6/17 9:19:32
CF1842G Tenzing and Random Operations题目描述又一道随机问题。Tenzing 有一个长度为nnn的数组aaa和一个整数vvv。Tenzing 将进行mmm次如下操作每次等概率随机选择一个整数iii满足1≤i≤n1 \leq i \leq n1≤i≤n。对所有满足i≤j≤ni \leq j \leq ni≤j≤n的jjj将aja_jaj赋值为ajva_j vajv。Tenzing 想知道经过mmm次操作后∏i1nai\prod_{i1}^n a_i∏i1nai的期望值是多少结果对109710^971097取模。形式化地设M1097M 10^97M1097。可以证明答案可以表示为最简分数pq\frac{p}{q}qp其中ppp和qqq是整数且q≢0(modM)q \not\equiv 0 \pmod{M}q≡0(modM)。请输出等于p⋅q−1 mod Mp \cdot q^{-1} \bmod Mp⋅q−1modM的整数。换句话说输出一个整数xxx满足0≤xM0 \le x M0≤xM且x⋅q≡p(modM)x \cdot q \equiv p \pmod{M}x⋅q≡p(modM)。输入格式输入的第一行包含三个整数nnn、mmm和vvv1≤n≤50001\leq n\leq 50001≤n≤50001≤m,v≤1091\leq m,v\leq 10^91≤m,v≤109。第二行包含nnn个整数a1,a2,…,ana_1,a_2,\ldots,a_na1,a2,…,an1≤ai≤1091\leq a_i\leq 10^91≤ai≤109。输出格式输出∏i1nai\prod_{i1}^n a_i∏i1nai的期望值对109710^971097取模的结果。输入输出样例 #1输入 #12 2 5 2 2输出 #184输入输出样例 #2输入 #25 7 9 9 9 8 2 4输出 #2975544726说明/提示经过所有mmm次操作后数组aaa有三种可能的情况a12,a212a_12,a_212a12,a212概率为14\frac{1}{4}41。a1a212a_1a_212a1a212概率为14\frac{1}{4}41。a17,a212a_17,a_212a17,a212概率为12\frac{1}{2}21。因此a1⋅a2a_1\cdot a_2a1⋅a2的期望值为14⋅(24144)12⋅8484\frac{1}{4}\cdot (24144) \frac{1}{2}\cdot 848441⋅(24144)21⋅8484。由 ChatGPT 4.1 翻译思路考虑如何使其时间复杂度和m无关。发现可以考虑设计一个链i-i1有a[i]条路可以每次给所有的增加v条路径。发现总共经过的增加的路径最多只有n种考虑设f[i][j]表示到第i条路总共经过了j种不同的时刻增加的路径集合指所有增加中其经历了j种增加的路径f[i1][j](f[i][j]a[i1]原本路径f[i][j]jv之前走过的新路)f[i1][j1](f[i][j](m-j)未被选的路径数)v增加的路径数(i1)选择其开始地点最初第一个所在地)最终答案为所有f[n][i]*n^(m-i) 其他随便/n^m总数代码#includebits/stdc.husingnamespacestd;constlonglongmod1e97;longlongn,m,v,a[5005],f[5005][5005],op0;longlongpow2(longlonga1,longlongb1){longlongc11;while(b11){if(b1%21){c1c1*a1%mod;}a1a1*a1%mod;b1/2;}returnc1;}intmain(){cinnmv;for(inti1;in;i){cina[i];}f[0][0]1;for(inti0;in-1;i){for(intj0;jmin((longlong)i,m);j){f[i1][j](f[i1][j]f[i][j]*(a[i1](longlong)j*v%mod))%mod;f[i1][j1](f[i1][j1]f[i][j]*(i1)*1ll%mod*(m-j)*1ll%mod*v)%mod;}}for(inti0;imin(n,m);i){op(opf[n][i]*pow2(pow2(n,mod-2),i))%mod;}coutopendl;return0;}//AKIOI//
