题目链接：[AHOI2022] 山河重整题意：计数有多少个元素在 $[1,n]$ 的集合，其 $01$ 背包能表示 $[1,n]$ 中的所有数。$1\le n\le 5\times 10^5$，时间限制 $\text{3s}$。首先考虑从小到大加入数字，那么加入数字中途的每一个时刻，所能表示的都应是值域的一个前缀（因为加的数字越来越大）。若目前能组合出 $[1,p]$，加入的新数是 $x$，那么能表示出的集合就变成了 $[1,p]\cup[x,p+x]$。若 $p+1<x$，由于加入的数字越来越大，所以以后再也组合不出 $p+1$ 了。因此，$x$ 需满足 $x\le p+1$，能拼出的新集合变成了 $[1,p+x]$。于是容易得到一个 $\mathcal{O}(n^2)$ 的算法：设 $\text{dp}(i,p)$ 表示考虑前 $i$ 个数，已经能拼出 $[1,p]$ 的方案数。每次只需要决策是否将 $i$ 加入集合，将 $\text{dp}(i-1,p)$ 转移到 $\text{dp}(i,p+i)$ 即可。我们需要一个更好的方式来描述上述过程。直接计数所有满足条件的序列看起来不那么容易，尝试钦定不满足条件的位置，然后进行容斥。确切来说，即找到一组不合法方案的，最小的 $i$，满足 $[1,i]$ 均可拼出但 $i+1$ 无法拼出，对这样的位置进行容斥。若值域 $[1,i]$ 中每个数均可拼出，且值域在 $[1,i]$ 中所有元素的和 $> i$，那么 $i+1$ 一定可以拼出。又需要能拼出 $i$，所以可知：若 $i$ 是这样一个位置，那么值域在 $[1,i]$ 中的所有元素的和恰好为 $i$。我们设 $f_i$ 表示，只考虑值域在 $[1,i]$ 中的元素，能拼出 $[1,i]$ 中每个数字，且总和恰好为 $i$ 的方案数。其计算可以通过 “所有方案” 减去 “$[1,i]$ 中存在元素无法拼出的方案”。前者是 $i$ 的互异拆分数，而后者可以通过之前的 $f$ 求得。更具体些，枚举第一个无法拼出的数字，在计算 $f_i$ 的时候，一个可以贡献的 $f_j$ 大概形如：$[1,j]$ 均可拼出，跳过 $j+1$（无法拼出），$[j+2,i]$ 中的元素加上 $[1,j]$ 中的元素总和恰好为 $i$（由 $f_j$ 定义可知，$[1,j]$ 中的元素之和恰好为 $j$，因此 $[j+2,i]$ 中的元素和应恰好为 $i-j$）。考虑求解互异拆分数的具体做法。拆分出的数字个数是 $\mathcal{O}(\sqrt{n})$ 级别，于是我们将 “计数 $\mathcal{O}(\sqrt{n})$ 个不同数字和为 $n$ 的方案数” 转变为 “对 $i\in[1,\sqrt{n}]$，考虑有多少个数 $\ge i$”。例如，上图可以看作 $12$ 的一组互异拆分 $\{1,2,4,5\}$（每行看作一个数字），也可以看作 $\ge 1$ 的有 $4$ 个，$\ge 2$ 的有 $3$ 个，$\ge 4$ 的有 $2$，$\ge 5$ 的有 $1$ 个（考虑每列）。由于 $\ge i+1$ 的数字个数一定不多于 $\ge i$ 的数字个数，所以可以从 $\sqrt{n}$ 到 $1$ 倒序枚举 $i$，类似完全背包加入一个体积为 $i$ 的元素（表示有 $i$ 个元素 $\ge$ 某一个值）。而 $f_j$ 向 $f_i$ 的贡献中，也存在 $[j+2,i]$ 中数字的背包状物。暴力做法可以从 $i$ 倒序枚举，在背包中逐步加入元素，在适当的时刻加入 $f_j$ 对 $f_i$ 的贡献。考虑用上述方法类似地优化。$f_j$ 贡献的时候，其他所有元素应 $\ge j+2$。所以，我们可以在确定 $[j+2,i]$ 的集合中有多少个数的时候（设其为 $c$，即上图第一列有多少点），将 $f_j$ 贡献到背包的 $j+(j+2)\times c$ 处作为初值（可以结合代码理解）。最后只剩下一个问题。在计算 $f_i$ 的时候，需要 $f_j$ 已经计算好了。但是上述做法中，我们需要先做一次完整的背包，才可以得到 $f_i$ 的系数。注意到，若 $f_j$ 能贡献到 $f_i$，则 $i\ge j+(j+2)$（$i$ 要在 $j$ 的两倍以上）。因此，只需要先计算 $\dfrac{n}{2}$ 以下部分的 $f_i$，便可以得到所有 $f_i$ 的答案（类似一个倍增的过程）。其复杂度为 $T(n)=\mathcal{O}(n\sqrt{n})+T\Big(\dfrac{n}{2}\Big)=\mathcal{O}(n\sqrt{n})$。//Code By CXY07 - It's My Fiesta. #include<bits/stdc++.h> using namespace std; //#define FILE //#define int long long #define randint(l, r) (rand() % ((r) - (l) + 1) + (l)) #define abs(x) ((x) < 0 ? (-(x)) : (x)) #define popc(x) __builtin_popcount(x) #define inv(x) qpow((x), mod - 2) #define lowbit(x) ((x) & (-(x))) #define ull unsigned long long #define pii pair<int, int> #define LL long long #define mp make_pair #define pb push_back #define scd second #define vec vector #define fst first #define endl '\n' #define y1 _y1 const int MAXN = 5e5 + 10; const int INF = 2e9; const double eps = 1e-6; const double PI = acos(-1); //const int mod = 1e9 + 7; //const int mod = 998244353; //const int G = 3; //const int base = 131; int n, mod, lim, Ans; int dp[MAXN], t[MAXN], p2[MAXN]; template<typename T> inline bool read(T &a) { a = 0; char c = getchar(); int f = 1; while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { a = a * 10 + (c ^ 48); c = getchar(); } return a *= f, true; } template<typename A, typename ...B> inline bool read(A &x, B &...y) { return read(x) && read(y...); } void modadd(int &x, int y) { x += y; if(x >= mod) x -= mod; } void run(int n) { if(n <= 1) return; run(n >> 1); for(int i = 0; i <= n; ++i) t[i] = 0; lim = sqrt(2 * n); for(int i = lim; i >= 1; --i) { for(int j = n; j >= i; --j) t[j] = t[j - i]; for(int j = i - 1; j >= 0; --j) t[j] = 0; for(int j = 0; j + (j + 2) * i <= n; ++j) modadd(t[j + (j + 2) * i], dp[j]); for(int j = i; j <= n; ++j) modadd(t[j], t[j - i]); } for(int i = (n >> 1) + 1; i <= n; ++i) modadd(dp[i], mod - t[i]); } signed main () { #ifdef FILE freopen("P8340.in", "r", stdin); freopen("P8340.out", "w", stdout); #endif read(n), read(mod); p2[0] = 1; for(int i = 1; i < MAXN; ++i) p2[i] = (p2[i - 1] + p2[i - 1]) % mod; lim = sqrt(2 * n); dp[0] = 1; for(int i = lim; i >= 1; --i) { for(int j = n; j > i; --j) dp[j] = dp[j - i]; for(int j = i; j >= 1; --j) dp[j] = 0; for(int j = i; j <= n; ++j) modadd(dp[j], dp[j - i]); } run(n); for(int i = 0; i < n; ++i) Ans = (Ans + 1ll * dp[i] * p2[n - i - 1]) % mod; Ans = (p2[n] - Ans + mod) % mod; printf("%d\n", Ans); return 0; }
题目链接：[BJOI2018] 双人猜数游戏题意：提交答案题。现有 $\text{Alice},\text{Bob}$ 两人，要猜出两个数字 $m,n\ (m\le n)$。一开始 $\text{Alice}$ 知道 $m\times n$，$\text{Bob}$ 知道 $m+n$，两人同时知道一个下界 $s$，即 $s\le m\le n$。从 $\text{Alice}$ 或 $\text{Bob}$，交替回答现在自己是否已经知道了 $m,n$。要求是两人在说了总共 $t$ 次“不知道”之后，同时知道了 $m,n$。给出 $s,t$ 和从谁开始，构造一组合法的 $m,n$，使得 $m+n$ 最小的情况下，$m$ 的值最小。对于 $100\%$ 的数据，满足 $1\le s\le 200,\ 2\le t\le 15$，数据保证有解。挺有意思的题。首先需要意识到，之所以在说了若干次“不知道”之后，知道了 $m,n$ 的取值，是因为之前另一人所说的“不知道”能够减少可能的 $(m,n)$。以 $\text{Alice}$ 开头为例，考虑一些简单的情形。以下不考虑两数之间的大小关系。如果第一轮 $\text{Alice}$ 就知道了呢？说明满足 $a\times b=m\times n$ 且 $a,b\ge s$ 的方案是唯一的。如果第二轮 $\text{Bob}$ 就知道了呢？$\text{Bob}$ 知道的是 $m+n$，在所有 $a+b=m+n$ 且 $a,b\ge s$ 的 $(a,b)$ 中，“合法”的数对方案唯一。这里的合法，意思是这对数在这轮之前还不能被另一个人猜到。例如在第二局中，数对 $(a,b)$ “合法”就指“满足 $c\times d=a\times b$ 且 $c,d\ge s$ 的方案不唯一”。如果我们简单地称 $\{(a,b)|a+b=m+n,\ a,b\ge s\}$ 为“和拆分”，$\{(a,b)|a\times b=m\times n,\ a,b\ge s\}$ 为“积拆分”，那么：第 $1$ 轮 $\text{Alice}$ 没猜到 $\to$ 积拆分不唯一。第 $2$ 轮 $\text{Bob}$ 没猜到 $\to$ 和拆分中“积拆分不唯一”的元素不唯一。第 $3$ 轮 $\text{Alice}$ 没猜到 $\to$ 积拆分中“和拆分中‘积拆分不唯一’的元素不唯一”的元素不唯一。以此类推。虽然这样写下去非常绕，但是我们容易从中观察出类似递归的形式。于是，尝试使用递归函数的形式描述上面的文字。我们称“已经完成 $t$ 轮后，下一个回答”的人称为 $p$，另一人称为 $q$。设 $f(t,a,b)$ 表示说了 $\le t$ 轮“不知道”后，$p$ 是否已经能猜到 $a,b$。注意到一个人只有在另外一个人说完话之后才会得到新信息。先判掉边界情况，$f(0,a,b)$ 就意味着和拆分 / 积拆分中元素唯一。然后，如果当前这个人在 $t-2$ 局后就已经能猜出了，那么这一轮肯定也行。接着，枚举积拆分 / 和拆分，判断有多少个元素在当前这轮“合法”。如果这样的元素唯一，那么 $p$ 就猜到了，否则就是暂时还猜不到。于是，我们就可以使用 $f(t,a,b)$ 来初步判断在 $t$ 次“不知道”后，当前 $p$ 能否猜出 $a,b$ 了。怎么判断 $(a,b)$ 满足“在恰好 $t$ 次‘不知道’后，两个人同时猜到了”呢？首先，$f(t,a,b)$ 应为真：这能保证在第 $t$ 轮的时候 $p$ 能够猜到。其次，$f(t-2,a,b),f(t-1,a,b)$ 均应为假：这保证要恰好第 $t$ 轮之后两人才可能猜到。我们使用 $g(a,b)$ 表示上述三个条件是否同时满足。容易想到还有一个条件：在 $p$ 说完“我知道了”之后，$q$ 应该立即也知道了。但是这不代表 $f(t+1,a,b)$ 为真，因为此时有人说出“我知道了”，与 $f$ 的定义情形不符。于是需要特殊判断，这相当于和拆分 / 积拆分中，“$g(a,b)$ 为真”的元素唯一。套上记忆化，暴力从小到大枚举 $m+n$，并从小到大枚举 $m$ 即可通过。跑的很快，所以这题是提交答案题是不是因为出题人没法证明答案上界啊。//Code By CXY07 - It's My Fiesta. #include<bits/stdc++.h> using namespace std; //#define FILE //#define int long long #define randint(l, r) (rand() % ((r) - (l) + 1) + (l)) #define abs(x) ((x) < 0 ? (-(x)) : (x)) #define popc(x) __builtin_popcount(x) #define inv(x) qpow((x), mod - 2) #define lowbit(x) ((x) & (-(x))) #define ull unsigned long long #define pii pair<int, int> #define LL long long #define mp make_pair #define pb push_back #define scd second #define vec vector #define fst first #define endl '\n' #define y1 _y1 const int MAXN = 20; const int INF = 2e9; const double eps = 1e-6; const double PI = acos(-1); //const int mod = 1e9 + 7; //const int mod = 998244353; //const int G = 3; //const int base = 131; int n, m, S, T, opt; map<pii, bool> ok[MAXN]; string who; template<typename T> inline bool read(T &a) { a = 0; char c = getchar(); int f = 1; while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { a = a * 10 + (c ^ 48); c = getchar(); } return a *= f, true; } template<typename A, typename ...B> inline bool read(A &x, B &...y) { return read(x) && read(y...); } bool f(int t, int a, int b) { // 说了 t 次之后,下个人是否已经知道 if(a > b) swap(a, b); if(ok[t].count(mp(a, b))) return ok[t][mp(a, b)]; if(t >= 2 && f(t - 2, a, b)) return true; int cnt = 0, sum = a + b, prod = a * b; if(t == 0) { if(!opt) { for(int i = S; i * i <= prod; ++i) if(prod % i == 0 && prod / i >= S) ++cnt; return ok[t][mp(a, b)] = (cnt == 1); } else { for(int i = S; i <= (sum >> 1); ++i) if(sum - i >= S) ++cnt; return ok[t][mp(a, b)] = (cnt == 1); } } if(!((t & 1) ^ opt)) { // Alice for(int i = S; i * i <= prod; ++i) if(prod % i == 0 && prod / i >= S && !f(t - 1, i, prod / i)) ++cnt; return ok[t][mp(a, b)] = (cnt == 1); } else { // Bob for(int i = S; i <= (sum >> 1); ++i) if(sum - i >= S && !f(t - 1, i, sum - i)) ++cnt; return ok[t][mp(a, b)] = (cnt == 1); } } bool valid(int a, int b) { return f(T, a, b) && (!f(T - 2, a, b)) && (!f(T - 1, a, b)); } signed main () { #ifdef FILE freopen(".in", "r", stdin); freopen(".out", "w", stdout); #endif read(S); cin >> who; read(T); opt = (who == "Bob"); for(int sum = (S << 1); ; ++sum) { for(int a = S, b, prod, cnt; a <= (sum >> 1); ++a) { b = sum - a; prod = a * b, cnt = 0; if(!valid(a, b)) continue; if((T & 1) ^ opt) { // Alice for(int i = S; i * i <= prod; ++i) if(prod % i == 0 && prod / i >= S && valid(i, prod / i)) ++cnt; if(cnt != 1) continue; } else { for(int i = S; i <= (sum >> 1); ++i) if(sum - i >= S && valid(i, sum - i)) ++cnt; if(cnt != 1) continue; } printf("%d %d\n", a, b); return 0; } } return 0; }
【题解】CF1621G Weighted Increasing Subsequences
题目链接：CF1621G Weighted Increasing Subsequences题意：给定长度为 $n$ 的序列 $\{a_n\}$，对于其一个长度为 $k$ 的上升子序列 $a_{i_1},a_{i_2}\cdots a_{i_k}$ 定义其权值为满足 $j\in[1,k]$，存在一个 $x\in(i_k,n]$ 使得 $a_x>a_{i_j}$ 的 $j$ 的个数。计算所有上升子序列的权值和。$1\le n\le 2\times 10^5, 1\le a_i\le 10^9$。首先将序列离散化，计算每个上升子序列的权值是困难的，我们考虑每个位置 $a_p$ 的贡献。对于一个 $a_p$，$i_k$ 最远可以到哪里，使得存在一个 $x\in(i_k,n]$ 满足 $a_x>a_i$？容易发现，若设 $r_p$ 表示最靠右的满足 $a_{r_p}>a_p$ 的下标，则 $i_k<r_p$。注意到 $a_{r_p}$ 必然在后缀单调栈上。于是，对于每一个 $p$，我们需要计算 “经过 $p$，且最后一个元素在 $r_p$ 之前” 的上升子序列个数。容斥成 “经过 $p$，且最后一个元素下标 $\in[r_p,n]$” 的上升子序列个数。本人做到这里的时候被卡住了，“经过定点，结尾在一段后缀的上升子序列个数” 看起来不是很可做。继续观察性质，注意到我们设 $r_p$ 是最靠右的满足 $a_{r_p}>a_p$ 的位置，这意味着 $\forall i\in(r_p, n],\ a_i\le a_p$。说明，任意经过 $p$ 的上升子序列，都不可能在 $(r_p, n]$ 结束。于是 “经过 $p$，且最后一个元素下标 $\in[r_p,n]$” 的限制就转变成了 “经过 $p$，且最后一个元素下标 $=r_p$”，相当于钦定了一个定点，钦定了结尾元素。如何计算这样的子序列个数？首先肯定要把子序列拆成 $p$ 之前、之后。前面是好算的，$p$ 之后的部分，就相当于：“第一个元素下标是 $p$，最后一个元素下标是 $r_p$” 的上升子序列个数。接下来我的处理和官方的题解有一些区别：由于 $r_p$ 是最靠右的满足条件的下标，所以任意从 $p$ 开始延申的上升子序列，其结尾下标必然 $\le r_p$。于是，我们只需要维护 “从 $p$ 开始，以最远的可行位置结尾” 的方案数即可，容易使用树状数组维护。时间复杂度 $\mathcal{O}(n\log n)$。//Code By CXY07 - It's My Fiesta. #include<bits/stdc++.h> using namespace std; //#define FILE //#define int long long #define randint(l, r) (rand() % ((r) - (l) + 1) + (l)) #define abs(x) ((x) < 0 ? (-(x)) : (x)) #define popc(x) __builtin_popcount(x) #define inv(x) qpow((x), mod - 2) #define lowbit(x) ((x) & (-(x))) #define ull unsigned long long #define pii pair<int, int> #define LL long long #define mp make_pair #define pb push_back #define scd second #define vec vector #define fst first #define endl '\n' #define y1 _y1 const int MAXN = 2e5 + 10; const int INF = 2e9; const double eps = 1e-6; const double PI = acos(-1); const int mod = 1e9 + 7; //const int mod = 998244353; //const int G = 3; //const int base = 131; int T, n, m; int a[MAXN], FT[MAXN], pre[MAXN], suf[MAXN]; int mx[MAXN], mxv[MAXN]; LL Ans; vec<int> v; template<typename T> inline bool read(T &a) { a = 0; char c = getchar(); int f = 1; while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { a = a * 10 + (c ^ 48); c = getchar(); } return a *= f, true; } template<typename A, typename ...B> inline bool read(A &x, B &...y) { return read(x) && read(y...); } void add1(int x, int v) { for(; x <= n; x += lowbit(x)) (FT[x] += v) %= mod; } int ask1(int x) { int res = 0; { for(; x; x -= lowbit(x)) (res += FT[x]) %= mod; } return res; } void add2(int x, pii v) { for(; x; x -= lowbit(x)) { if(mx[x] < v.fst) mx[x] = v.fst, mxv[x] = 0; if(mx[x] == v.fst) (mxv[x] += v.scd) %= mod; } } pii ask2(int x) { int _mx = 0, _mxv = 0; for(; x <= n; x += lowbit(x)) { if(_mx < mx[x]) _mx = mx[x], _mxv = 0; if(_mx == mx[x]) (_mxv += mxv[x]) %= mod; } return mp(_mx, _mxv); } void solve() { read(n); v.clear(); Ans = 0; for(int i = 1; i <= n; ++i) read(a[i]), v.pb(a[i]); for(int i = 1; i <= n; ++i) FT[i] = mx[i] = mxv[i] = 0; sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); for(int i = 1; i <= n; ++i) a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1; for(int i = 1; i <= n; ++i) add1(a[i], pre[i] = ask1(a[i] - 1) + 1); for(int i = 1; i <= n; ++i) FT[i] = 0; for(int i = n; i >= 1; --i) { add1(n - a[i] + 1, suf[i] = ask1(n - a[i]) + 1); pii cur = ask2(a[i] + 1); if(!cur.scd) cur = mp(i, 1); (suf[i] -= cur.scd) %= mod; add2(a[i], cur); } for(int i = 1; i <= n; ++i) (Ans += 1ll * pre[i] * suf[i]) %= mod; Ans = (Ans + mod) % mod; printf("%lld\n", Ans); } signed main () { #ifdef FILE freopen(".in", "r", stdin); freopen(".out", "w", stdout); #endif read(T); while(T--) solve(); return 0; }
题目链接：CF1540C Converging Array题意：现在有长度为 $n$ 的数组 $a$ 和长度为 $n - 1$ 的数组 $b$，进行无穷次如下过程直至 $a$ 数组值收敛。选择一个数字 $i$。同时使 $a_i = \min(a_i, \frac{a_i + a_{i + 1} - b_i}{2})$，$a_{i + 1} = \max(a_{i + 1}, \frac{a_i + a_{i + 1} + b_i}{2})$（没有取整）。定义 $F(a, b)$ 为操作完成后 $a_1$ 的值。现在你知道数组 $b$ 和长度为 $n$ 的数组 $c$，保证 $\forall i \in [1, n],\ 0 \le a_i \le c_i$。有 $q$ 组询问，每次问使 $F(a, b) \ge x$ 的数组 $a$ 有多少个。$2\le n\le 100,0\le b_i,c_i\le 100,1\le q\le 10^5,-10^5\le x\le 10^5$。首先，对于上述操作，有几个比较基本的观察：两个操作要么同时成功，要么同时失败。第一个操作成功当且仅当 $2a_i>a_i+a_{i+2}-b_i$，第二个操作成功当且仅当 $2a_{i+1}<a_i+a_{i+1}+b_i$，这两个不等式显然等价。进行任意次操作，$\sum_{i=0}^n a_i$ 保持不变。因为 $\dfrac{a_i+a_{i+1}-b_i}{2}+\dfrac{a_i+a_{i+1}+b_i}{2}=a_i+a_{i+1}$。一次操作成功，当且仅当 $|a_{i+1}-a_i|<b_i$，操作过后 $a_{i+1}-a_i=b_i$。因为上述操作实际上可以描述为先取平均数，然后左右各走 $\dfrac{b_i}{2}$ 步。于是，假设 $\{a_n\}$ “收敛”后变成 $\{f_n\}$，则 $\{f_n\}$ 需要满足以下条件：$\sum_{i=1}^n a_i=\sum_{i=1}^n f_i$。$\forall 1\le i<n, f_{i+1}\ge f_{i}+b_i$。注意到，若对于任意 $1\le i<n$，$f_{i+1}=f_i+b_i$，又有 $\sum_{i=1}^n f_i$ 的限制，于是我们实际上可以解出 $\{f_n\}$。具体来说：$$ f_i=f_1+\sum_{j=1}^{i-1} b_j $$$$ \sum_{i=1}^n a_i=\sum_{i=1}^n f=\sum_{i=1}^n(f_1+\sum_{j=1}^{i-1} b_j) $$$$ =f_1 \times n+\sum_{i=1}^{n-1}(n-i)\times b_i $$于是可以得到：$$ f_1=\dfrac{\sum_{i=1}^n a_i-\sum_{i=1}^{n-1}(n-i)\times b_i}{n} $$但是，我们知道并不一定所有 $f_{i+1}=f_i+b_i$。不过，对于 $f_{i+1}>f_{i}+b_i$ 的情况，我们可以得知：在 $i$ 与 $i+1$ 之间没有进行过操作。这是因为我们一次操作一定会使得 $f_{i+1}=f_i+b_i$，但最后 $f_{i+1}>f_i+b_i$，只能说明一开始 $a_i$ 与 $a_{i+1}$ 的差就已经 $>b_i$ 了。于是，总存在一个前缀 $[1,p]$，满足 $\forall 1\le i<p,f_{i+1}=f_i+b_i$，且 $[p+1,n]$ 与 $[1,p]$ 是互不影响的。因此，如果我们已经得知了 $p$ 的确切值，那么 $f_1$ 的值就得到了确定，他应该是：$$ \dfrac{\text{suma}_p-\text{sumb}_p}{p} $$其中：$$ \text{suma}_p=\sum_{i=1}^p a_i,\ \text{sumb}_p=\sum_{i=1}^{p-1}(p-i)\times b_i $$不过实际上，$p$ 的取值是未知的。那应该怎么确定 $f_1$ 呢？首先，由于一定存在一个合法的 $p$，所以：$$ f_1\in\Big\{\dfrac{\text{suma}_p-\text{sumb}_p}{p}\ |\ p\in[1,n]\Big\} $$同时，假设对于一个前缀 $p$，他不满足 $\forall 1\le i<p,f_{i+1}=f_i+b_i$，那么一定有：$$ f_1<\dfrac{\text{suma}_p-\text{sumb}_p}{p} $$这是因为，前缀 $p$ 不满足一定是因为存在一个位置满足 $f_{i+1}>f_i+b_i$，则 $f_{i+1}$ 的大小超出了我们的预计。又 $f$ 的和是一定的，所以 $i$ 及其前面的部分应该比预计的更小。于是，结合上述两条观察，我们可以得出一个厉害的结论：$$ f_1=\min\Big\{\dfrac{\text{suma}_p-\text{sumb}_p}{p}\Big\} $$至此，我们得到了一种方式，能够快速通过 $\{a_n\}$、$\{b_n\}$ 来计算 $F(a,b)$（即 $f_1$）的值。接下来考虑计数，$F(a,b)\ge x$ 实际上就是：$$ \forall\ p\in[1,n],\ \dfrac{\text{suma}_p-\text{sumb}_p}{p}\ge x $$即：$$ \text{suma}_p\ge \text{sumb}_p+p\times x $$这是一个背包的模型，设 $m$ 为 $a_i$ 的值域上界的话，对于单个 $x$ 进行求解的复杂度是 $\mathcal{O}(n^2m^2)$，容易通过前缀和优化的方式做到单次 $\mathcal{O}(n^2m)$。于是，我们便得到了一种 $\mathcal{O}(qn^2m)$ 的做法。但在困难版中，$q\le 10^5$，这是无法接受的。考虑如何快速计算不同 $x$ 的答案。感性地想，如果这个 $x$ 极小，导致甚至 $\{a_n\}$ 中全是 $0$ 都合法，那么便说明所有序列都是合法的，方案数是：$$ \prod_{i=1}^n (c_i+1) $$需要满足什么条件？应该是：$$ x\le \min\Big\{\dfrac{-\text{sumb}_p}{p}\Big\} $$即就算 $\{a_n\}$ 中全是 $0$ 仍然合法。相应的，如果这个 $x$ 极大，导致 $\forall\ 1\le i\le n,\ a_i=c_i$ 都不满足条件，则说明所有序列都是不合法的，答案为 $0$。他需要满足条件：$$ x>\min\Big\{\dfrac{p\times m-\text{sumb}_p}{p}\Big\} $$因此，只有 $x\in \Big(\min\Big\{\dfrac{-\text{sumb}_p}{p}\Big\},\ \min\Big\{\dfrac{p\times m-\text{sumb}_p}{p}\Big\}\Big]$ 的部分是需要计算的，这里只有 $\mathcal{O}(m)$ 个取值！因此，我们可以在 $\mathcal{O}(n^2m^2)$ 的时间内进行预处理，然后 $\mathcal{O}(1)$ 回答。//Code By CXY07 - It's My Fiesta. #include<bits/stdc++.h> using namespace std; //#define FILE #define int long long #define randint(l, r) (rand() % ((r) - (l) + 1) + (l)) #define abs(x) ((x) < 0 ? (-(x)) : (x)) #define popc(x) __builtin_popcount(x) #define inv(x) qpow((x), mod - 2) #define lowbit(x) ((x) & (-(x))) #define ull unsigned long long #define pii pair<int, int> #define LL long long #define mp make_pair #define pb push_back #define scd second #define vec vector #define fst first #define endl '\n' #define y1 _y1 const int MAXN = 110; const int MAXX = 2e5 + 10; const int SIZ = 1e4 + 10; const int INF = 2e9; const double eps = 1e-6; const double PI = acos(-1); const int mod = 1e9 + 7; //const int mod = 998244353; //const int G = 3; //const int base = 131; int n, m, q, prod = 1, c[MAXN], b[MAXN]; int L, R, sav[MAXX], sumb[MAXN]; int dp[SIZ], sum[SIZ]; bool vis[MAXX]; template<typename T> inline bool read(T &a) { a = 0; char c = getchar(); int f = 1; while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { a = a * 10 + (c ^ 48); c = getchar(); } return a *= f, true; } template<typename A, typename ...B> inline bool read(A &x, B &...y) { return read(x) && read(y...); } int calc(int x) { if(vis[x + (int)1e5]) return sav[x + (int)1e5]; vis[x + (int)1e5] = true; memset(sum, 0, sizeof sum); for(int i = 0; i <= n * m; ++i) sum[i] = 1; for(int i = 1; i <= n; ++i) { memset(dp, 0, sizeof dp); for(int j = 0; j <= n * m; ++j) { if(j < i * x + sumb[i]) continue; dp[j] = sum[j]; if(j > c[i]) (dp[j] -= sum[j - c[i] - 1]) %= mod; } for(int j = 0; j <= n * m; ++j) sum[j] = (dp[j] + (j > 0 ? sum[j - 1] : 0)) % mod; } return sav[x + (int)1e5] = (sum[n * m] + mod) % mod; } signed main () { #ifdef FILE freopen(".in", "r", stdin); freopen(".out", "w", stdout); #endif read(n), m = 100; for(int i = 1; i <= n; ++i) { read(c[i]); prod = prod * (c[i] + 1) % mod; } for(int i = 1; i < n; ++i) read(b[i]); L = R = INF; for(int i = 1, s = 0, si = 0; i <= n; ++i) { sumb[i] = (i * s - si + mod) % mod; (s += b[i]) %= mod, (si += b[i] * i) %= mod; L = min(L, -sumb[i] / i - 1); R = min(R, (i * m - sumb[i]) / i + 1); } read(q); while(q--) { int x; read(x); if(x < L) printf("%lld\n", prod); else if(x > R) puts("0"); else printf("%lld\n", calc(x)); } return 0; }
题目链接：CF1336E Chiori and Doll Picking题意：给定长度为 $n$ 的序列 $\{a_n\}$，$\forall i\in [1,n],\ a_i\in[0,2^m)$。对 $c\in[0,m]$，计算有多少子序列的异或和的 $\text{popcount}=c$。$1\le n\le 2\times 10^5,0\le m\le 53$。看了一年 终于看懂了首先，对于子序列的异或和这种操作，让我们联想到线性基。将一个整数看作 $\mathbb{F}_2$ 上的 $m$ 维向量，设 $V=\text{span}(a_1,a_2,\cdots,a_n)$，即序列中元素张出的向量空间，$k=\dim V$，即线性基的大小。我们知道，对于任意 $x\in V$，都有恰好 $2^{n-k}$ 种方式通过序列中的元素异或来得到他。于是我们可以将问题转变为在线性基上计算答案，最后将答案 $\times 2^{n-k}$。对线性基大小进行讨论。当 $k\le 26$ 的时候，我们可以 $\mathcal{O}(2^{k})$ 枚举线性基中每个元素是否被选择。而在 $k>26$ 的时候，我们希望得到一个 $\mathcal{O}(2^{m-k})$ 的算法，将两个算法结合得到一个 $\mathcal{O}(2^{\frac{m}{2}})$ 的算法。设：$$ A_i=[i\in V] $$$$ F^{(c)}_i=[\text{popcount}(i)=c] $$则我们需要的应该是：$$ \text{Ans}_c=\sum_{i=0}^{2^m-1} A_i F^{(c)}_i $$即我既要能被张出，又要满足 $\text{popcount}$ 为定值 $c$。可以写作：$$ \sum_{i=0}^{2^m-1} A_i\sum_{j=0}^{2^m-1} F^{(c)}_j [i=j] $$将其写成异或卷积的形式，$i=j\iff i\oplus j=0$，于是所求即为：$$ (A*F^{(c)})_0 $$其中 $*$ 表示异或卷积。我们令 $\langle i,j\rangle=\text{popcount}(i \text{ and }j)\bmod 2$，即 $i,j$ 按位与的二进制位下 $1$ 的个数奇偶性。由于已经转化为异或卷积的形式，所以不妨考虑 $\text{FWT}(A)$ 与 $\text{FWT}(F^{(c)})$。首先考虑 $\hat F^{(c)} =\text{FWT}(F^{(c)})$，他可以表示为：$$ \hat F^{(c)}_i=\sum_{\text{popcount(j)=c}} (-1)^{\langle i, j\rangle} $$令 $\text{popcount}(i)=a$，枚举 $b=\text{popcount}(i \text{ and }j)$，可以表示为：$$ \hat F^{(c)}_i=\sum_{\text{popcount(j)=c}} (-1)^{\langle i, j\rangle}=\sum_{b=0}^m (-1)^b \binom{m-a}{c-b}\binom{a}{b} $$注意到其值只与 $a,c$ 相关，设其为 $f(a,c)$。接下来考虑 $\hat A=\text{FWT}(A)$，可以表示为：$$ \hat A_i=\sum_{j\in V}(-1)^{\langle i,j\rangle} $$给出如下结论：对于任意 $i\in[0,2^m)$，有 $\hat A_i\in\{0, 2^k\}$。证明：首先，一个事实是：$\langle a,c\rangle\oplus \langle b,c\rangle=\langle a\oplus b, c\rangle$。对于 $\forall x\in V$，在枚举的元素 $j$ 在遍历 $V$ 中所有元素的时候，$j\oplus x$ 也在遍历 $V$ 中所有元素。因此如果 $\exists j\in V$，$\langle i, j\rangle=1$，则 $\langle i,j\oplus x\rangle=0$，于是上述 $\hat A_i$ 中 $\pm 1$ 贡献抵消，和为 $0$。如果 $\forall j\in V, \langle i,j\rangle=0$，则 $\hat A_i = 2^k$。注意到这是一个齐次线性方程组，因此我们只需要找到一组基础解系，这些向量张出的向量空间中每个元素都满足 $\hat A_i=2^k$。设原线性基消元之后为 $M$，则 $M$ 可以表示为：$$ M=\begin{bmatrix} E_k & X \end{bmatrix} $$可以发现，$\begin{bmatrix} X\\E_{m-k}\end{bmatrix}$ 的列向量构成基础解系（可以验证两两按位与后 $1$ 的个数为偶数）。由于这里有 $m-k$ 个向量，所以我们可以在 $\mathcal{O}(2^{m-k})$ 的时间内，找到所有 $\hat A_i=2^k$ 的位置 $i$。于是，我们所求的答案：$$ \text{Ans}_c=\sum_{i=0}^{2^m-1} A_i F^{(c)}_i=(A*F^{(c)})_0=\dfrac{1}{2^{m}}\sum_{i=0}^{2^m-1} \hat A_i\hat F^{(c)}_i $$$$ =\dfrac{1}{2^m}\sum_{a=0}^m 2^k\text{cnt}_a\times f(a,c) $$其中 $\text{cnt}_a$ 表示 $\hat A_i =2^k$ 的 $i$ 中，$\text{popcount}(i)=a$ 的位置个数。这样，我们就得到了一个神奇的 $\mathcal{O}(2^{m-k})$ 做法。结合对线性基内元素搜索的暴力，可以得到 $\mathcal{O}(2^{\frac{m}{2}})$ 的时间复杂度。//Code By CXY07 - It's My Fiesta. #include<bits/stdc++.h> using namespace std; //#define FILE #define int long long #define randint(l, r) (rand() % ((r) - (l) + 1) + (l)) #define abs(x) ((x) < 0 ? (-(x)) : (x)) #define popc(x) __builtin_popcountll(x) #define inv(x) qpow((x), mod - 2) #define lowbit(x) ((x) & (-(x))) #define ull unsigned long long #define pii pair<int, int> #define LL long long #define mp make_pair #define pb push_back #define scd second #define vec vector #define fst first #define endl '\n' #define y1 _y1 const int MAXN = 2e5 + 10; const int MAXD = 60; const int INF = 2e9; const double eps = 1e-6; const double PI = acos(-1); //const int mod = 1e9 + 7; const int mod = 998244353; //const int G = 3; //const int base = 131; int n, m, k, tot; int a[MAXN], d[MAXD], b[MAXD], cnt[MAXD], Ans[MAXD], s[MAXD]; int f[MAXD][MAXD], C[MAXD][MAXD]; template<typename T> inline bool read(T &a) { a = 0; char c = getchar(); int f = 1; while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { a = a * 10 + (c ^ 48); c = getchar(); } return a *= f, true; } template<typename A, typename ...B> inline bool read(A &x, B &...y) { return read(x) && read(y...); } void Insert(int x) { for(int i = m - 1; ~i; --i) { if(!((x >> i) & 1)) continue; if(!d[i]) return d[i] = x, ++k, void(); x ^= d[i]; } } int qpow(int x, int b) { int res = 1; if(b < 0) b += mod - 1; for(; b; b >>= 1, (x *= x) %= mod) if(b & 1) (res *= x) %= mod; return res; } void DFS(int x, int S) { if(x > tot) return ++cnt[popc(S)], void(); DFS(x + 1, S); if(s[x]) DFS(x + 1, S ^ s[x]); } signed main () { #ifdef FILE freopen("CF1336E2.in", "r", stdin); freopen("CF1336E2.out", "w", stdout); #endif read(n), read(m); for(int i = 0; i < MAXD; ++i) { C[i][0] = 1; for(int j = 1; j <= i; ++j) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod; } for(int i = 1; i <= n; ++i) read(a[i]), Insert(a[i]); if(k <= 26) { for(int i = 0; i <= m; ++i) if(d[i]) s[++tot] = d[i]; DFS(0, 0); for(int i = 0; i <= m; ++i) Ans[i] = cnt[i]; } else { for(int i = m - 1; ~i; --i) for(int j = 0; j < m; ++j) if(i != j && (d[j] >> i) & 1) d[j] ^= d[i]; for(int i = 0; i < m; ++i) { if(d[i]) continue; b[i] = (1ll << i); for(int j = 0; j < m; ++j) if((d[j] >> i) & 1) b[i] |= (1ll << j); } for(int i = 0; i <= m; ++i) if(b[i]) s[++tot] = b[i]; for(int a = 0; a <= m; ++a) for(int c = 0; c <= m; ++c) for(int b = 0, opt = 1; b <= c; ++b) { (f[a][c] += C[m - a][c - b] * C[a][b] % mod * opt) %= mod; opt = (mod - opt) % mod; } DFS(0, 0); for(int i = 0; i <= m; ++i) { for(int j = 0; j <= m; ++j) (Ans[i] += cnt[j] * f[j][i]) %= mod; Ans[i] = Ans[i] * qpow(2, k - m) % mod; } } for(int i = 0; i <= m; ++i) Ans[i] = Ans[i] * qpow(2, n - k) % mod; for(int i = 0; i <= m; ++i) printf("%lld ", Ans[i]); return 0; }
题目链接：[Ynoi2009] rprmq题意：有一个 $n \times n$ 的矩阵 $A$，初始全是 $0$，有 $m$ 次修改操作和 $q$ 次查询操作，先进行所有修改操作，然后进行所有查询操作。一次修改操作会给出 $l_1,l_2,r_1,r_2,x$，代表把所有满足 $l_1 \le i \le r_1$ 且 $l_2 \le j \le r_2$ 的 $A_{i,j}$ 元素加上一个值 $x$。一次查询操作会给出 $l_1,l_2,r_1,r_2$，代表查询所有满足 $l_1 \le i \le r_1$ 且 $l_2 \le j \le r_2$ 的 $A_{i,j}$ 元素的最大值。$1\le n,m\le 5\times 10^4,1\le q \le 5\times 10^5$。或许是一个实现方式有一些小差别的做法。首先考虑离线分治，每次考虑跨过分治中心的查询与修改。将第二维放在线段树上，第一维做扫描线，每次从分治中心 $\text{mid}$ 向左、右进行拓展，如果遇到一个矩阵的开始，或一个矩阵的结束，就在线段树上进行区间修改。由于我们需要的是“矩形 $\max$”，而在分治的时候，第一维变成了时间，所以这个问题在这里就是线段树历史 $\max$。于是对于一个跨过 $\text{mid}$ 的询问，我们只需要在扫描线到了左端点处，或到了右端点处的时候，查询区间历史最大值即可。这一部分中，一个实现的细节是当扫描完 $\text{mid}$ 左侧时，需要将整棵线段树的状态 $\text{roll back}$ 回到还没有扫描左侧时的状态，然后再进行右侧的扫描线。这个可以通过直接对线段树 $\text{DFS}$，将每一个遍历过的节点的权值进行回滚来做到。另一个容易错的点是，如果一个位置上同时有矩形的结束与矩形的开始（即有区间加与区间减操作），那么应该先进行区间减操作，这样才能使历史 $\max$ 保持正确。这样单次查询的复杂度就是 $\mathcal{O}(\log n)$ 的，$\mathcal{O}(q\log n)$ 的总复杂度可以接受。但是修改的复杂度实际上是不太对的。在一般的分治中，其时间复杂度的保证基于每一个操作在进入分治树下一层的时候，都只会进入一边（一个分治树节点）。然而在这里，一个跨越了 $\text{mid}$ 的操作，可以同时向 $[\text{L},\text{mid}]$ 与 $[\text{mid+1},\text{R}]$ 进行递归。也就是说，任意一个修改实际上是在分治的时间维度的一个区间上存在的，而分治的结构本身就类似一棵线段树，所以可以认为一个操作是存在在分治树的一个区间上的。由于分治树是线段树结构，而操作存在在分治树的区间上，这让我们想到“线段树分治”。线段树分治的思想就是将一个存在在某个时间段的修改划分为 $\log$ 个部分，通过在 $\text{DFS}$ 整棵线段树的时候，维护当前线段树节点的祖先的所有修改操作，来保证复杂度。于是，把这个思想套到本题上，就变成了：如果一个操作完全覆盖了当前的分治区间，则把他看作一个类似“初值”的部分。因为在这个区间中这次操作永远存在，所以只需要在进入区间的时候将该操作执行，则分治树的子树中这个操作就一直存在了。从而一个操作被拆分成了 $\mathcal{O}(\log n)$ 次操作，总复杂度是 $\mathcal{O}(m\log^2n+q\log n)$。一个细节：由于进行分治的过程中可能需要进行状态的回滚，而状态的修改次数是 $\mathcal{O}(m\log^2 n)$ 的，直接记录的话空间将与时间同阶。不过实际上，即使修改次数是 $\mathcal{O}(n\log^2 n)$，其修改的元素个数却是 $\mathcal{O}(n\log n)$，可以通过把可回退的部分较为精细地实现来保证空间复杂度。//Code By CXY07 - It's My Fiesta. #include<bits/stdc++.h> using namespace std; //#define FILE //#define int long long #define randint(l, r) (rand() % ((r) - (l) + 1) + (l)) #define abs(x) ((x) < 0 ? (-(x)) : (x)) #define popc(x) __builtin_popcount(x) #define inv(x) qpow((x), mod - 2) #define lowbit(x) ((x) & (-(x))) #define ull unsigned long long #define pii pair<int, int> #define pb emplace_back #define LL long long #define mp make_pair #define scd second #define vec vector #define fst first #define endl '\n' #define y1 _y1 const int MAXN = 5e4 + 10; const int MAXQ = 5e5 + 10; const int MAXD = 16; const int INF = 2e9; const double eps = 1e-6; const double PI = acos(-1); //const int mod = 1e9 + 7; //const int mod = 998244353; //const int G = 3; //const int base = 131; struct info { int l, r, x; info(int _l = 0, int _r = 0, int _x = 0) : l(_l), r(_r), x(_x) {} bool operator < (const info &b) const { return x < b.x; } }; int n, m, q; LL Ans[MAXQ]; vec<info> qp[MAXN], add[MAXN]; template<typename T> inline bool read(T &a) { a = 0; char c = getchar(); int f = 1; while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { a = a * 10 + (c ^ 48); c = getchar(); } return a *= f, true; } template<typename A, typename ...B> inline bool read(A &x, B &...y) { return read(x) && read(y...); } struct NODE { int l1, l2, r1, r2, x, id; void read(int i) { id = i, ::read(l1), ::read(l2), ::read(r1), ::read(r2); } }; vec<NODE> qs[MAXN << 2], mdf[MAXN << 2]; inline LL max(const LL x, const LL y) { return x > y ? x : y; } namespace SMT { int D; LL mx[MAXN << 2], hmx[MAXN << 2], tag[MAXN << 2], htag[MAXN << 2]; LL mx_bak[MAXD][MAXN << 2], hmx_bak[MAXD][MAXN << 2]; LL tag_bak[MAXD][MAXN << 2], htag_bak[MAXD][MAXN << 2]; bool vis[MAXD][MAXN << 2]; inline void pushup(const LL &x) { mx[x] = max(mx[x << 1], mx[x << 1 | 1]); hmx[x] = max(hmx[x], mx[x]); } inline void push(const int &x, const LL &v, const LL &hv) { htag[x] = max(htag[x], tag[x] + hv); tag[x] = tag[x] + v; hmx[x] = max(hmx[x], mx[x] + hv); mx[x] = mx[x] + v; } inline void pushdown(const LL &x) { push(x << 1, tag[x], htag[x]); push(x << 1 | 1, tag[x], htag[x]); htag[x] = 0; tag[x] = 0; } void save(int x) { if(!vis[D][x]) { vis[D][x] = true; mx_bak[D][x] = mx[x], hmx_bak[D][x] = hmx[x]; tag_bak[D][x] = tag[x], htag_bak[D][x] = htag[x]; } } void update(int x, int l, int r, int L, int R, int v) { save(x); if(L <= l && r <= R) return push(x, v, v), void(); int mid = (l + r) >> 1; save(x << 1), save(x << 1 | 1); pushdown(x); if(L <= mid) update(x << 1, l, mid, L, R, v); if(R > mid) update(x << 1 | 1, mid + 1, r, L, R, v); pushup(x); } LL query(int x, int l, int r, int L, int R) { save(x); if(L <= l && r <= R) return hmx[x]; int mid = (l + r) >> 1; LL res = 0; save(x << 1), save(x << 1 | 1); pushdown(x); if(L <= mid) res = max(res, query(x << 1, l, mid, L, R)); if(R > mid) res = max(res, query(x << 1 | 1, mid + 1, r, L, R)); return res; } void clear(int x, int l, int r) { if(!vis[D][x]) return; vis[D][x] = false; if(l == r) return; int mid = (l + r) >> 1; clear(x << 1, l, mid), clear(x << 1 | 1, mid + 1, r); } void roll(int x, int l, int r) { if(!vis[D][x]) return; mx[x] = mx_bak[D][x], hmx[x] = hmx_bak[D][x]; tag[x] = tag_bak[D][x], htag[x] = htag_bak[D][x]; vis[D][x] = false; if(l == r) return; int mid = (l + r) >> 1; roll(x << 1, l, mid), roll(x << 1 | 1, mid + 1, r); } } using SMT::update; using SMT::query; using SMT::clear; using SMT::roll; using SMT::D; void solve(int _x, int vL, int vR, int dep) { if(vL > vR || !qs[_x].size()) return; int mid = (vL + vR) >> 1; NODE cur; for(auto x : qs[_x]) { if(x.r1 < mid) qs[_x << 1].pb(x); if(x.l1 > mid) qs[_x << 1 | 1].pb(x); if(x.l1 <= mid && mid <= x.r1) { qp[x.l1].pb(info(x.l2, x.r2, x.id)); qp[x.r1].pb(info(x.l2, x.r2, x.id)); } } for(auto x : mdf[_x]) { if(x.r1 < mid) { mdf[_x << 1].pb(x), add[x.r1].pb(info(x.l2, x.r2, x.x)); if(vL < x.l1) add[x.l1 - 1].pb(info(x.l2, x.r2, -x.x)); } else if(x.l1 > mid) { mdf[_x << 1 | 1].pb(x), add[x.l1].pb(info(x.l2, x.r2, x.x)); if(x.r1 < vR) add[x.r1 + 1].pb(info(x.l2, x.r2, -x.x)); } else if(x.l1 <= mid && mid <= x.r1) { add[mid].pb(info(x.l2, x.r2, x.x)); if(vL < x.l1) add[x.l1 - 1].pb(info(x.l2, x.r2, -x.x)); if(x.r1 < vR) add[x.r1 + 1].pb(info(x.l2, x.r2, -x.x)); } } D = dep; clear(1, 1, n); for(int i = mid; i >= vL; --i) { sort(add[i].begin(), add[i].end()); for(auto x : add[i]) update(1, 1, n, x.l, x.r, x.x); for(auto x : qp[i]) Ans[x.x] = max(Ans[x.x], query(1, 1, n, x.l, x.r)); } roll(1, 1, n); for(int i = mid; i <= vR; ++i) { sort(add[i].begin(), add[i].end()); for(auto x : add[i]) update(1, 1, n, x.l, x.r, x.x); for(auto x : qp[i]) Ans[x.x] = max(Ans[x.x], query(1, 1, n, x.l, x.r)); } roll(1, 1, n); for(int i = vL; i <= vR; ++i) add[i].clear(), qp[i].clear(); for(auto x : mdf[_x]) { if(x.l1 < mid && mid <= x.r1) { if(x.l1 <= vL) update(1, 1, n, x.l2, x.r2, x.x); else { cur = x; cur.r1 = mid - 1; mdf[_x << 1].pb(cur); } } } solve(_x << 1, vL, mid - 1, dep + 1); D = dep; roll(1, 1, n); for(auto x : mdf[_x]) { if(x.l1 <= mid && mid < x.r1) { if(x.r1 >= vR) update(1, 1, n, x.l2, x.r2, x.x); else { cur = x; cur.l1 = mid + 1; mdf[_x << 1 | 1].pb(cur); } } } solve(_x << 1 | 1, mid + 1, vR, dep + 1); D = dep; roll(1, 1, n); } signed main () { #ifdef FILE freopen("P6109.in", "r", stdin); freopen("P6109.out", "w", stdout); #endif read(n), read(m), read(q); mdf[1].resize(m), qs[1].resize(q); for(int i = 0; i < m; ++i) mdf[1][i].read(i), read(mdf[1][i].x); for(int i = 0; i < q; ++i) qs[1][i].read(i + 1); solve(1, 1, n, 0); for(int i = 1; i <= q; ++i) printf("%lld\n", Ans[i]); return 0; }
题目链接：[HNOI2019] JOJO题意：维护一个字符串 $s$，支持以下两种操作：在 $s$ 末尾插入连续 $x$ 个字符 $c$。将 $s$ 撤回到第 $x$ 次操作之后的状态。在每次操作后，计算 $s$ 的每一个前缀的最长 $\text{border}$ 的长度和。$1\le n\le 10^5$。2019 年 4 月 6 日，HNOI2019 Day 1 赛场上，菜鸡 CXY07 打了这题的 50 分部分分做法，可是下午出成绩的时候发现本题 boom 0。2019 年 7 月，菜鸡 CXY07 看到了神仙们的题解，但是由于太菜，并没有看懂。2019 年 10 月，菜鸡 CXY07 深刻研究了 KMP，可是并没有学出什么所以然。2021 年 9 月 10 日，菜鸡 CXY07 准备回来补坑，结果被此题的可持久化线段树做法劝退。2021 年 9 月 18 日，菜鸡 CXY07 最终还是学习了此题另一种做法，并且在 1h 切掉此题。两年前我在 HNOI2019 的赛场上，折戟沉沙。两年后，我从倒下的地方爬起。我成功了。我不再是以前的那个我了。以上是整活环节，题解在下面计算每一个前缀的最长 $\text{border}$ 的长度和，实际上就是 $\sum\limits_{i=1}^n \text{fail}_i$。这让我们想到 $\text{KMP}$。对于撤回操作，自然可以将操作建成操作树，在上面 $\text{DFS}$ 来计算贡献。每次，我们将操作树上一个节点的答案分为：该节点父亲的答案 $+$ 当前点的贡献。当前点的贡献形如加入一段长度为 $x$ 的字符 $c$ 后，这个后缀的最长 $\text{border}$ 和。如果先不考虑 $\text{KMP}$ 的均摊性质，我们可以把 $(c,x)$ 看作一个新的元素，对这样一个元素的序列进行 $\text{KMP}$。那么加入一段长度为 $x$ 的字符 $c$ 就相当于在该序列末尾加入一个元素 $(c,x)$，我们希望在计算序列末尾元素的 $\text{fail}$ 的过程中，维护答案的增量。若在匹配元素 $(c,x)$ 的时候，前缀中匹配到了一个元素 $(c,x')$，那么至少我们可以匹配 $\min(x,x')$ 个字符 $c$ 了，这一部分的贡献便形如一个等差数列求和。当然，如果在匹配到当前的 $(c,x')$ 之前，有一个更长的前缀，可以匹配 $l$ 个字符 $c$，那么当前的 $(c,x')$ 便只能匹配 $l+1$ ~ $\min(x,x')$ 个 $c$（因为如果 $c$ 的个数 $\le l$，那么就存在一个更长的 $\text{border}$）还有一种特殊情况，若当前元素 $(c,x)$ 没有办法匹配一个长度 $>0$ 的前缀，但是序列的第一个元素 $(c',x')$ 满足 $c'=c,x'\le x$，则当前元素 $(c,x)$ 也是可以匹配序列的第一个元素的。这样，我们就在维护二元组序列的同时，维护了答案的增量。接下来来解决 $\text{KMP}$ 复杂度均摊，导致复杂度无保证的情况。实际上在原数据上，直接均摊也能过设当前正在考察的，长度为 $p$ 的前缀不是当前序列的 $\text{border}$，对于该前缀的形态进行讨论：若该前缀有一个 $>1$ 的周期，则可以直接跳过所有整周期（因为没必要对一模一样的部分检查多遍）。若该前缀没有 $>1$ 的周期，则直接暴力跳 $\text{fail}$ 指针。如果有 $>1$ 的周期，直接跳过串长至少减半；如果没有 $>1$ 的周期，说明 $\text{fail}<\dfrac{\text{len}}{2}$，串长仍然减半。因此，这样处理之后，跳 $\text{fail}$ 的复杂度就不再均摊，而是严格 $\mathcal{O}(\log n)$。于是我们就把该算法优化到 $\mathcal{O}(n\log n)$，可以通过本题。//Code By CXY07 - It's My Fiesta. #include<bits/stdc++.h> using namespace std; //#define FILE #define int long long #define randint(l, r) (rand() % ((r) - (l) + 1) + (l)) #define abs(x) ((x) < 0 ? (-(x)) : (x)) #define popc(x) __builtin_popcount(x) #define inv(x) qpow((x), mod - 2) #define lowbit(x) ((x) & (-(x))) #define ull unsigned long long #define pii pair<int, int> #define LL long long #define mp make_pair #define pb push_back #define scd second #define vec vector #define fst first #define endl '\n' const int MAXN = 1e5 + 10; const int INF = 2e9; const double eps = 1e-6; const double PI = acos(-1); //const int mod = 1e9 + 7; const int mod = 998244353; //const int G = 3; //const int base = 131; int n, m; int len[MAXN], fail[MAXN], Ans[MAXN], tot[MAXN]; int fail2[MAXN], ok[MAXN]; bool is1[MAXN]; char _s[10]; pii opt[MAXN], s[MAXN]; vec<pair<int*, int>> stk; vec<int> G[MAXN]; template<typename T> inline bool read(T &a) { a = 0; char c = getchar(); int f = 1; while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { a = a * 10 + (c ^ 48); c = getchar(); } return a *= f, true; } template<typename A, typename ...B> inline bool read(A &x, B &...y) { return read(x) && read(y...); } void make(int &x, int y) { stk.pb(mp(&x, x)); x = y; } void roll(int siz) { while((int)stk.size() > siz) { *(stk.back().fst) = stk.back().scd; stk.pop_back(); } } int sum(int l, int r) { return ((l + r) * (r - l + 1) >> 1) % mod; } void modadd(int &x, int y) { x += y; if(x >= mod) x -= mod; } void add(int x, int c, int cnt) { int l = ++len[x]; make(s[l].fst, c), make(s[l].scd, cnt); make(tot[l], tot[l - 1] + cnt); if(l == 1) return modadd(Ans[x], sum(0, cnt - 1)), void(); int p = fail[l - 1], lim = 1; while((~p) && s[p + 1] != s[l]) { if(s[p + 1].fst == s[l].fst && s[p + 1].scd >= lim && lim <= cnt) { modadd(Ans[x], sum(tot[p] + lim, tot[p] + min(s[p + 1].scd, cnt))); lim = min(s[p + 1].scd, cnt) + 1; } if(ok[p + 1]) p = fail2[p + 1] - 1; else p = fail[p]; } ++p; if(p && ((l - p) << 1) <= l) make(ok[l], 1), make(fail2[l], fail[l % (l - p) + (l - p)]); if(!p && s[1].fst == c && s[1].scd <= cnt) ++p; if(p) { if(s[p].scd >= lim && lim <= cnt) { modadd(Ans[x], sum(tot[p - 1] + lim, tot[p - 1] + min(s[p].scd, cnt))); lim = min(s[p].scd, cnt) + 1; } if(p == 1 && lim <= cnt) { modadd(Ans[x], tot[p] * (cnt - lim + 1) % mod); lim = cnt + 1; } return make(fail[l], p), void(); } else return make(fail[l], p), void(); } void DFS(int x) { int sav = stk.size(); if(is1[x]) add(x, opt[x].fst, opt[x].scd); for(auto to : G[x]) len[to] = len[x], Ans[to] = Ans[x], DFS(to); roll(sav); } signed main () { #ifdef FILE freopen("jojo.in", "r", stdin); freopen("jojo.out", "w", stdout); #endif read(n); fail[0] = -1; for(int i = 1, op, x; i <= n; ++i) { read(op), read(x); if(op == 2) { G[x].pb(i); continue; } scanf("%s", _s + 1); opt[i] = mp(_s[1] - 'a' + 1, x), is1[i] = true; G[i - 1].pb(i); } DFS(0); for(int i = 1; i <= n; ++i) printf("%lld\n", Ans[i]); return 0; }
【题解】CF1466H Finding satisfactory solutions
题目链接：CF1466H Finding satisfactory solutions题意：由于洛谷目前的中文题面过于简洁，导致看完中文题面之后本题就已经解决了一半，所以我来简单翻译一下英文题面。有 $n$ 个人，第 $i$ 个人初始的时候手上有物品 $i$。他们之间可以交换物品，每个人恰好拿到一个物品。而每个人有对物品的偏好，第 $i$ 个人的偏好用排列 $\{s_{i,n}\}$ 来表示。第 $i$ 个人相较物品 $y$ 更喜欢物品 $x$，当且仅当在排列 $\{s_{i,n}\}$ 中 $x$ 在 $y$ 之前。对于一个物品交换的排列 $p$，表示第 $i$ 个物品最后到了 $p_i$ 的手上。对于一个非空的，人的子集 $S$，如果子集内部的人，使用子集内所有人初始手上的物品进行交换，可以达到以下结果：不存在一个人 $x\in S$，在子集内交换后得到物品 $y\in S$，且第 $x$ 个人比起 $y$ 更喜欢 $p_x$。至少存在一个人 $x\in S$，在子集内交换后得到物品 $y\in S$，且第 $x$ 个人比起 $p_x$ 更喜欢 $y$。则称这样一个子集 $S$ 是“不稳定”的。一个物品交换的排列 $p$ 是“稳定”的，当且仅当不存在一个“不稳定”的子集。现给出一个物品交换的排列 $p$，求有多少种 $\{\{s_{1,n}\},\{s_{2,n}\}\cdots,\{s_{n,n}\}\}$ 使得 $p$ 是“稳定”的。（可以证明，对于一组 $\{\{s_{1,n}\},\{s_{2,n}\}\cdots,\{s_{n,n}\}\}$，恰好存在一个 $p$ 是“稳定”的）$1\le n\le 40$。“不稳定”的定义可以认为是，如果一个子集内部的人，可以在内部进行交换之后，使得没有人拿到的物品变劣，且至少有一个人拿到的物品变优，则这个子集就不乐意了。首先不妨考虑一下，为什么对于一组 $\{\{s_{1,n}\},\{s_{2,n}\}\cdots,\{s_{n,n}\}\}$，其“稳定”的 $p$ 有且仅有一组。首先，我们不妨先让每一个人选择自己最喜欢的物品（在图上连边），则我们会得到一棵基环内向树森林。考虑有哪些人所得到的物品可能需要变化。如果环上的某一个人 $x$ 所得的物品变化了，则这个环就会变成一个“不稳定”的子集，因为其他人都没有变劣，而 $x$ 得到的物品变优了。因此，环上边是不能删除的。所以不妨直接把环上的点，和连到环上的边删除，递归进行问题。最后我们一定会得到若干环，这就是唯一合法的 $p$。那么从这个角度转化一下题意，可以把题意转化为：给定 n 和排列 $\{p_n\}$。对于 $1 \le i \le n$，有排列 $\{s_{i,n}\}$。考虑 $n$ 个点的有向图，有两类边：如果 $j$ 在排列 $\{s_{i,n}\}$ 中比 $p_i$ 靠前，存在黑边 $i \to j$。白边 $i \to p_i$。这张图是合法的，当且仅当所有环中都不存在黑边。求有多少种 $\{\{s_{1,n}\},\{s_{2,n}\}\cdots,\{s_{n,n}\}\}$ 使得这张图是合法的。这是因为，如果环上存在黑边，则这个环上的点按照这个环来交换物品之后，黑边上的人会变优，白色边上的点不变劣，这就出现了一个“不稳定”的子集。现在考虑从 $p$ 入手。显然 $p$ 由若干环构成，根据上述表述，我们知道最后如果把每个环看作一个点，会连出一张 $\text{DAG}$。对于一张 $\text{DAG}$，他自然对应很多种 $\{\{s_{1,n}\},\{s_{2,n}\}\cdots,\{s_{n,n}\}\}$。具体来说，如果设一个点 $i$ 连出的黑边条数为 $d_i$，则一张 $\text{DAG}$ 对应的排列集合个数应该是：$$ \prod_{i=1}^n d_i! \times (n-d_i-1)! $$这是因为黑边连向的元素在 $\{s_{i,n}\}$ 中一定在 $p_i$ 之前，但他们之间可以任意排列。没有出现的边所代表的元素也可以任意排列。于是，我们不难得到一个状压 $\text{dp}$。设 $\text{dp}_S$ 表示将 $S$ 的生成子图连成一个 $\text{DAG}$ 的权值之和。那么有：$$ \text{dp}_S=\sum_{T\subset S} (-1)^{|S-T|-1}\text{dp}_{T}\times f(T,S-T) $$其中 $f(A,B)$ 表示将集合 $B$ 连向集合 $A$ 所贡献的权值和。实际上就是枚举最后一层有哪些元素，然后前面往最后一层连边。前面的 $(-1)^{|S-T|-1}$ 是容斥系数，这是因为对于每一种方案，会枚举出最后一层的所有子集，这个要通过容斥来去掉。不难发现，$f(A,B)$ 与 $A,B$ 具体是多少没有关系，而只与 $|A|,|B|$ 相关。且由于 $B$ 中每个元素向 $A$ 连边都是独立的，所以我们可以直接 $|B|$ 次方。于是就只需要算一个节点向一个大小为 $s$ 的集合连边的权值和 $f(s)$。不妨枚举连了多少条边，可得：$$ f(s)=\sum_{i=0}^s \binom{s}{i} i!(n-i-1)! $$推一推组合式子可以得到：$$ f(s)=\dfrac{n!}{n-s} $$这样，我们就得到了一个 $\mathcal{O}(3^c)$ 的解法。但是这明显不够，我们还需要继续优化。容易发现的一点是，对于相同大小的环，我们并不关系到底是哪几个环，因为所有贡献只和大小相关。因此可以直接把状态压缩为“每种大小的环分别有多少个”，做上述转移的时候，在枚举子集之后乘上一个组合数。这样，状态就被压缩了，对于 $n$ 个点，状态个数 $\max g(n)$ 是以下问题的解：$\sum_{i=1}^n c_i\times i = n$，$\text{maximize }\prod_{i=1}^n (c_i+1)$这个东西在 $n=40$ 的时候只有 $1440$，所以跑的很快。//Code By CXY07 - It's My Fiesta. #include<bits/stdc++.h> using namespace std; //#define FILE #define int long long #define randint(l, r) (rand() % ((r) - (l) + 1) + (l)) #define abs(x) ((x) < 0 ? (-(x)) : (x)) #define popc(x) __builtin_popcount(x) #define inv(x) qpow((x), mod - 2) #define lowbit(x) ((x) & (-(x))) #define ull unsigned long long #define pii pair<int, int> #define LL long long #define mp make_pair #define pb push_back #define scd second #define vec vector #define fst first #define endl '\n' const int MAXN = 50; const int SIZ = 2010; const int INF = 2e9; const double eps = 1e-6; const double PI = acos(-1); const int mod = 1e9 + 7; //const int mod = 998244353; //const int G = 3; //const int base = 131; int n, m, lim; int p[MAXN], _cnt[MAXN], cnt[MAXN]; int cir[MAXN], c, fac[MAXN], cur[MAXN], pre[MAXN]; int C[MAXN][MAXN], F[MAXN][MAXN]; int dp[SIZ]; template<typename T> inline bool read(T &a) { a = 0; char c = getchar(); int f = 1; while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { a = a * 10 + (c ^ 48); c = getchar(); } return a *= f, true; } template<typename A, typename ...B> inline bool read(A &x, B &...y) { return read(x) && read(y...); } void Init() { static bool vis[MAXN]; fac[0] = 1; for(int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % mod; function< int (int, int) > DFS = [&](int x, int siz) { if(vis[x]) return siz; vis[x] = true; return DFS(p[x], siz + 1); }; for(int i = 1; i <= n; ++i) if(!vis[i]) _cnt[DFS(i, 0)]++; for(int i = 1; i <= n; ++i) if(_cnt[i]) { cir[++c] = i; cnt[c] = _cnt[i]; } C[0][0] = 1; for(int i = 1; i <= n; ++i) { C[i][0] = 1; for(int j = 1; j <= i; ++j) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod; } for(int i = 0; i < n; ++i) { F[i][0] = F[i][1] = 1; for(int j = 1; j <= n; ++j) if(j != n - i) (F[i][1] *= j) %= mod; for(int j = 2; j <= n; ++j) F[i][j] = (F[i][j - 1] * F[i][1]) % mod; } for(int i = 1; i <= c; ++i) lim = lim * (cnt[i] + 1) + cnt[i]; } int encode(int *a) { int res = 0; for(int i = 1; i <= c; ++i) res = res * (cnt[i] + 1) + a[i]; return res; } void decode(int a) { for(int i = c; i >= 1; --i) { cur[i] = a % (cnt[i] + 1); a /= (cnt[i] + 1); } } void nxt(int *a) { a[1]++; for(int i = 1; i <= c; ++i) { if(a[i] > cnt[i]) a[i] = 0, a[i + 1]++; else break; } } signed main () { #ifdef FILE freopen("CF1466H.in", "r", stdin); freopen("CF1466H.out", "w", stdout); #endif read(n); for(int i = 1; i <= n; ++i) read(p[i]); Init(); dp[0] = 1; for(int i = 0, j, sumi, sumj, cnti, cntj, coe; i <= lim; ++i) { decode(i); memset(pre, 0, sizeof pre); sumi = cnti = 0; for(int p = 1; p <= c; ++p) cnti += cur[p], sumi += cur[p] * cir[p]; while(1) { j = encode(pre); if(i == j) break; sumj = cntj = 0, coe = 1; for(int p = 1; p <= c; ++p) cntj += pre[p], sumj += pre[p] * cir[p]; for(int p = 1; p <= c; ++p) coe = coe * C[cur[p]][pre[p]] % mod; if(!((cnti - cntj) & 1)) coe = mod - coe; (dp[i] += dp[j] * coe % mod * F[sumj][sumi - sumj]) %= mod; nxt(pre); } } printf("%lld\n", dp[lim]); return 0; }
题目链接：[Ynoi2008] stcm题意：给定一棵树，可以维护一个集合，支持以下操作：当前集合中插入一个节点 $x$。撤回上一次插入操作。将当前点集标为第 $i$ 个点的子树补信息。一个点 $x$ 的子树补信息定义为：树的点集除去 $x$ 的子树（包括 $x$）内的点得到的集合。要求在 $4.5\times 10^6$ 次操作以内，标记所有点的子树补。$1\le T\le 3,1\le n\le 10^5$。操作次数是 $\mathcal{O}(n\log n)$ 级别，先无脑重链剖分一下。根据重链剖分相关结论，可知轻子树大小总和是 $\mathcal{O}(n\log n)$ 的。因此，对于一条重链上的所有节点，我们可以直接暴力加入所有轻子树，这样每一棵轻子树只被加入一次。具体来说，对于一条重链的顶端 $x$，假设当前状态已经是 $x$ 的子树补，则每次可以暴力将 $x$ 的轻儿子遍历一遍，加入所有节点，再加入 $x$，得到 $x$ 的重儿子的子树补。则现在的问题变成了，如何求出每一条重链顶端的子树补。对于一条重链的顶端 $x$，假设当前状态已经是 $x$ 的子树补，当我们进行一些操作之后，当前状态转变为 $x$ 这条重链上某一个节点 $y$ 的某一个轻儿子 $p$ 的子树补，则我们就可以递归处理 $p$ 子树内部的答案了。若要让当前 $x$ 的子树补，转变为 $p$ 的子树补，则 $x$ 这条重链上其他节点的所有轻儿子都要被标记，所需要的操作次数是：$$ \sum_{y\in \text{link}(x)}\sum_{k\in \text{lightson}(y),k\ne p}\text{siz}(k) $$的级别。我们希望这个式子的总和尽量小。考虑把所有轻子树 $k$ 看作一个二元组 $(k,\text{siz}(k))$，重链上的点 $y$ 看作 $(y,1)$。建立这样一个二元组的哈夫曼树，可知一棵权值和为 $s$ 的哈夫曼树，带权子树和是 $\mathcal{O}(s\log s)$ 级别的。于是，可以在哈夫曼树上 $\text{DFS}$，每次要往哈夫曼树的左子树进行处理，就暴力加入右子树内的所有节点；要往右子树走，就加入左子树节点。这样的时间复杂度看起来是 $\mathcal{O}(n\log^2 n)$ 的，但是好像可以通过将每次递归子问题所得到的哈夫曼树拼接起来，最后得到一个 $\mathcal{O}(n\log n)$ 的时间复杂度。//Code By CXY07 #include<bits/stdc++.h> using namespace std; //#define FILE //#define int long long #define file(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout) #define randint(l, r) (rand() % ((r) - (l) + 1) + (l)) #define LINE() cout << "LINE = " << __LINE__ << endl #define debug(x) cout << #x << " = " << x << endl #define abs(x) ((x) < 0 ? (-(x)) : (x)) #define popc(x) __builtin_popcount(x) #define inv(x) qpow((x), mod - 2) #define lowbit(x) ((x) & (-(x))) #define ull unsigned long long #define pii pair<int, int> #define LL long long #define mp make_pair #define pb push_back #define scd second #define vec vector #define fst first #define endl '\n' const int MAXN = 1e5 + 10; const int INF = 2e9; const double eps = 1e-6; const double PI = acos(-1); //const int mod = 1e9 + 7; //const int mod = 998244353; //const int G = 3; //const int base = 131; int T, n, m, cnt, opt_cnt; int fa[MAXN], siz[MAXN], son[MAXN]; int huffman[MAXN * 50][2], hc, id[MAXN * 50]; int type[MAXN * 50]; vec<int> G[MAXN]; priority_queue<pii> Q; template<typename T> inline bool read(T &a) { a = 0; char c = getchar(); int f = 1; while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { a = a * 10 + (c ^ 48); c = getchar(); } return a *= f, true; } template<typename A, typename ...B> inline bool read(A &x, B &...y) { return read(x) && read(y...); } void DFS(int x) { siz[x] = 1; for(auto to : G[x]) { DFS(to), siz[x] += siz[to]; if(!son[x] || siz[son[x]] < siz[to]) son[x] = to; } } void calc(int x); void clear() { hc = opt_cnt = 0; for(int i = 1; i <= n; ++i) G[i].clear(); memset(huffman, 0, sizeof huffman); memset(type, 0, sizeof type); memset(id, 0, sizeof id); memset(son, 0, sizeof son); } void add(int x) { printf("+%d", x); ++cnt; opt_cnt++; } void pop() { putchar('-'); cnt--; opt_cnt++; } void eq(int x) { printf("=%d", x); opt_cnt++; } void roll(int x) { assert(cnt >= x); while(cnt > x) pop(); } void add_son(int x) { add(x); for(auto to : G[x]) add_son(to); } void add_Huffman(int x) { if(!huffman[x][0] || !huffman[x][1]) { if(type[x] == 1) add(id[x]); else add_son(id[x]); return; } add_Huffman(huffman[x][0]), add_Huffman(huffman[x][1]); } void DFS_Huffman(int x) { if(!huffman[x][0] || !huffman[x][1]) { if(type[x] == 2) calc(id[x]); return; } int cur = cnt; add_Huffman(huffman[x][1]); DFS_Huffman(huffman[x][0]); roll(cur); add_Huffman(huffman[x][0]); DFS_Huffman(huffman[x][1]); roll(cur); } void calc(int x) { int cur = cnt, now = x; while(now) { eq(now); Q.push(mp(-1, ++hc)); id[hc] = now, type[hc] = 1; add(now); for(auto to : G[now]) if(to != son[now]) { add_son(to); Q.push(mp(-siz[to], ++hc)); id[hc] = to, type[hc] = 2; } now = son[now]; } roll(cur); while(Q.size() > 1) { pii x, y; x = Q.top(); Q.pop(); y = Q.top(); Q.pop(); Q.push(mp(x.fst + y.fst, ++hc)); huffman[hc][0] = x.scd, huffman[hc][1] = y.scd; } Q.pop(); DFS_Huffman(hc); roll(cur); } void solve() { clear(); for(int i = 2; i <= n; ++i) read(fa[i]), G[fa[i]].pb(i); DFS(1); calc(1); putchar('!'); putchar('\n'); assert(!cnt); } signed main () { #ifdef FILE freopen("P7124.in", "r", stdin); freopen("P7124.out", "w", stdout); #endif while(scanf("%d", &n) != EOF) solve(); return 0; }
题目链接：重返现世题意：有 $n$ 个元素，每次抽取到第 $i$ 个的概率是 $\dfrac{p_i}{m}$，求抽到任意不同 $k$ 个的期望次数。$1\le n\le 1000,1\le m\le 10^4,0\le n-k\le 10,\sum p_i=m$。这题也太神秘了/bx/bx/bx首先考虑 $\text{min-max}$ 容斥，则这个东西是：$$ E(\text{kth-min}(S))=\sum_{T\subseteq S} \binom{|T|-1}{k-1}(-1)^{|T|-k} E(\max(T)) $$回忆一下 $E(\max(T))$ 的求法，这是一个经典的 $\text{min-max}$ 容斥问题，其做法需要把 $\max$ 反演成 $\min$。所以这样仍然是不好做的。但是我们知道，第 $k$ 小 $\iff$ 第 $n-k+1$ 大，所以我们令 $k\leftarrow n-k+1$。这样还有一个好处：当 $k\leftarrow n-k+1$，则 $k\le 11$，用上了题目的条件。于是有：$$ E(\text{kth-max}(S))=\sum_{T\subseteq S} \binom{|T|-1}{k-1}(-1)^{|T|-k} E(\min(T)) $$这时候 $E(\min(T))$ 就是一个经典问题了，这个问题问的是：第一次抽出集合 $T$ 中的元素所需要的期望次数。抽出集合中任意一个元素的概率是 $\dfrac{\sum_{x\in T} p_x}{m}$，所以期望次数就是其倒数 $\dfrac{m}{\sum_{x\in T}p_x}$。因此答案是：$$ E(\text{kth-max}(S))=\sum_{T\subseteq S} \binom{|T|-1}{k-1}(-1)^{|T|-k} \dfrac{m}{\sum_{x\in T}p_x} $$这个 $\sum_{x\in T}p_x$ 在分母上太神秘了，但是我们有 $m\le 10^4$，所以可以枚举这个和！答案变成：$$ =\sum_{s=1}^m \dfrac{m}{s}\sum_{T\subseteq S}\binom{|T|-1}{k-1}(-1)^{|T|-k}\Big[\sum_{x\in T} p_x=s\Big] $$考虑对每一种 $s$，算后面那个系数之和。考虑 $\text{dp}$，设 $\text{dp}_{i,j,x}$ 表示考虑前 $i$ 个元素，$\sum_{x\in T} p_x=j$，$$ \binom{|T|-1}{x-1}(-1)^{|T|-x} $$的和。考虑如何转移，首先如果第 $i$ 个元素不选，则有：$$ \text{dp}_{i,j,x}=\text{dp}_{i-1,j,x} $$如果选择第 $i$ 个元素，则 $j\leftarrow j+p_i$。考虑上面这个系数会怎样变化：$$ \binom{|T|-1}{x-1}(-1)^{|T|-x}=-\binom{|T|-2}{x-1}(-1)^{(|T|-1)-x}+\binom{|T|-2}{x-2}(-1)^{(|T|-1)-(x-1)} $$也就是把杨辉三角拆开，然后把 $-1$ 的系数修正一下。于是有转移：$$ \text{dp}_{i,j,x}=\text{dp}_{i-1,j,x}+\text{dp}_{i-1,j-p_i,x-1}-\text{dp}_{i-1,j-p_i,x} $$直接 $\text{dp}$ 即可做到 $\mathcal{O}(nm\times (n-k))$。空间开不下，记得滚动一下。彩蛋：推式子的时候，大力推了 kth-min 转化为 min 的系数，觉得自己巨大厉害，后来发现这和 kth-max 转变为 min 没有任何区别/tuu//Code By CXY07 #include<bits/stdc++.h> using namespace std; //#define FILE #define int long long #define file(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout) #define randint(l, r) (rand() % ((r) - (l) + 1) + (l)) #define LINE() cout << "LINE = " << __LINE__ << endl #define debug(x) cout << #x << " = " << x << endl #define abs(x) ((x) < 0 ? (-(x)) : (x)) #define popc(x) __builtin_popcount(x) #define inv(x) qpow((x), mod - 2) #define lowbit(x) ((x) & (-(x))) #define ull unsigned long long #define pii pair<int, int> #define LL long long #define mp make_pair #define pb push_back #define scd second #define vec vector #define fst first #define endl '\n' const int MAXN = 1010; const int MAXM = 10010; const int INF = 2e9; const double eps = 1e-6; const double PI = acos(-1); //const int mod = 1e9 + 7; const int mod = 998244353; //const int G = 3; //const int base = 131; int n, k, m, p[MAXN], Ans; int dp[MAXM][12], Inv[MAXM]; template<typename T> inline bool read(T &a) { a = 0; char c = getchar(); int f = 1; while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { a = a * 10 + (c ^ 48); c = getchar(); } return a *= f, true; } template<typename A, typename ...B> inline bool read(A &x, B &...y) { return read(x) && read(y...); } void modadd(int &x, int y) { x += y; if(x >= mod) x -= mod; } signed main () { #ifdef FILE freopen(".in", "r", stdin); freopen(".out", "w", stdout); #endif read(n), read(k), read(m); Inv[1] = 1, k = n - k + 1; for(int i = 1; i <= n; ++i) read(p[i]); for(int i = 2; i <= m; ++i) Inv[i] = Inv[mod % i] * (mod - mod / i) % mod; dp[0][0] = 1; for(int i = 1; i <= n; ++i) for(int j = m; j >= p[i]; --j) for(int c = k; c; --c) (dp[j][c] += dp[j - p[i]][c - 1] - dp[j - p[i]][c] + mod) %= mod; for(int p = 1; p <= m; ++p) Ans = (Ans + dp[p][k] * m % mod * Inv[p]) % mod; printf("%lld\n", Ans); return 0; }