求 d F
  • 板块学术版
  • 楼主CuteChat
  • 当前回复10
  • 已保存回复12
  • 发布时间2025/6/28 21:42
  • 上次更新2025/6/29 16:28:46
查看原帖
求 d F
726525
CuteChat楼主2025/6/28 21:42
#include <bits/stdc++.h>
using namespace std;
//#undef ONLINE_JUDGE
#define int long long

void clear() {
}
/*
   2*2
*/
int n, c, a[300005], dp[300005], mx, cnt[3005], sm;
const int p = 998244353;

/*
   i == c:
   3 1 2
   i != c:
   2 2 2
*/


long long qpow(long long a, long long b) {
	long long res = 1;
	while (b) {
		if (b & 1) res = res * a % p;
		b >>= 1;
		a = a * a % p;
	}
	return res;
}

int dfs(int i) { // 手上拿的袜子的出现个数(在原堆中)
	if (i == mx || i + 1 == mx) {
		int pd = (i - (i != a[c])) * qpow(sm, p - 2) % p;
		return qpow(pd + p, p - 2); // 拿到大袜子的期望次数
	}
	// 三种情况:
	// 一步结束(p1)
	// 抽到小袜子的概率,重新抽(p2)
	// 抽到大袜子的期望步数,继续抽(p33),p3 表期望
	int p1 = (i - (i != a[c])) * qpow(sm, p - 2) % p;
	int p2 = 0, p3 = 0, p33 = 0;
	for (int j = i + 2; j <= 3000; ++j) {
		if (!cnt[j]) continue;
		(p3 += cnt[j] * j % p * qpow(sm, p - 2) % p * (dfs(j) + 1) % p) %= p;
		(p33 += cnt[j] * j % p * qpow(sm, p - 2) % p) %= p;

	}
	p2 = (1 - p1 - p33 + p + p) % p;
	// f = p1 + (f + 1) * p2 + p3;
	// (1 - p2) f = p1 + p3 + p2
	cout << i << " " << p1 << " " << p2 << " " << p33 << "(" << p3 << ")" << "\n";

	return (p3 + p1 + p2) * qpow(1 - p2 + p, p - 2) % p;
}

void solve() {
	cin >> n >> c;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		sm += a[i];
		cnt[a[i]]++;
		mx = max(mx, a[i]);
	}
	cout << dfs(a[c]) << "\n";
}


signed main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tc = 1;
	//cin >> tc;
	while (tc--) {
		clear();
		solve();
	}
	return 0;
}

不知道为什么样例 2 挂了,感觉理论推导很正确

2025/6/28 21:42
加载中...