platelet's blog

题目链接

给定 \(n,m\)，保证 \(m \le n\)，设 \(f(a,b)=\sum\limits_{i=0}^b\binom bi\binom {n-i}a\)。

求 \(\bigoplus\limits_{a=1}^m\bigoplus\limits_{b=1}^m\left(f(a,b) \bmod 998244353\right)\)。

\(n \le 10^9,m \le 5000\)

引理

\[ \sum_{a=0}^n f(a,b)x^a=(x+2)^b(x+1)^{n-b} \]

证明一：

\[ \begin{aligned} &\sum_{a=0}^n f(a,b)x^a\\\\ &=\sum_{a=0}^n\sum\limits_{i=0}^b\binom bi\binom {n-i}ax^a\\\\ &=\sum_{i=0}^b\binom bi\sum_{a=0}^n\binom {n-i}ax^a\\\\ &=\sum_{i=0}^b\binom bi(x+1)^{n-i}\\\\ &=\sum_{i=0}^b\binom bi(x+1)^{b-i}(x+1)^{n-b}\\\\ &=(x+2)^b(x+1)^{n-b} \end{aligned} \]

证明二

考虑 \(f(a,b)\) 的组合意义：有 \(n\) 个人，其中 \(b\) 个人比较强，要选出两批人：

• 先从比较强的 \(b\) 个人中选出 \(i\) 个人作为第一批。
• 再从剩下的 \(n-i\) 个人中选出 \(a\) 个人作为第二批。

因为要对 \(i \in [0,b]\) 求和，所以 \(f(a,b)\) 表示第一批的人数任意，第二批的人数为 \(a\) 的方案数。

换一个角度看这个方案数：设第二批的 \(a\) 个人中有 \(x\) 个人比较强，\(y\) 个人不强（\(a=x+y\)）。

题目链接

给定一个长度为 \(n\) 的序列 \(A\)，定义 \(f(l,r)\) 表示从区间 \([l,r]\) 中选择若干不相邻的数的和的最大值。

求 \(\sum\limits_{l=1}^n\sum\limits_{r=l}^nf(l,r) \bmod 10^9 + 7\)。

\(n \le 10^5,0 \le a_i \le 10^9\)

\(f(l,r)\) 显然可以通过 DP 在 \(O(r-l+1)\) 的时间内求出，枚举左端点或右端点来计算答案都不太行得通，因为端点移动一步后难以快速维护。

但所有包含同一位置 \(p\) 的区间（\(p\) 是端点不算）的 \(f\) 值之和却可以快速计算，因为枚举了 \(p\) 选不选后，\(p\) 左右的部分是独立的。

对于一个包含 \(p\) 的区间 \([l,r]\)，有 \[ f(l,r)=\max\{f(l,p-1)+f(p+1,r),f(l,p-2)+f(p+2,r)+A_p\} \] 设 \[ x_i=\begin{cases}f(i,p-1)&(i < p)\\\\f(p+1,i)&(i>p)\\\\0&(i=p)\end{cases},y_i=\begin{cases}f(i,p-2)&(i<p-1)\\\\f(p+2,i)&(i>p+1)\\\\0&(p-1 \le i \le p+1)\end{cases} \] \(x,y\) 数组可以通过 DP 在 \(O(n)\) 的时间内求出。 \[ f(l,r)=\max\{x_l+x_r,y_l+y_r+A_p\}\\\\ x_l+x_r \ge y_l + y_r + A_p \iff (x_l - y_l) + (x_r - y_r) \ge A_p \] 把所有除 \(p\) 以外的位置按 \(x_i-y_i\) 为关键字升序排序，再用双指针扫描一遍即可求出所有包含 \(p\) （\(p\) 是端点不算）的 \(f\) 值之和，单次的复杂度为 \(O(n\log n)\)。

接下来就是套路了，考虑分治，定义函数 \(solve(L,R)\) 表示 \(\sum\limits_{l=L}^R\sum\limits_{r=l}^Rf(l,r)\)。

令 \(mid = \lfloor \frac {L + R}2 \rfloor\)，那么 \(solve(L, R) = solve(L, mid) + solve(mid, R) - A_{mid} + \sum\limits_{l=L}^{mid-1}\sum\limits_{r=mid+1}^Rf(l,r)\)。

最后一项用上述方法计算，总复杂度为 \(O(n \log^2 n)\)。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)
#define pb push_back

