P4071 – SDOI2016 – D2T1 – 排列计数
题目信息
难度：提高+/省选-
算法：数学递推、逆元
题目描述
求有多少种 $1$ 到 $n$ 的排列 $a$，满足序列恰好有 $m$ 个位置 $i$，使得 $a_i=i$.
答案对 $10^9+7$ 取模，多组询问，询问次数为 $T$.
| 测试点编号 | $T=$ | $n, m\leq$ | 测试点编号 | $T=$ | $n, m\leq$ |
|---|---|---|---|---|---|
| $1 \sim 3$ | $10^3$ | $8$ | $10 \sim 12$ | $10^3$ | $10^3$ |
| $4 \sim 6$ | $10^3$ | $12$ | $13 \sim 14$ | $5\times 10^5$ | $10^3$ |
| $7 \sim 9$ | $10^3$ | $100$ | $15 \sim 20$ | $5\times 10^5$ | $10^6$ |
对于 $100\%$ 的数据，$0\leq m\leq 10^6$.
$\rm{Subtask}$ $\rm{1}$
$T=10^3$，$n, m\leq 8$.
对于每次询问，暴力枚举所有排列，时间复杂度 $\mathcal{O}(T\times n!)$，期望得分 $\rm{15pts}$.
$\rm{Subtask}$ $\rm{2}$
想到错排之后，正解非常自然。
根据小学排列组合知识，我们从数列中任意取 $n$ 个数，让它们满足 $a_i=i$，情况数为 $C_{n}^{m}$.
又因为 $n$ 个数的排列中，有 $m$ 个位置满足 $a_i=i$，对于剩下的 $n-m$ 个位置需要满足 $a_i\neq i$.
这样的情况数是 $n-m$ 的错排数，也就是 $D_{n-m}$.
由于乘法原理，最终的答案就是 $C_{n}^m\times D_{n-m}$.
对于多组询问，我们需要 $\mathcal{O}(n)$ 预处理组合数和错排数。
错排
概念
对于一个 $n$ 个元素的排列，若一个排列中所有的元素都不在自己的位置上，这样的一个排列称为一个错排。
一般将 $n$ 个元素的错排数量记作 $D_n$.
通过递推，可以在 $\mathcal{O}(n)$ 的复杂度内处理出 $D_1,D_2\cdots, D_n$.
递推式
推导过程不唯一。
第一步，在 $[1, n-1]$ 中任取一个元素 $i$，将 $n$ 连向 $i$，方法数量为 $(n-1)$.
第二步，确定 $i$ 连向哪个元素，分类讨论：
- $i$ 连向 $n$.此时剩下的 $n-2$ 个元素要满足错排，对答案贡献为 $(n-1)\times D_{n-2}$.
- $i$ 不连向 $n$.此时，相当于有 $n-1$ 个元素需要满足错排，对答案贡献为 $(n-1)\times D_{n-1}$.根据加法原理，得到递推式：
\begin{align}
D_{n}=(n-1)\times(D_{n-1}+D_{n-2})\tag{n>2}
\end{align}
$$
特殊地，$D_1=0$，$D_2=1$.
求逆元 & 组合数
扩展欧几里得
概述
扩展欧几里得算法是用来在已知 $a,b$ 的情况下求解一组 $x,y$，使满足 $ax+by=gcd(a,\,b)=d$.
$\gcd(a, b)$ 为 $a, b$ 的最大公因数，方程一定有整数解。
特解
要计算 $\gcd(a,\,b)$，并求出满足条件的 $x,y$.
将下一个状态 $b$ 和 $(a\%b)$ 表示为：$b\cdot x_1+(a\%b)\cdot y_1=d$
则：
\begin{align}
\because b\cdot x_1+(a\%b)\cdot y_1=d,\\
\text{又}\because a\%b=a-\left\lfloor\frac{a}{b}\right\rfloor\times b\\
\end{align}
$$
\begin{aligned}\therefore gcd(a,\,b)=d&=b\cdot x_1+(a-\left\lfloor\frac{a}{b}\right\rfloor\times b)\cdot y_1\\
&=b\cdot x_1+a\cdot y_1-\left\lfloor\frac{a}{b}\right\rfloor\times b\times y_1\\
&=a\times y1+b\times(x_1-\left\lfloor\frac{a}{b}\right\rfloor\times y_1)
\end{aligned}
$$
所以满足条件的 $x=y_1,\,y=x_1-\left\lfloor\frac{a}{b}\right\rfloor\times y_1$.
int exgcd(int a, int b, int &x, int &y) {//函数返回值为gcd(a,b)
if(b == 0) {
x = 1;//gcd(a,b) = a = 1a+0b
y = 0;
return a;
}
int r = exgcd(b, a % b, x, y);//先递归
int t = x;//再计算x,y
x = y;
y = t - a / b * y;
return r;
}
时间复杂度为：$\mathcal{O}(\min(\log a, \log b))$，即 $\mathcal{O}(\log n)$ 级别。
通解
假设特解为 $(x_0,y_0)$，满足 $ax_0+by_0=gcd(a,\,b)=d$，
则有：
a(x_0+k\frac{b}{d})+b(y_0-k\frac{a}{d})=d\tag{k为整数}
$$
所以方程的通解为：
x=x_0+k\frac{b}{d}\\y=y_0-k\frac{a}{d}
$$
对于其它二元一次不定方程$ax+by=c$（$c$为任意正整数）只有当 $d\mid c$ 时才有整数解，通解形式：
x=\frac{c}{d}x_0+k\frac{b}{d}\\y=\frac{c}{d}y_0-k\frac{a}{d}
$$
同余方程（模方程）
概述
指形如 $ax\equiv b\pmod c$ 的一种方程。其中 $a,b,c$ 是参数，$a,c$ 是正整数，$b$ 是小于 $c$ 的非负整数，$ x$ 是未知数。
解同余方程
根据同余定义，$ax\equiv b\pmod c$ 可化为 $xa+kc=b$. 其中 $a,b,c$ 已知，$x,k$ 未知，所以能用扩展欧几里得解同余方程。
通解
如果 $b\nmid gcd(a,c)$，方程无整数解.
否则同扩展欧几里得酸法，求得通解：
x=\frac{b}{d}x_0+k\frac{c}{d}\\k=\frac{b}{d}p_0-k\frac{a}{d}
$$
其中 $k\in \Bbb{Z}$.
最小非负整数解
因为 $x=\frac{b}{d}x_0+k\frac{c}{d}$，其中 $x_0$ 是方程 $xa+kc=gcd(a,\,c)$ 的特解， $\frac{b}{d}x_0$ 是原同余方程的特解，
若 $x>0$，则有 $x\equiv \frac{b}{d}x_0 \pmod{ \frac{c}{d}} $。最小非负整数解为 $\frac{b}{d}x_0\,\%\,\frac{c}{d}$.
若 $x<0$，同理，最小非负整数解为 $(\frac{b}{d}x_0\bmod \frac{c}{d}+\frac{c}{d} )\bmod\frac{c}{d}$.
综上，最小非负整数解为：
x=(\frac{b}{d}x_0\bmod\frac{c}{d}+\frac{c}{d})\bmod \frac{c}{d}
$$
乘法逆元
概述
给定两个整数 $a$ 和 $p$，假设存在 $x$ 使得 $ax\equiv 1\pmod p)$，称 $x$ 为 $a$ 关于 $p$ 的乘法逆元。
$a$ 关于 $p$ 的逆元存在的充分必要条件是 $\gcd(a,p)=1$.
在模意义下，乘一个数 $x$ 的逆元，可以理解为除以 $x$.
求一个数的逆元
将上面式子变形，变成 $ax+kp=1$，用扩展欧几里得能够求出一个 $x$.
如果 $p$ 是质数，有另一种方法求 $a$ 关于 $p$ 的逆元（费马小定理）
a^{p-1}\bmod p=(a^{p-2}\times a)\bmod p=(x\times a)\bmod p=1
$$
所以 $a$ 关于 $p$ 的逆元是 $a^{b-2}\bmod b$ 的值，用快速幂优化。
时间复杂度：均为 $\mathcal{O}(\log n)$ 级别。
线性预处理逆元
在 $\mathcal{O}(n)$ 的时间复杂度内，求出任意 $n$ 个数的逆元，一般用于处理 $1\sim n$ 的逆元。
设我们要处理出 $a_1, a_2\cdots, a_n$ 的逆元。
第一步，预处理出前缀积数组 $\operatorname{pre}_i=\prod_{j=1}^ia_i$.
第二步，求出 $\operatorname{pre}_n$ 的逆元 $\operatorname{pre\_inv}_n$，复杂度 $\mathcal{O}(\log n)$.
第三步，通过 $\operatorname{pre\_inv}_i$，求出 $\operatorname{pre\_inv}_{i-1}$.
在模意义下，$\operatorname{pre\_inv}_i=\frac{1}{a_1\times a_{2}\times \cdots \times a_{i}}$，$\operatorname{pre\_inv}_{i-1}=\frac{1}{a_1\times a_2\times\cdots\times a_{i-1}}=\operatorname{pre\_inv}_{i}\times a_i$.
第四步，通过 $\operatorname{pre\_inv}_i$，求出 $\operatorname{inv}_i$.
在模意义下，$\operatorname{inv}_i=\operatorname{pre}_{i-1}\times \operatorname{pre\_inv}_{i}$.
在上面的步骤中，$\operatorname{pre\_inv}_i$ 即为 $i$ 的阶乘的逆元，在处理组合数时常用。
有另一种方法也可以处理逆元，时间复杂度相同，但不好记，而且证明麻烦，不需要掌握。
inv[1] = 1;
for (int i = 2; i <= n; ++i) {
inv[i] = (p - p / i) * inv[p % i] % p;
}
预处理组合数
预处理后，$\mathcal{O}(1)$ 地求解 $[1, n]$ 范围内的组合数，对大质数取模的结果。
记 $\operatorname{fac}_n=n!$，根据组合数的定义式：
C_n^m=\frac{n!}{m!(n-m)!}=\frac{\operatorname{fac}_n}{\operatorname{fac}_m\times \operatorname{fac}_{n-m}}
$$
可以得到：
C_n^m \bmod p = \operatorname{fac}_n (\operatorname{fac}_m)^{-1}(\operatorname{fac}_{n-m})^{-1}
$$
所以预处理出 $[1, n]$ 的阶乘，以及阶乘的逆元，每次即可 $\mathcal{O}(1)$ 求组合数。
int fac[], inv_fac[];
fac[0] = 1;
for(int i = 1; i <= n; i++)
fac[i] = fac[i - 1] * i % p;
inv_fac[n] = power(fac[n], p - 1);
for(int i = n - 1; i >= 0; i--)
inv_fac[i] = inv_fac[i + 1] * (i + 1) % p;
P4343 – SHOI2015 – 自动刷题机
题目信息
难度：提高+/省选-
算法：二分答案
题目描述
每秒，自动刷题机的代码生成模块会有两种可能的结果：
- 写了 $x$ 行代码
- 删除之前写的 $y$ 行代码。（如果 $y$ 大于当前代码长度则相当于全部删除。）
对于一个 OJ，每道题都需要且仅需要 $n$ 行代码。一旦在某秒结束时，其积累了大于等于 $n$ 行的代码，刷题机会在瞬间提交代码并新建一个文件。
题目给定 $l$ 关于写代码的日志信息，每条日志信息包含一个正整数 $x_i$，表示第 $i$ 秒时添加的代码行数。若 $x$ 为负数，则代表删除了代码。
自动刷题机一共切了 $k$ 道题，希望你计算 $n$ 可能的最小值和最大值。
$1\leq l\leq 10^5, -10^9\leq x_i\leq 10^9$.
题解
二分。
int check(int x) {
int sum1 = 0, sum2 = 0;
for(int i = 1; i <= n; i++) {
if(a[i] > 0) sum1 += a[i];
else if(sum1 + a[i] < 0) sum1 = 0;
else sum1 += a[i];
if(sum1 >= x) {
sum1 = 0; sum2++;
}
}
return sum2;
}
P4092 – HEOI2016/TJOI2016 – 树
题目信息
难度：提高+/省选-
算法：DFS序、线段树
题目描述
给定一颗有根树，根为 $1$ ，有以下两种操作：
- 标记操作：对某个结点打上标记。（在最开始，只有结点 $1$ 有标记，其他结点均无标记，而且对于某个结点，可以打多次标记。）
- 询问操作：询问某个结点最近的一个打了标记的祖先。（这个结点本身也算自己的祖先）
$1\leq n\leq 10^5, 1\leq q\leq 10^5$.
题解
预处理这棵树的DFS序，所有点权值初始为 $0$.
对 $x$ 点操作时，将 $x$ 点的权值赋为 $\operatorname{dfn}_{x}$
对 $x$ 点询问时，答案就是根结点 $1$ 到 $x$ 的路径上的最大值。
这个可以树剖+线段树维护，也可以只用线段树维护。
线段树做法
用线段树维护区间最大值。
由于子树内的所有节点 dfs 序相邻，每次操作时，在线段树区间修改 $x$ 的子树，取最大值即可。
每次询问时，在线段树上查询 $x$ 点在线段树上的权值即可。
#include <bits/stdc++.h>
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
using namespace std;
const int MAXN = 1e5 + 10;
inline int read() {
int ret = 0; char ch = getchar();
while(ch < '0' || ch > '9') ch = getchar();
while(ch <= '9' && ch >= '0') {
ret = ret * 10 + ch - '0';
ch = getchar();
}
return ret;
}
int n, q;
struct Edge{
int to, nxt;
}edge[MAXN << 1];
int head[MAXN], e_cnt = 0;
void add(int u, int v) {
edge[++e_cnt].to = v;
edge[e_cnt].nxt = head[u];
head[u] = e_cnt;
}
int fa[MAXN], siz[MAXN], son[MAXN], dfn[MAXN], rk[MAXN], top[MAXN], tot = 0;
void dfs1(int x, int father) {
fa[x] = father;
siz[x] = 1;
for(int i = head[x]; i; i = edge[i].nxt) {
int ne = edge[i].to; if(ne == father) continue;
dfs1(ne, x);
if(siz[ne] > siz[son[x]]) son[x] = ne;
siz[x] += siz[ne];
}
}
void dfs2(int x, int topf) {
dfn[x] = ++tot; rk[tot] = x; top[x] = topf;
if(!son[x]) return;
dfs2(son[x], topf);
for(int i = head[x]; i; i = edge[i].nxt) {
int ne = edge[i].to;
if(ne == fa[x]) continue;
if(ne == son[x]) continue;
dfs2(ne, ne);
}
}
int c[MAXN << 2], lazy[MAXN << 2];
inline void push_up(int rt) {
c[rt] = max(c[ls(rt)], c[rs(rt)]);
}
inline void build(int rt, int l, int r) {
c[rt] = -1; lazy[rt] = -1;
if(l == r) return;
int mid = (l + r) >> 1;
build(ls(rt), l, mid);
build(rs(rt), mid + 1, r);
push_up(rt);
}
void push_down(int rt, int l, int r) {
if(lazy[rt] != -1) {
lazy[ls(rt)] = max(lazy[ls(rt)], lazy[rt]);
lazy[rs(rt)] = max(lazy[rs(rt)], lazy[rt]);
c[ls(rt)] = max(c[ls(rt)], lazy[rt]);
c[rs(rt)] = max(c[rs(rt)], lazy[rt]);
lazy[rt] = -1;
}
}
void update(int rt, int l, int r, int x, int y, int v) {
if(x <= l && r <= y) {
lazy[rt] = max(lazy[rt], v);
c[rt] = max(c[rt], v);
return;
}
int mid = (l + r) >> 1;
push_down(rt, l, r);
if(x <= mid) update(ls(rt), l, mid, x, y, v);
if(y > mid) update(rs(rt), mid + 1, r, x, y, v);
push_up(rt);
}
int query(int rt, int l, int r, int x, int y) {
if(x <= l && r <= y) {
return c[rt];
}
int mid = (l + r) >> 1;
push_down(rt, l, r);
int ret = -1;
if(x <= mid) ret = max(ret, query(ls(rt), l, mid, x, y));
if(y > mid) ret = max(ret, query(rs(rt), mid + 1, r, x, y));
push_up(rt);
return ret;
}
int main() {
n = read(); q = read();
for(int i = 2; i <= n; i++) {
int u = read(), v = read();
add(u, v); add(v, u);
}
dfs1(1, 0);
dfs2(1, 1);
build(1, 1, n);
update(1, 1, n, 1, n, dfn[1]);
while(q--) {
char cmd; cin >> cmd; int num = read();
if(cmd == 'Q') {
printf("%d\n", rk[query(1, 1, n, dfn[num], dfn[num])]);
} else {
update(1, 1, n, dfn[num], dfn[num] + siz[num] - 1, dfn[num]);
}
}
return 0;
}
P4588 – TJOI2018 – 数学计算
题目信息
难度：提高+/省选-
算法：线段树
题目描述
有一个数 $x$，初始值为 $1$，现在有 $Q$ 次操作，操作分为两种类型：
- 给定 $m$，将 $x$ 变为 $x\times m$，并输出 $x\bmod M$，
- 给定 $pos$，将 $x$ 变为 $x$ 除以第 $pos$ 次所乘的数（保证第 $pos$ 次操作一定为类型 $1$，对于每个类型 $1$ 的操作最多被除一次），并输出 $x\bmod M$.
$M$ 是题目给定的常数。
对于 $20\%$ 的数据，$1\leq q\leq 500$，
对于 $100\%$ 的数据，$1\leq q\leq 10^5, 1 < M\leq 10^9$.
$\rm{Subtask}$ $1$
对于 $1\leq q\leq 500$ 的数据。
记录第 $i$ 次操作输入的数 $m_i$，对这次操作是否被除掉作标记。
每次询问的时候，扫一遍 $m$ 数组，计算乘积，复杂度 $\mathcal{O}(q^2)$.
$\rm{Subtask}$ $2$
对于 $1\leq q\leq 10^5$ 的数据，不难发现，上面算法的时间复杂度瓶颈在于求 $q$ 个数的乘积。
直接把询问编号作为横坐标，作为线段树维护即可将复杂度降到 $\mathcal{O}(q\log q)$.
#include <bits/stdc++.h>
#define int long long
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
using namespace std;
const int MAXN = 1e5 + 10;
int T, mod;
int c[MAXN << 2], lazy[MAXN << 2];
void push_up(int rt) {
c[rt] = c[ls(rt)] * c[rs(rt)] % mod;
}
void build(int rt, int l, int r) {
if(l == r) {
c[rt] = 1;
return;
}
int mid = (l + r) >> 1;
build(ls(rt), l, mid);
build(rs(rt), mid + 1, r);
push_up(rt);
}
void update(int rt, int l, int r, int x, int v) {
if(l == x && r == x) {
c[rt] = v;
return;
}
int mid = (l + r) >> 1;
if(x <= mid) update(ls(rt), l, mid, x, v);
if(x > mid) update(rs(rt), mid + 1, r, x, v);
push_up(rt);
}
signed main() {
scanf("%lld", &T);
while(T--) {
int Q; scanf("%lld%lld", &Q, &mod);
build(1, 1, Q);
for(int i = 1; i <= Q; i++) {
int opt, m; scanf("%lld%lld", &opt, &m);
if(opt == 1) {
update(1, 1, Q, i, m);
printf("%lld\n", c[1]);
} else {
update(1, 1, Q, m, 1);
printf("%lld\n", c[1]);
}
}
}
return 0;
}
P5677 – GZOI2017 – 配对统计
题目信息
难度：提高+/省选-
算法：数学、树状数组
题意
给定一个数列 $a_1, a_2, \cdots, a_n$.
定义在有序数对 $(x, y)$ 上的“好对”：对于 $a_x$，$y\in[1, x)\cup(x, n]$ 能使 $|a_x-a_y|$ 取最小值。
给定 $q\leq 3\times 10^5$ 组询问，每次询问一个区间 $[l, r]$ 中，有多少个好对。
题目求：每次询问的答案 $Ans_i$ 与询问编号 $i$ 的乘积的和，即：
\sum_{i=1}^{m}Ans_i\times i
$$
分析
关于匹配
任何一个好对 $(x, y)$，都满足 $|a_x-a_y|\leq |a_x-a_i|(i\neq x)$.
并且通过数据范围可以发现：$\forall i\neq j$ 都有 $a_i\neq a_j$，所以当 $x$ 固定时，确定 $y$ 的方法是非常自然的。
将 $a$ 数组排序，排序后的数组为 $b$，不妨设 $a_x$ 在 $b$ 中的下标为 $t$，那么 $a_y$ 在 $b$ 中的下标只可能为 $t-1$ 和 $t+1$.
具体地：
- 如果 $|b_t-b_{t-1}|<|b_{t+1}-b_{t}|$，也就是 $b_{t-1}$ 距离 $b_t$ 更近，那么 $a_y$ 在 $b$ 中的下标为 $t-1$；
- 如果 $|b_t-b_{t-1}|>|b_{t+1}-b_{t}|$，此时 $b_{t+1}$ 距离 $b_t$ 最近，$a_y$ 在 $b$ 中的下标为 $t+1$；
- 如果 $|b_t-b_{t-1}|=|b_{t+1}-b_{t}|$，$a_y$ 在 $b$ 中的下标为 $t-1$ 或 $t+1$.
总之，我们可以非常容易地在 $O(n\log n)$ 复杂度内，对于每个 $x$，找到能与其构成好的配对的 $y$.
关于询问
思路
现在的问题是如何统计答案。
因为题目只要求输出所有询问的和，于是想到将询问离线下来。对于每个好对，统计有多少个询问完全覆盖了它。这个好对对于最终答案的贡献就是：所有覆盖它的询问的编号之和。
对于这个问题，容易想到将所有询问排序，之后用树状数组维护，具体方法：
方法
从左到右枚举 $[1, n]$，假设枚举到了 $i$.
对于 $i$，我们已经计算过与其匹配的数，在 $a$ 中的下标 $y$，如果 $y > i$，那么所有左端点 $l\leq i$ 且右端点 $r\geq y$ 的询问都能包含这个好对。
再考虑答案的形式 $\sum_{i=1}^{m}Ans_i\times i$，我们现在要求：左端点 $l\leq i$ 且右端点 $r\geq y$ 的询问的编号和，使用树状数组维护。
于是考虑将询问按照左端点排序，在枚举到 $i$ 的时候，把所有左端点 $l\leq i$ 的询问加入到树状数组中，把树状数组的位置 $r$ 的权值加上这个询问的编号 $num$.
这样，$(i, y)$ 的贡献就等价于：树状数组中 $[y, n]$ 的区间和。
如果与 $i$ 匹配的 $y < i$，在上面的方法中并没有包含到。所以我们再反向枚举一遍 $i$，方法相同。将右端点 $r\geq i$ 的询问加入树状数组，每次的贡献为树状数组中 $[1, y]$ 的区间和。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 3e5 + 10;
const int inf = 0x3f3f3f3f3f3f3f3f;
int c[MAXN];
int n, m;
int lowbit(int x) {
return x & (-x);
}
void update(int x, int k) {
for(int i = x; i <= n; i += lowbit(i)) {
c[i] += k;
}
}
int query(int x) {
int ret = 0;
for(int i = x; i > 0; i -= lowbit(i)) {
ret += c[i];
}
return ret;
}
int query2(int x) {
return query(n) - query(x - 1);
}
int a[MAXN];
struct Node{int num, val;} b[MAXN];
bool cmp(Node A, Node B) {
return A.val <= B.val;
}
struct Query{int val, l, r;} q[MAXN];
bool cmp2(Query A, Query B) {
return A.r >= B.r;
}
bool cmp3(Query A, Query B) {
return A.l <= B.l;
}
int rk[MAXN];
signed main() {
scanf("%lld%lld", &n, &m);
for(int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
b[i].val = a[i]; b[i].num = i;
}
sort(b + 1, b + n + 1, cmp);
for(int i = 1; i <= n; i++) {
rk[b[i].num] = i;
}
for(int i = 1; i <= m; i++) {
q[i].val = i;
scanf("%lld%lld", &q[i].l, &q[i].r);
}
sort(q + 1, q + m + 1, cmp2);
int ans = 0;
b[0].val = -inf; b[n + 1].val = inf;
for(int i = n, j = 1; i >= 1; i--) {
while(q[j].r >= i && j <= m) {
update(q[j].l, q[j].val);
j++;
}
//下面六行：判断 t-1 和 t+1，哪个距离 t 更近，能与 t 构成好的匹配。
if(b[rk[i]].val - b[rk[i] - 1].val <= b[rk[i] + 1].val - b[rk[i]].val) {
if(b[rk[i] - 1].num < i) ans += query(b[rk[i] - 1].num);
}
if(b[rk[i]].val - b[rk[i] - 1].val >= b[rk[i] + 1].val - b[rk[i]].val) {
if(b[rk[i] + 1].num < i) ans += query(b[rk[i] + 1].num);
}
}
sort(q + 1, q + m + 1, cmp3);
memset(c, 0, sizeof(c));
for(int i = 1, j = 1; i <= n; i++) {
while(q[j].l <= i && j <= m) {
update(q[j].r, q[j].val);
j++;
}
if(b[rk[i]].val - b[rk[i] - 1].val <= b[rk[i] + 1].val - b[rk[i]].val) {
if(b[rk[i] - 1].num > i) ans += query2(b[rk[i] - 1].num);
}
if(b[rk[i]].val - b[rk[i] - 1].val >= b[rk[i] + 1].val - b[rk[i]].val) {
if(b[rk[i] + 1].num > i) ans += query2(b[rk[i] + 1].num);
}
}
cout << ans << endl;
return 0;
}
P5675 – GZOI2017 – 取石子游戏
题目信息
难度：提高+/省选-
算法：博弈论、动态规划
题目分析
显然，可以看出这个问题与Nim类游戏相关。Nim类游戏先手必胜，当且仅当每堆石子的数量的异或和不为 $0$。
所以Alice先手必败仅有两种情况：
- 异或和为 $0$；
- 异或和不为 $0$，但
Alice选择的第一堆石子无法使异或和变成0.
第一种情况容易处理，对于第二种情况，可以发现：只有指定选的第一堆石子数量，大于其他堆的异或和时，才能够做到：删去一堆棋子，异或和也不为 $0$.
综合两种情况，只要其他 $n-1$ 堆石子的异或和 $\geq $ 第一堆石子数量即可。
所以就可以枚举Alice先选择哪一堆 $i$，然后每次DP处理：有多少种选择方法使得异或和等于 $k$.
通过数学方法进行分析，容易得到上一段中的 $k\in[0, 256]$，于是直接二维 DP 即可。
DP状态：$f_{j, k}$ 表示，当固定一堆不选时，其余的前 $j$ 堆，异或和为 $k$ 的方案数量。
每次从上一行转移过来，具体看代码就行了。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 208, MAXJ = 270, mod = 1e9 + 7;
int n;
int a[MAXN];
int dp[MAXN][MAXJ]; //dp[j][k]表示，当固定一堆不选时，其余的前j堆，异或和为k的方案数量
signed main() {
scanf("%lld", &n);
for(int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
}
int ans = 0; dp[0][0] = 1;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
for(int k = 0; k < 256; k++) {
if(i == j) dp[j][k] = dp[j-1][k];
else dp[j][k] = (dp[j - 1][k] + dp[j - 1][k ^ a[j]]) % mod;
}
}
for(int j = a[i]; j < 256; j++) {
ans = (ans + dp[n][j]) % mod;
}
}
cout << ans << endl;
return 0;
}