【XSY3409】树（概率与期望，思维）

【XSY3409】树（概率与期望，思维）

考虑累加种下第 i i i 棵不同的树树到种下第 i + 1 i+1 i+1 棵不同的树之间的时间间隔，设 f ( i ) f(i) f(i) 表示种了 i i i 棵不同的树游戏仍未结束的概率，那么有：
a n s = ∑ i = 0 n − 1 f ( i ) ( ∑ t = 0 ∞ ( i n ) t ( 1 − i n ) ( t + 1 ) ) = ∑ i = 0 n − 1 n n − i f ( i ) begin{aligned} ans&=sum_{i=0}^{n-1}f(i)left(sum_{t=0}^{infty}left(frac{i}{n}right)^tleft(1-frac{i}{n}right)(t+1)right)\ &=sum_{i=0}^{n-1}frac{n}{n-i}f(i) end{aligned} ans​=i=0∑n−1​f(i)(t=0∑∞​(ni​)t(1−ni​)(t+1))=i=0∑n−1​n−in​f(i)​
设 g ( i ) g(i) g(i) 表示恰好在种了 i i i 棵不同的树时游戏结束的概率，那么有 f ( i ) = 1 − ∑ j ≤ i g ( j ) f(i)=1-sum_{jleq i}g(j) f(i)=1−∑j≤i​g(j)。

考虑恰好在种了 i i i 棵不同的树时游戏结束的情形会是怎样：有 i i i 个位置是我们种的树，剩下 n − i n-i n−i 个位置是它们自己长出来的（称这些位置为空位置），我们需要保证这 n − i n-i n−i 个空位置不能相邻（否则长不出来）。把符合这种条件的游戏情形称为 ”结束情形“。

考虑先把这 n − i n-i n−i 个位置选出来，概率为 ( i n − i ) ( n − 1 i − 1 ) dfrac{binom{i}{n-i}}{binom{n-1}{i-1}} (i−1n−1​)(n−ii​)​。

当然也有可能一些本来我们要种树的地方它自己长出来了，导致游戏提前结束，所以这部分的概率要剪掉。而发现当存在空位置相邻时游戏一定不可能结束，所以（在我们限制的情形下，游戏提前结束的概率）就等于（游戏提前结束的概率），即游戏不可能在我们限制的情形之外提前结束，于是直接减掉 ∑ j < i g ( j ) sum_{j g ( i ) = ( i n − i ) ( n − 1 i − 1 ) − ∑ j < i g ( j ) g(i)=dfrac{binom{i}{n-i}}{binom{n-1}{i-1}}-sum_{j 你发现 f ( i ) f(i) f(i) 刚好等于 ( i n − i ) ( n − 1 i − 1 ) dfrac{binom{i}{n-i}}{binom{n-1}{i-1}} (i−1n−1​)(n−ii​)​，即把 n − i n-i n−i 个位置选出来的概率。

另一种解释是：考虑在所有树都长出来的情况下 ”宣布“ 游戏结束，但仍能继续种树，那么之后无论我怎么种树总是满足 ”结束情形“ 的要求。所以前 i i i 轮中 ”宣布“ 了游戏结束的概率就等于第 i i i 轮时的情形满足 ”结束情形“ 要求的概率。

#include

#define N 10000010

using namespace std;

namespace modular
{
	const int mod=1000000007;
	inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
	inline int dec(int x,int y){return x-y<0?x-y+mod:x-y;}
	inline int mul(int x,int y){return 1ll*x*y%mod;}
	inline void Add(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}
}using namespace modular;

inline int poww(int a,int b)
{
	int ans=1;
	while(b)
	{
		if(b&1) ans=mul(ans,a);
		a=mul(a,a);
		b>>=1;
	}
	return ans;
}

inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^'0');
		ch=getchar();
	}
	return x*f;
}

int n,fac[N],ifac[N];

inline int inv(int x)
{
	return mul(ifac[x],fac[x-1]);
}

inline int C(int n,int m)
{
	return mul(mul(fac[n],ifac[m]),ifac[n-m]);
}

inline int invC(int n,int m)
{
	return mul(mul(ifac[n],fac[m]),fac[n-m]);
}

int main()
{
	n=read();
	fac[0]=1;
	for(int i=1;i<=n;i++) fac[i]=mul(fac[i-1],i);
	ifac[n]=poww(fac[n],mod-2);
	for(int i=n;i>=1;i--) ifac[i-1]=mul(ifac[i],i);
	int ans=0;
	for(int i=0;i=n-(n/2)?dec(1,mul(C(i,n-i),invC(n-1,i-1))):1));
	printf("%dn",mul(ans,n));
	return 0;
}