using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
const ll P = 1e9 + 7, Inf = 1e18;
int n; ll a[N], f[N][2][2], A[N], B[N], as;
void solve(int l, int r) {
    if(l == r) { (as += a[l]) %= P; return; }
    if(r == l + 1) { (as += a[l] + a[r] + max(a[l], a[r])) %= P; return; }
    int mid = (l + r) / 2;
    rep(i, 0, 1) f[mid][i][i] = 0, f[mid][i][!i] = -Inf;
    rep(i, mid + 1, r) rep(j, 0, 1) {
        f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1]);
        f[i][j][1] = f[i - 1][j][0] + a[i];
    }
    per(i, mid - 1, l) rep(j, 0, 1) {
        f[i][j][0] = max(f[i + 1][j][0], f[i + 1][j][1]);
        f[i][j][1] = f[i + 1][j][0] + a[i];
    }
    vector <int> v;
    rep(i, l, r) if(i ^ mid) {
        v.pb(i);
        A[i] = max(f[i][0][0], f[i][0][1]);
        B[i] = max(f[i][1][0], f[i][1][1]);
    }
    sort(v.begin(), v.end(), [](int i, int j){ return A[i] - B[i] < A[j] - B[j]; });
    int j = v.size() - 1;
    ll sua = 0, sub = 0; int cna = 0, cnb = 0;
    for(int i : v) if(i > mid) (sub += B[i]) %= P, cnb++;
    for(int i : v) if(i < mid) {
        while(j >= 0 && (v[j] < mid || A[i] - B[i] + A[v[j]] - B[v[j]] > a[mid])) {
            if(v[j] > mid) (sua += A[v[j]]) %= P, (sub -= B[v[j]]) %= P, cna++, cnb--;
            j--;
        }
        (as += (a[mid] + B[i]) * cnb + A[i] * cna + sua + sub) %= P;
    }
    (as -= a[mid]) %= P, solve(l, mid), solve(mid, r);
}
int main() {
    cin >> n;
    rep(i, 1, n) scanf("%lld", &a[i]);
    solve(1, n);
    cout << (as + P) % P;
    return 0;
}

题目链接

一张有 \(n\) 个点的图，每个点的点权为 \(a_i\)。

点 \(u\) 和点 \(v\) 连边当且仅当 \(a_u \& a_v = 0\)。

对于点 \(u\)，有两种操作：

• 直接涂黑，无贡献。
• 找一个与 \(u\) 相邻且已经涂黑的点 \(v\)，再涂黑 \(u\)，贡献为 \(a_v\)。

求涂黑所有点的最大贡献。

\(n \le 2 \cdot 10^5,a_i \le 2 \cdot 10^5\)

首先加入一个点权为 \(0\) 的虚点，且初始为黑，则两种操作就可以统一成第二种。

对于每次操作，就从 \(u\) 向 \(v\) 连一条有向边，得到一个以 \(0\) 为根的有根树。

设点 \(u\) 的度数为 \(degree_u\)，则总贡献可以表示为 \[ \sum_{u \in V}a_u(degree_u-1)=\sum_{u \in V}a_udegree_u-\sum_{u \in V}a_u = \sum_{(u,v) \in E}a_u + a_v - \sum_{u \in V}a_u \] 如果定义 \((u,v)\) 边权为 \(a_u + a_v\)，则前一部分为生成树权值，后一部分是定值。

所以问题转化为求最大生成树。

先考虑所有点的点权两两不同。

根据枚举子集的经典结论，边的总数小于 \(3^{18}\)，但实际只有一半左右，即 \(1.7 \cdot 10^8\) 左右。

考虑 Kruskal 算法，虽然并查集复杂度要乘一个 \(\alpha(n)\)，但感觉卡不满。

首先不可能存下所有边，更不可能排序，所以考虑从大到小枚举边权。

注意到 \(u,v\) 连边当且仅当 \(a_u \& a_v = 0\)，而边权为 \(a_u + a_v\)。

题目链接

给定一张 \(n\) 个点 \(m\) 条边的简单无向图。

问在图中能否找到两个点，满足这两个点之间有至少三条点不相交的简单路径，有解要打印三条路径。

\(n,m \le 2 \cdot 10^5\) 不保证图连通。

考虑 \(u \rightarrow v\) 有三条点不相交的路径会是什么样子，发现有两个环相交了。

反过来，如果任意两个环都不相交，即仙人掌，那就无解。

至此，得到了有解的充要条件：不是仙人掌。

但为了便于打印路径，采用另一种方法。

设 \(low_u\) 为 tarjan 算法中的定义，\(Low_u\) 表示次小值。

