题意：给出四个数 \(U,T,P,C\)，代表你现在有四种牌，分别有这么多张。你会重复以下操作：
-
从剩下的牌中选一张扔掉。
-
如果这张牌是第一类牌，得两分；如果是第二类牌，得一分；如果是第三类牌，不得分；如果是第四类牌，得分清空且直接结束。
你可以随时结束你的操作。
求最好的操作策略下期望得分。\(U,T,P,C\le 10^6\)。
做法：
首先 \(P\) 没有啥用，跟我们的答案没关系，扔出来也就是过一手，不影响答案。
考虑我们把第四种牌的代价改一改，假设目前收益为 \(s\)，那么他的收益是 \(-s\)，并且可以继续摸，如果剩下卡牌的平均值为正数，继续摸；否则立刻结束。解释一下为什么这样是对的因为如果是正的，下一步收益期望就是平均数，显然这样很好，是正收益；否则，你剩下的牌肯定没有一开始多，肯定收益不如开始。
所以我们就可以枚举一下目前的情况，假设用了 \(x\) 张一类牌，\(y\) 张二类牌，答案就是每一步的期望收益，为：
第一项是我达到当前这个局面的概率，第二项是下一步的期望。
然后就不太好做了，因为这里有跟两项都相关的项。
那么我们考虑枚举 \(i+j\)，去掉这些相关的项，那么对于一个 \(i+j=t\)，答案为：
发现我们可以快速算出 \(i\) 的一个上界限制，记为 \(l\)。
分离一下系数，把 \(i\) 乘到组合数里去，那就等于我现在要解决一个形如 \(f(s,t) = \sum\limits_{i=0}^t\binom{U}{i}\binom{V}{s-i}\) 的求和问题。
考虑组合意义，这个东西就等于我们要在 \(U+V\) 个物品里选 \(s\) 个，且前 \(U\) 个中最多选 \(t\) 个物品。首先 \(t\to t+1\) 是简单的，直接加一项即可，重点是对于 \(s \to s + 1\) 如何处理，我们考虑我们可以在 \(f(s,t)\) 的基础上，在剩下 \((U+V-s)\) 个位置里再任选一个，但是这样有两个问题：前 \(U\) 个中会多于 \(t\) 个，对于一个合法方案会统计 \(s+1\) 次。后者好解决，直接除即可，问题是前者，我们考虑这种情况刚好就是前 \(U\) 个中选满 \(t +1\) 个，选择一个作为我们这一次选的位置，减掉即可，写成柿子，那么就有：
直接按这个东西递推即可，复杂度线性，有些逆元我偷懒就用了快速幂算了。
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 3e6 + 5, mod = 998244353;
int u, t, p, c, jc[maxn], revjc[maxn], n, inv[maxn];
void prepare() {jc[0] = jc[1] = revjc[0] = revjc[1] = 1;inv[0] = inv[1] = 1;for (int i = 2; i <= n; i++)jc[i] = jc[i - 1] * i % mod,revjc[i] = (mod - mod / i) * revjc[mod % i] % mod,inv[i] = revjc[i];for (int i = 2; i <= n; i++)revjc[i] = revjc[i] * revjc[i - 1] % mod;
}
int C(int m, int n) {if(m < 0 || n < 0 || m < n)return 0;return jc[m] * revjc[n] % mod * revjc[m - n] % mod;
}
int ans;
int qpow(int x, int k, int p) {int res = 1;while(k) {if(k & 1)res = res * x % p;x = x * x % p; k >>= 1;}return res;
}
int x, y, res;
signed main() {cin >> u >> t >> p >> c;n = u + t + c;prepare();x = res = 0, y = -1;for (int i = 0; i <= u + t; i++) {if(2 * u + t - (c + 1) * i <= 0)break;int lim = (2 * u + t - (c + 1) * i) / (c + 1);int coef = inv[u + t + c - i] * (2 * u + t - (c + 1) * i) % mod * qpow(C(u + t + c, i), mod - 2, mod) % mod;// cout << coef << "Adf" << " " << inv[u + t + c - i] << " " << C(u + t + c, i) << endl;if(x < i) {res = (res * (u + t - x) - C(u, y + 1) * C(t, x - y) % mod * (y + 1) % mod + mod) % mod * inv[x + 1] % mod;x++;}while(y < lim) {y++;res = (res + C(u, y) * C(t, x - y)) % mod;}while(y > lim) {res = (res - C(u, y) * C(t, x - y) % mod + mod) % mod;y--;}ans = (ans + coef * res) % mod;}x = res = 0, y = -1;for (int i = 1; i <= u + t; i++) {if(2 * u + t - (c + 1) * i <= 0)break;int lim = (2 * u + t - (c + 1) * i) / (c + 1); lim--;if(lim < 0)break;int coef = inv[u + t + c - i] * (c + 1) % mod * qpow(C(u + t + c, i), mod - 2, mod) % mod * u % mod;if(x < i - 1) {res = (res * (u - 1 + t - x) - C(u - 1, y + 1) * C(t, x - y) % mod * (y + 1) % mod + mod) % mod * inv[x + 1] % mod;x++;}while(y < lim) {y++;res = (res + C(u - 1, y) * C(t, x - y)) % mod;}while(y > lim) {res = (res - C(u - 1, y) * C(t, x - y) % mod + mod) % mod;y--;}ans = (ans - coef * res % mod + mod) % mod;}cout << ans << endl;return 0;
}