CF1842G Tenzing and Random Operations题解

CF1842G Tenzing and Random Operations

题目描述

又一道随机问题。

Tenzing 有一个长度为nnn的数组aaa和一个整数vvv。

Tenzing 将进行mmm次如下操作：

1. 每次等概率随机选择一个整数iii，满足1≤i≤n1 \leq i \leq n1≤i≤n。
2. 对所有满足i≤j≤ni \leq j \leq ni≤j≤n的jjj，将aja_jaj​赋值为aj+va_j + vaj​+v。

Tenzing 想知道，经过mmm次操作后，∏i=1nai\prod_{i=1}^n a_i∏i=1n​ai​的期望值是多少，结果对109+710^9+7109+7取模。

形式化地，设M=109+7M = 10^9+7M=109+7。可以证明答案可以表示为最简分数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≤x<M0 \le x < M0≤x<M且x⋅q≡p(modM)x \cdot q \equiv p \pmod{M}x⋅q≡p(modM)。

输入格式

输入的第一行包含三个整数nnn、mmm和vvv（1≤n≤50001\leq n\leq 50001≤n≤5000，1≤m,v≤1091\leq m,v\leq 10^91≤m,v≤109）。

第二行包含nnn个整数a1,a2,…,ana_1,a_2,\ldots,a_na1​,a2​,…,an​（1≤ai≤1091\leq a_i\leq 10^91≤ai​≤109）。

输出格式

输出∏i=1nai\prod_{i=1}^n a_i∏i=1n​ai​的期望值对109+710^9+7109+7取模的结果。

输入输出样例 #1

输入 #1

2 2 5 2 2

输出 #1

84

输入输出样例 #2

输入 #2

5 7 9 9 9 8 2 4

输出 #2

975544726

说明/提示

经过所有mmm次操作后，数组aaa有三种可能的情况：

1. a1=2,a2=12a_1=2,a_2=12a1​=2,a2​=12，概率为14\frac{1}{4}41​。
2. a1=a2=12a_1=a_2=12a1​=a2​=12，概率为14\frac{1}{4}41​。
3. a1=7,a2=12a_1=7,a_2=12a1​=7,a2​=12，概率为12\frac{1}{2}21​。

因此，a1⋅a2a_1\cdot a_2a1​⋅a2​的期望值为14⋅(24+144)+12⋅84=84\frac{1}{4}\cdot (24+144) + \frac{1}{2}\cdot 84=8441​⋅(24+144)+21​⋅84=84。

由 ChatGPT 4.1 翻译

思路

考虑如何使其时间复杂度和m无关。
发现可以考虑设计一个链，i->i+1有a[i]条路，可以每次给所有的增加v条路径。
发现总共经过的增加的路径最多只有n种，考虑设f[i][j]表示到第i条路总共经过了j种不同的时刻增加的路径集合（指所有增加中其经历了j种增加的路径）
f[i+1][j]+=(f[i][j]a[i+1]（原本路径）+f[i][j]jv（之前走过的新路）)
f[i+1][j+1]+=(f[i][j](m-j)（未被选的路径数)v（增加的路径数）(i+1)（选择其开始地点（最初第一个所在地））)
最终答案为所有f[n][i]*n^(m-i) （其他随便）/n^m（总数）

代码

#include<bits/stdc++.h>usingnamespacestd;constlonglongmod=1e9+7;longlongn,m,v,a[5005],f[5005][5005],op=0;longlongpow2(longlonga1,longlongb1){longlongc1=1;while(b1>=1){if(b1%2==1){c1=c1*a1%mod;}a1=a1*a1%mod;b1/=2;}returnc1;}intmain(){cin>>n>>m>>v;for(inti=1;i<=n;i++){cin>>a[i];}f[0][0]=1;for(inti=0;i<=n-1;i++){for(intj=0;j<=min((longlong)i,m);j++){f[i+1][j]=(f[i+1][j]+f[i][j]*(a[i+1]+(longlong)j*v%mod))%mod;f[i+1][j+1]=(f[i+1][j+1]+f[i][j]*(i+1)*1ll%mod*(m-j)*1ll%mod*v)%mod;}}for(inti=0;i<=min(n,m);i++){op=(op+f[n][i]*pow2(pow2(n,mod-2),i))%mod;}cout<<op<<endl;return0;}//>>AKIOI<<//