如果 \(Low_u = dfn_u\)，则子树内的一个点到子树外的一个点至多有两条点不相交的简单路径。

于是存在满足 \(Low_u < dfn_u\) 的点 \(u\) 是有解的必要条件。

观察这张图，如果 \(lca(v,V)=u\)，那么 \(u \rightarrow Low\)，\(u \rightarrow v \rightarrow low \rightarrow Low\) 和 \(u \rightarrow V \rightarrow Low\) 是三条点不相交的简单路径。

题目链接

给定一张 \(n\) 个点 \(m\) 条边的无向图和 \(q\) 组有序点对 \((s_i,t_i)\)。

询问是否可以给每条边定向，使得所有的 \(s_i\) 都能到达 \(t_i\)。

\(n,m,q \le 2 \cdot 10^5\) 不保证图连通，可能有重边。

先假设有解，尝试求出一组解，再判定这组解合不合法。

构造解

一个经典结论：

一个边双连通分量存在一种给每条边定向的方案，使之成为强连通分量。

一个强连通分量把有向边变成无向边后成为边双连通分量。

对于前者直接让树边向下，反向边向上即可。

对于后者考虑一条有向边的两个端点可以相互到达，推出这条边在一个简单环上。

把图中的边双全部定向成强连通分量，接下来只需要给所有桥定向，以使 \(s_i\) 所在的边双能到达 \(t_i\) 所在的边双。

其实无需求边双，只需求出哪些边是桥即可，由于此题有重边，tarjan 算法应当记录上一条边而不是父亲。

建出 dfs 树，对于每组 \((s_i,t_i)\)，要求 \(s_i\) 到 \(t_i\) 路径上的桥由 \(s_i\) 指向 \(t_i\)。

题目链接

给定一棵 \(n\) 个点的树和 \(k\)，每个结点上有 \(a_i\) 个物品，Alice 和 Bob 在上面玩游戏。

在确定根之后，两个玩家轮流选择任意一个存在 \(k\) 级祖先的结点 \(u\)，然后把 \(u\) 的任意个物品移到 \(u\) 的 \(k\) 级祖先上。

最后没有物品可取的人输。

问当每个结点作为根时，谁必胜。

\(n \le 10^5, k \le 20,a_i \le 10^9\)

当 \(k=1\) 时，它几乎是一个阶梯 NIM 游戏。

设根结点深度为 \(0\)，根据阶梯 NIM 游戏的结论，原问题等价于所有深度为奇数的结点做 NIM 游戏，即先手必胜当且仅当所有深度为奇数的结点的 \(a_i\) 异或和不为 \(0\)。

对于一般的情况，先手必胜当且仅当 \[ \bigoplus_{\big\lfloor \frac {depth_u}k \big\rfloor 为奇数}a_u \ne 0 \] 设 \(f_{u,i}\) 表示以 \(u\) 为根的子树里，所有满足 \(depth_v - depth_u \equiv i \pmod {2k}\) 的结点 \(v\) 的点权异或和。

然后换根 DP 一下即可。

复杂度 \(O(nk)\)。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)

using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int n, K, a[N];
ll f[N][40], ans[N];
vector <int> G[N];
void add(int u, int v) {
    For(i, 0, K) f[u][(i + 1) % K] ^= f[v][i];
}
void dfs(int u, int fa) {
    f[u][0] = a[u];
    for(int v : G[u]) if(v ^ fa) dfs(v, u), add(u, v);
}
void Dfs(int u, int fa) {
    For(i, K / 2, K) ans[u] ^= f[u][i];
    for(int v : G[u]) if(v ^ fa) add(u, v), add(v, u), Dfs(v, u), add(v, u), add(u, v);
}
int main() {
    cin >> n >> K, K *= 2;
    int u, v;
    rep(i, 2, n) {
        scanf("%d%d", &u, &v);
        G[u].push_back(v), G[v].push_back(u);
    }
    rep(i, 1, n) scanf("%d", &a[i]);
    dfs(1, 0), Dfs(1, 0);
    rep(i, 1, n) printf("%d ", ans[i] != 0);
    return 0;
}

定义必胜状态为当前局面先手必胜的状态，必败状态为当前局面先手必败的状态。

有向图游戏

在一个有向无环图中，只有一个起点，上面有一个棋子，两个玩家轮流沿着有向边推动棋子，不能走的玩家判负。

