网站建立方案,滁州公司做网站,网站建设系统哪家好,互联网销售公司正题
题目链接:https://www.ybtoj.com.cn/contest/113/problem/2 题目大意
一个空序列#xff0c;每次往末尾加入一个[1,m][1,m][1,m]中的随机一个数。如果末尾两个数相同都为xxx且(xt)(xt)(xt)#xff0c;那么将它们合并成x1x1x1。
如果序列长度为nnn且无法合…正题
题目链接:https://www.ybtoj.com.cn/contest/113/problem/2 题目大意
一个空序列每次往末尾加入一个[1,m][1,m][1,m]中的随机一个数。如果末尾两个数相同都为xxx且(xt)(xt)(xt)那么将它们合并成x1x1x1。
如果序列长度为nnn且无法合并则结束求序列期望和。
n,m∈[1,103],t∈[1,109]n,m\in[1,10^3],t\in[1,10^9]n,m∈[1,103],t∈[1,109] 解题思路
首先显然地tmin{nm−1,t}tmin\{nm-1,t\}tmin{nm−1,t}。
之后考虑序列中的每一个位置可能的数因为每种情况都有可能所以我们需要算概率先设pi,jp_{i,j}pi,j表示剩余iii个位置时出现jjj的概率那么有pi,j1m×[j≤m]pi,j−12p_{i,j}\frac1m\times [j\leq m]p_{i,j-1}^2pi,jm1×[j≤m]pi,j−12直接出现或者合并出来。
设pi,j×qi,jp_{i,j}\times q_{i,j}pi,j×qi,j表示剩下iii个位置且第一个最终是jjj的概率那么有qi,j1−pi−1,j×[jt]q_{i,j}1-p_{i-1,j}\times [jt]qi,j1−pi−1,j×[jt]qi,jq_{i,j}qi,j就表示在出现了jjj的前提下不变的概率减去会变的概率就好了。
但是因为每个位置的概率不是独立的所以不能直接用这个来算答案。
设pi,j×gi,jp_{i,j}\times g_{i,j}pi,j×gi,j表示在剩下iii个位置且第一个最终是jjj时和的期望和注意期望概率*次数pi,j×fi,jp_{i,j}\times f_{i,j}pi,j×fi,j表示剩下iii个位置时第一个出现过jjj的情况的期望和ansians_iansi表示剩下iii个位置时的期望和。
那么有 ansi∑j1tpi,j×gi,jans_i\sum_{j1}^{t}p_{i,j}\times g_{i,j}ansij1∑tpi,j×gi,j
考虑ggg的递推式有 gi,jqi,j×jansi−1−pi−1,j×fi−1,jg_{i,j}q_{i,j}\times jans_{i-1}-p_{i-1,j}\times f_{i-1,j}gi,jqi,j×jansi−1−pi−1,j×fi−1,j 有qi,jq_{i,j}qi,j的概率最终是jjj填完剩下的且下一个不能出现jjj 考虑fff的递推式有 fi,jgi,j(1−qi,j)fi,j1f_{i,j}g_{i,j}(1-q_{i,j})f_{i,j1}fi,jgi,j(1−qi,j)fi,j1 第一种是最终不变第二种是变成了j1j1j1的情况
这样就可以递推了时间复杂度O(n2)O(n^2)O(n2) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N2100,P1e97;
ll n,m,t,p[N][N],q[N][N],g[N][N],f[N][N],ans[N];
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%P;xx*x%P;b1;}return ans;
}
signed main()
{freopen(sequence.in,r,stdin);freopen(sequence.out,w,stdout);scanf(%lld%lld%lld,n,m,t);ll invpower(m,P-2);tmin(t,nm-1);for(ll i1;in;i)for(ll j1;jt;j){p[i][j](inv*(jm)p[i-1][j-1]*p[i][j-1]%P)%P;q[i][j](1-(jt)*p[i-1][j]P)%P;}for(ll i1;in;i){for(ll jt;j1;j--){if(j!t)g[i][j](q[i][j]*j%Pans[i-1]-f[i-1][j]*p[i-1][j]%PP)%P;elseg[i][j](q[i][j]*j%Pans[i-1])%P;f[i][j](g[i][j]%P(1-q[i][j])*f[i][j1]%P)%P;(ans[i]g[i][j]*p[i][j])%P;}}printf(%lld\n,ans[n]);return 0;
}
