526互联

CF908D New Year and Arbitrary Arrangement 题解

发布时间 2023-10-12 19:20:05作者: xuantianhao

New Year and Arbitrary Arrangement

思路：

期望题果然还是恶心呀！

我们设 \(f[i][j]\) 表示当串中有 \(i\) 个 \(a\) 和 \(j\) 个 \(ab\) 时的方案数。为了方便，设 \(A=\dfrac{P_a}{P_a+P_b},B=\dfrac{P_b}{P_a+P_b}\)。

显然，可以这样转移：

\[f[i][j]=f[i+1][j]\times A+f[i][i+j]\times B \]

因为，如果串后面加上一个 \(a\)，概率是 \(A\)，并且加完后唯一的影响就是 \(i+1\)；如果加入一个 \(b\)，概率是 \(B\)，加完后前面每一个 \(a\) 都会与这个 \(b\) 形成一对 \(ab\)。

那么边界条件呢？

显然，当 \(i+j\geq k\) 时，只要再往后面加入一个 \(b\)，过程就停止了。

则这个的期望长度应该是：

\[B\times \sum\limits_{a=0}^{\infty}(i+j+a)\times A^a \]

其中，枚举的这个 \(a\) 是在终于搞出一个 \(b\) 前，所刷出的 \(a\) 的数量。

为了方便，我们设 \(i+j=c\)，并用 \(i\) 替换 \(a\)。即：

\[B\times \sum\limits_{i=0}^{\infty}(c+i)\times A^i \]

因为 \(A+B=1\)，我们可以用 \((1-A)\) 代 \(B\)。

即：

\[(1-A)\times \sum\limits_{i=0}^{\infty}(c+i)\times A^i \]

拆开括号得:

\[\sum\limits_{i=0}^{\infty}(c+i)\times A^i-\sum\limits_{i=0}^{\infty}(c+i)\times A^{i+1} \]

一上来直接 \(\infty\) 有些不直观，我们用 \(n\) 替换掉:

\[\sum\limits_{i=0}^n(c+i)\times A^i-\sum\limits_{i=0}^n(c+i)\times A^{i+1} \]

在第二个式子里面用 \(i+1\) 代掉 \(i\):

\[\sum\limits_{i=0}^n(c+i)\times A^i-\sum\limits_{i=1}^{n+1}(c+i-1)\times A^i \]

将第一个 \(\Sigma\) 中 \(i=0\) 的情况和第二个 \(\Sigma\) 中 \(i=n+1\) 的情况分别提出：

\[c+\sum\limits_{i=1}^n(c+i)\times A^i-\sum\limits_{i=1}^n(c+i-1)\times A^i-(c+n)\times A^{n+1} \]

合并两个 \(\Sigma\)：

\[c+\sum\limits_{i=1}^nA^i-(c+n)\times A^{n+1} \]

套等比数列求和公式，注意要先提出一个 \(A\) 使首项为为一。

\[c+A\times \dfrac{1-A^n}{1-A}-(c+n)\times A^{n+1} \]

注意到 \(1-A=B\)：

\[c+A\times \dfrac{1-A^n}{B}-(c+n)\times A^{n+1} \]

现在，考虑 \(n\rightarrow\infty\) 的情况，即：

\[\lim\limits_{n\rightarrow\infty}c+A*\dfrac{1-A^n}{B}-(c+n)*A^{n+1} \]

注意到 \(0<A<1\)，因此
\(\lim\limits_{n\rightarrow\infty}A^n=0\) 带入发现：

\[c+A\times \dfrac{1-0}{B}-(c+n)\times 0 \]

处理一下 \(c+\dfrac{A}{B}\) 注意到我们一开始的定义了吗？

\[A=\dfrac{P_a}{P_a+P_b},B=\dfrac{P_b}{P_a+P_b} \]

以及 \(c=i+j\) 代入得：

\[i+j+\dfrac{P_a}{P_b} \]

也就是说，边界条件就是 \(f[i][j]=i+j+\dfrac{P_a}{P_b}(i+j\geq k)\)！！！

再搬出我们一开始的转移式：

\[f[i][j]=f[i+1][j]\times A+f[i][i+j]\times B \]

完事。

哦，另外，还要思考一下答案到底是 \(f[0][0]\) 还是 \(f[1][0]\)。

因为一开始的那些 \(b\)，无论来多少个都是没用的，因此不如直接从 \(f[1][0]\) 开始。事实上，你如果把转移式代回去或者打个表的话，你会发现就有 \(f[0][0]=f[1][0]\)。

复杂度 \(O(k^2+\log mod)\)。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
const int N=1e3+100;
int n,a,b,c,A,B;
int f[N][N];
int ksm(int x,int y){
    int z=1;
    for(;y;(x*=x)%=mod,y>>=1) if(y&1) (z*=x)%=mod;
    return z;
}
int dfs(int x,int y){
    if(x+y>=n) return x+y+c;
    if(f[x][y]!=-1) return f[x][y];
    int &res=f[x][y];
	res=0;
    (res+=dfs(x+1,y)*A%mod)%=mod;
    (res+=dfs(x,x+y)*B%mod)%=mod;
    return res;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
    cin>>n>>a>>b;
	memset(f,-1,sizeof(f));
	A=a*ksm(a+b,mod-2)%mod;
	B=b*ksm(a+b,mod-2)%mod;
	c=a*ksm(b,mod-2)%mod;
    cout<<dfs(1,0);
    return 0;
}