对于点 \(u\) 和它的 \(k\) 个后继点 \(v_1,v_2,\cdots,v_k\)，定义 SG 函数： \[ SG(u)=\text{mex}\{SG(v_1),SG(v_2),\cdots,SG(v_k)\} \] 特别地，当 \(u\) 没有后继状态时 \(SG(u)=0\)。

显然，先手必胜当且仅当 \(SG(u) \ne 0\)。

对于 \(n\) 个有向图游戏组合而成的游戏，即两个玩家轮流推动 \(n\) 个棋子之一，设这个游戏的初始状态为 \(S\)，棋子的起点分别为 \(s_1,s_2,\cdots,s_n\)，则有 SG 定理：

\(SG(S) = SG(s_1) \oplus SG(s_2) \oplus \cdots \oplus SG(s_n)\)。

证明：由于组合而成的游戏也是有向图游戏，因此所有的状态存在一个拓扑序，以下使用数学归纳法证明：

• 归纳奠基：对于没有后继的状态 \(S\)，\(\forall i \in [1,n], SG(s_i)=0, SG(S)=0\)，命题成立。

• 归纳假设：设当前状态 \(S\) 满足 \(SG(s_1) + SG(s_2) + \cdots + SG(s_n) = m\)，对于所有满足 \(SG(s_1') + SG(s_2') + \cdots + SG(s_n') < m\) 的状态以及所有满足 \(SG(s_1') + SG(s_2') + \cdots + SG(s_n') = m\) 并且拓扑序小于 \(S\) 的状态命题成立。

• 归纳递推：设 \(SG(s_1) \oplus SG(s_2) \oplus \cdots \oplus SG(s_n) =k\)。

  先证明 \(\forall k' < k\), \(S\) 都存在一个后继状态 \(S'\) 满足 \(SG(S')=k'\)。

  设 \(k \oplus k'\) 在二进制下的最高位为第 \(m\) 位，因为 \(k' < k\), 所以 \(k'\) 的第 \(m\) 位为 \(0\)，\(k\) 的第 \(m\) 位为 \(1\)。

  根据异或定义，存在 \(i\) 满足 \(SG(s_i)\) 的第 \(m\) 位为 \(1\)。

  那么 \(SG(s_i) \oplus k \oplus k' < SG(s_i)\)，根据 SG 函数定义，\(s_i\) 一定存在后继点 \(s_i'\)，满足 \(SG(s_i') = SG(s_i) \oplus k \oplus k'\)。

  把 \(s_i\) 推到 \(s_i'\) 后满足 \(SG(s_1) + SG(s_2) + \cdots + SG(s_i') + \cdots + SG(s_n) < m\)，因此 \(SG(S')=SG(s_1) \oplus SG(s_2) \oplus \cdots \oplus SG(s_i') \oplus \cdots \oplus SG(s_n)=k'\)。

  再证明 \(S\) 不存在后继状态 \(S'\) 满足 \(SG(S')=k\)。

  如果把 \(s_i\) 推到 \(s_i'\)，一定 \(SG(s_i') \ne SG(s_i)\)。

  如果 \(SG(s_i') < SG(s_i)\)，那么 \(SG(s_1) + SG(s_2) + \cdots + SG(s_i') + \cdots + SG(s_n) < m\)，因此 \(SG(S')=SG(s_1) \oplus SG(s_2) \oplus \cdots \oplus SG(s_i') \oplus \cdots \oplus SG(s_n) \ne k\)。

  如果 \(SG(s_i') > SG(s_i)\)，那么 \(SG(s_1) + SG(s_2) + \cdots + SG(s_i') + \cdots + SG(s_n) > m\)，因此 \(SG(S')\) 未知，但我们只需证 \(SG(S') \ne k\)。根据 SG 函数定义，\(s_i'\) 一定存在后继点 \(s_i''\)，满足 \(SG(s_i'') = SG(s_i)\)，此时 \(SG(s_1) + SG(s_2) + \cdots + SG(s_i'') + \cdots + SG(s_n) = m\)，并且 \(S''\) 的拓扑序小于 \(S\)，因此 \(SG(S'')=SG(s_1) \oplus SG(s_2) \oplus \cdots \oplus SG(s_i'') \oplus \cdots \oplus SG(s_n)=k\)，所以一定有 \(SG(S') \ne k\)。

NIM 游戏

题目链接

有一张 \(n\) 个点的竞赛图。

不会给这张竞赛图，但会给每个点的入度 \(k_i\)。

还可以通过交互询问从 \(u\) 能否到达 \(v\)，但一旦回答了”是“，就不能再询问了。

定义一个点对 \((u,v)\) 的价值是 \(|k_u-k_v|\)。

