616模拟赛题目背景是 arcaea

B Tempestissimo

抽象一下，这题相当于有一个盒子里面有 $n$ 个球，其中 $m$ 个关键球，求期望抽出所有关键球的时间。

我们可以考虑倒过来，也就是求期望抽出第一个球的时间，最后由 $n$ 减去即可。

考虑这个东西本质上就是

$$\sum_{i=1}^{n-m} P[这个球在第一个关键球之前被抽出]$$

如果我们把关键球先加进去，每个球在哪两个关键球直接抽出本质上是相同的。由 $m$ 个关键球可以分成 $m+1$ 段，于是概率就是 $\frac{1}{m+1}$。答案就是

$$n - \frac{n-m}{m+1}$$

但是 $O(\log n)$ 求逆元必然爆炸，可以考虑 希望 的求逆元方式。我们先离线下来所有询问，假设我们得对 $a_1,a_2,\dots a_n$ 求逆元，我们可以求出这个序列乘起来的逆元，设为 $M$ ，如果需要 $a_i$ 的逆元，我们可以直接拿 $M$ 乘上一段前缀积和后缀积即可。

复杂度 $O(T)$。

---

但是这个题如果暴推组合数也是可以做的（而且还可以练习组合恒等式）。

我们考虑钦定第 $i$ 个位置抽出第 $m$ 个球，那么所有情况抽完关键球的时间的和可以写成下面的式子：

$$\sum_{i=1}^n \binom{i-1}{m-1} \times i$$

注意这里是方案数量不是期望，最后得除以 $\binom n m$ 才是期望。

然后考虑神奇的推式子

$$\begin{aligned} & \sum_{i=1}^n \binom{i-1}{m-1} \times i\\ &= n \sum_{i=1}^n \binom{i-1}{m-1} - \sum_{i=1}^n \binom{i-1}{m-1} (n-i)\\ \end{aligned}$$

考虑

$$\sum_{i=1}^n \binom{i-1}{m-1} (n-i)$$

这个式子，相当于是在前 $i-1$ 个位置选择一个位置，后面 $n-i$ 个位置选择一个位置，还得选上当前的第 $i$ 个位置 的方案个数，也就是从 $n$ 个位置选择 $m+1$ 个位置。也就是说我们可以写成

$$\begin{aligned} &= n\sum_{i=1}^n \binom{i-1}{m-1} - \binom{n}{m+1} \end{aligned}$$

再考虑前面那个

$$\sum_{i=1}^n \binom{i-1}{m-1}$$

我们可以看成在枚举第 $m$ 个数的位置，在哪里。所以可以写成 $\binom{n}{m}$

$$\begin{aligned} &= n\binom{n}{m} - \binom{n}{m+1}\\ &= \binom n m (n - \frac{n-m}{m+1}) \end{aligned}$$

因此期望就是

$$n - \frac{n-m}{m + 1}$$

#define P 998244353
int n , m , T;
int range;
unsigned int seed;
inline unsigned int randint()
{
	seed^=seed<<13;
	seed^=seed>>7;
	seed^=seed<<5;
	return seed%range+1;
}

int f[MAXN];

int Pow( int x , int a ) {
	int ret = 1;
	while( a ) {
		if( a & 1 ) ret = ret * 1ll * x % P;
		x = x * 1ll * x % P , a >>= 1;
	}
	return ret;
}

int N[MAXN] , M[MAXN] , preM[MAXN];

void solve() {
	cin >> T >> seed >> range;
	int ans = 0;
	rep( i , 1 , T ) {
		N[i] = randint() , M[i] = randint();
		if( N[i] < M[i] ) swap( N[i] , M[i] );
	}
	preM[0] = 1;
	rep( i , 1 , T ) preM[i] = preM[i - 1] * 1ll * ( M[i] + 1 ) % P;
	int mul = 1 , iv = Pow( preM[T] , P - 2 );
	per( i , T , 1 ) {
		ans ^= ( N[i] + P - ( N[i] - M[i] ) * 1ll * iv % P * preM[i - 1] % P ) % P;
		iv = iv * 1ll * ( M[i] + 1 ) % P;
	}
	cout << ans << endl;
	
}

signed main() {
//    freopen("input","r",stdin);
//    freopen("fuckout","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
	solve();
}