想了一个更一般性的解法

传送门

---

【分析】

不难得出方程，令 \(f_{n, m}\) 表示共 \(n\) 个人，第 \(m\) 个人获胜的概率

则 \(f_{n, m}=\begin{cases} {1\over 2}f_{n, m-1}+{1\over 3}f_{n-1, m-1}&m>1 \\\\ {1\over 2}f_{n, n}+{1\over 6}&n>1\wedge m=1 \\\\ 1&n=1 \end{cases}\)

那么考虑 \(f_{n-1, 1}\sim f_{n-1,n-1}\) 已经计算得出，现在要转移 \(f_{n, 1}\sim f_{n, n}\)

但由于 \(f_{n, 1}\) 的递推式中含有 \(f_{n, n}\)，无法朴素递推。一般这类构成一堆等式的问题需要高斯消元求解，但总复杂度 \(O(n)\cdot O(n^3)=O(n^4)\) 显然是不可能的

但有一个很显然的事情是，如果已知 \(f_{n, n}\) ，则可推出 \(f_{n, 1}\) ，而后递推算出 \(f_{n, 2}\sim f_{n, n-1}\)

那么这样就可以二分一个 \(f_{n, n}\) 然后递推回 \(f_{n, n}\) ，再检查是否符合。这样的话复杂度是 \(O(n^2\log \varepsilon)\) 的，但无法解决模意义下的问题。

---

考虑类似拓域的做法（实际上不是拓域），往实数域 \(<R, +, *>\) 中再引入一个域 \(f_{n, n}\cdot R\)

看不懂的，可以理解为像复数一样，再添一维

那我们可以用二元组 \(\left<a, b\right>=a+b\cdot f_{n, n}\) 来描述这个“域”中的每一个元素

则这个域的运算，有

\(\begin{aligned} \left<a, b\right>+c&=&\left<a+c, b\right> \\\\\left<a,b\right>\cdot c&=&\left<a\cdot c,b\cdot c\right> \end{aligned}\)

其他的不重要，就不写了

那我们可以初始化 \(f_{n, 1}=\left<{1\over 6}, {1\over 2}\right>\)

然后直接 \(O(n)\) 递推到 \(f_{n, n}=\left<a,b\right>\)

又有 \(f_{n, n}=\left<a,b\right>=a+b\cdot f_{n, n}\)

所以解方程得 \(f_{n, n}={a\over 1-b}\)

接下来就可以求出 \(f_{n, 1}\) ，再 \(O(n)\) 递推出 \(f_{n, 2}\sim f_{n, n-1}\)

总复杂度优化为 \(O(n^2)\)

如果题目是模意义下的，这个方法显然也是适用的

---

【代码】

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
typedef double db;
typedef pair<db, db> pdd;
#define fi first
#define se second

inline pdd operator / (const pdd &a, db b) { return pdd(a.fi/b, a.se/b); }
inline pdd operator + (const pdd &a, db b) { return pdd(a.fi+b, a.se); }

const int MAXN=1024;
db f[MAXN][MAXN];
inline void init() {
	f[1][1]=1;
	for(int n=2; n<=1000; ++n) {
		pdd p(1.0/6, 1.0/2);
		for(int m=2; m<=n; ++m)
			p=p/2+f[n-1][m-1]/3;
		f[n][n]=p.fi/(1-p.se);
		f[n][1]=1.0/6+f[n][n]/2;
		for(int m=2; m<=n; ++m)
			f[n][m]=f[n][m-1]/2+f[n-1][m-1]/3;
	}
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
	init();
	int n, m;
	cin>>n>>m;
	cout<<fixed<<setprecision(9)<<f[n][m];
    cout.flush();
    return 0;
}

---

【拓展】

对于像 \(f_{n, n}\) 这样要预先确定的项，我们假定为预先项

对于这类问题，当预先项数量为 \(k\) 时

如果对于每个预先项进行二分，则复杂度为 \(O(n\cdot \log^k\varepsilon)\)

如果采用该方法，可以“拓域”的时候拓 \(k\) 维，这样的转移是 \(O(kn)\) 的，最后对预先项进行高斯消元 \(O(k^3)\) ，总复杂度为 \(O(kn+k^3)\)

可以发现，当 \(k\) 较小时（比如 \(k=1,2,3\)），这个方法是很优秀的，几乎是 \(O(n)\) 的