求所有双向可达的点对中价值最大的一对，或者输出无解。如果有多对，输出任意一对。

\(n \le 500\)

做法一

考虑一对点 \((u,v)\)，由于是竞赛图，\(u,v\) 间有连边，不妨设 \(u \rightarrow v\)。

如果 \(v\) 不能到达 \(u\)，\(\exists S,u \in S \land \forall x \in S, y \not \in S,x \rightarrow y\)，即集合 \(S\) 内的点全部向 \(S\) 外的点连边。

\(\therefore k_v \ge |S|,k_u < |S| \Rightarrow k_u < k_v\)

得到一个结论：如果一对点不双向可达，那么入度大的一定无法到达入度小的。

把所有点对按价值从大到小依次询问，每次询问入度大的能否到达入度小的，如果可以，就直接输出这一对。

如果到最后都没有回答“是”，那么输出无解。

复杂度 \(O(n^2)\)。

代码：

题目链接

有一个变量 \(k\) 初始为 \(0\)。

对于时刻 \(i=1,2,3,\cdots,n\)，给定 \(t_i,x_i,y_i\)，且执行以下操作：

• 若 \(t_i=1\)，选择 \(a \in [0,y_i]\)，执行 \(a\) 次 \(k=\lceil k + x_i \rceil\)。
• 若 \(t_i=2\)，选择 \(a \in [0,y_i]\)，执行 \(a\) 次 \(k=\lceil k \cdot x_i \rceil\)。

其中 \(x_i\) 是实数。

对于每个 \(j \in [1,m]\)，求可能的最小时刻使得 \(k=j\)。

\(n \le 200,y_i \le m \le 10^5\)

对于 \(t_i=1\)，有 \(0 < x_i \le m\)，对于 \(t_i=2\)，有 \(1 < x_i \le m\)。

对于每个时刻 \(i\)，维护数组 \(ok_j\) 表示经过前 \(i\) 个时刻能否使 \(k=j\)。

设 \(next_j=\begin{cases}\lceil j + x_i \rceil&(t_i=1)\\\\\lceil j \cdot x_i \rceil&(t_i=2)\end{cases}\)。

因为 \(\forall j \ne k,next_j \ne next_k\)，所以 \(j \rightarrow next_j\) 连边后形成若干条链。

假设一条链上的结点分别为 \(v_1,v_2,v_3,\cdots,v_s\)

对于 \(v_j\)，如果 \(\exist k \in [j-y_i,j)\)，满足 \(ok_k=1\)，那么在第 \(i\) 时刻 \(k\) 可以等于 \(v_j\)。

对每条链扫描一遍即可求出在第 \(i\) 时刻 \(k\) 可以等于哪些值。

复杂度 \(O(nm)\)。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)
#define upd(a, b) (a = min(a, b))

using namespace std;
typedef long long ll;
const int N = 1e5, M = N + 5;
int n, m, f[M], nxt[M], vis[M], ok[M];
int main() {
    mem(f, -1);
    int t, y; ll x;
    cin >> n >> m;
    f[0] = 0;
    rep(k, 1, n) {
        scanf("%d%lld%d", &t, &x, &y);
        if(t == 1) {
            x = (x + N - 1) / N;
            rep(i, 0, m) nxt[i] = min(i + x, m + 1ll);
        } else {
            nxt[0] = m + 1;
            rep(i, 1, m) nxt[i] = min((i * x + N - 1) / N, m + 1ll);
        }
        mem(vis, 0);
        rep(i, 0, m) if(!vis[i]) {
            vector <int> v;
            for(int j = i; j <= m; j = nxt[j]) vis[j] = 1, v.push_back(j);
            int cnt = 0;
            For(j, 0, v.size()) {
                if(cnt) ok[v[j]] = 1;
                cnt += f[v[j]] != -1;
                if(j >= y) cnt -= f[v[j - y]] != -1;
            }
        }
        rep(i, 0, m) if(!~f[i] && ok[i]) f[i] = k;
    }
    rep(i, 1, m) printf("%d ", f[i]);
    return 0;
}

题目链接

定义 \(S(x)\) 表示把 \(x\) 各数位上的数排序后得到的新数，\(S(353594)=334559\)。

给定 \(n\)，求 \(\sum\limits_{i=1}^nS(i) \bmod 10^9+7\)。

\(n \le 10^{700}\)

设 \(n\) 总共 \(m\) 位，\(h_{x,i}\) 表示 \(x\) 有多少个数位上的数大于等于 \(i\)。