草，这道题前前后后调了几个月，这几天终于给 A 了。
这道题可以使用 KDT 解决。显然先把 \(a_i\) 排序，接下来就是喜闻乐见的二维约束统计。如果是一维的约束，我们可以直接使用线段树。二维的话使用二维线段树又不现实（不知道动态开点行不行，没试过，顺便 orz 徐神的三维动态开点线段树）。
使用 KDT，考虑把 \((b_i,c_i)\) 当成一个坐标，接下来我们的 KDT 只需要资瓷插入点和查询有多少点在某个点的左上方就可以了，这是 KDT 的基操。
然而由于只写了两回这玩意儿，所以调了很久。主要的问题出在 query 部分：
int query(int p, int X0, int Y0, int X1, int Y1, int d) {
if(!p) return 0;
if(X0 <= tree[p].x[0] && tree[p].x[1] <= X1 && Y0 <= tree[p].y[0] && tree[p].y[1] <= Y1) return tree[p].siz;
int add = (X0 <= tree[p].d[0] && tree[p].d[0] <= X1 && Y0 <= tree[p].d[1] && tree[p].d[1] <= Y1) * tree[p].count;
//cout << "query " << p << " " << tree[p].x[0] << " " << tree[p].y[0] << " " << tree[p].x[1] << " " << tree[p].y[1] << " " << " / " << X0 << " " << Y0 << " " << X1 << " " << Y1 << endl;
if(!d) {
if(X1 < tree[p].d[0]) return query(tree[p].s[0], X0, Y0, X1, Y1, d ^ 1) + add;
else if(tree[p].d[0] < X0) return query(tree[p].s[1], X0, Y0, X1, Y1, d ^ 1) + add;
return query(tree[p].s[0], X0, Y0, tree[p].d[0], Y1, d ^ 1) + query(tree[p].s[1], tree[p].d[0], Y0, X1, Y1, d ^ 1) + add;
}
else {
if(Y1 < tree[p].d[1]) return query(tree[p].s[0], X0, Y0, X1, Y1, d ^ 1) + add;
else if(tree[p].d[1] < Y0) return query(tree[p].s[1], X0, Y0, X1, Y1, d ^ 1) + add;
return query(tree[p].s[0], X0, Y0, X1, tree[p].d[1], d ^ 1) + query(tree[p].s[1], X0, tree[p].d[1], X1, Y1, d ^ 1) + add;
}
}
注意到其中的 9 行和 14 行。如果当前询问区间分居当前节点的两侧，我们需要合并两侧 query 的答案对吧。然而这两个子区间需要都包含这个节点的在该维度上的坐标，以避免漏统计的情况。
一道很神的期望 dp，思维很是巧妙。
考虑最优的关灯方法。很容易想到一定是按编号从大到小关灯，遇到 1 就搞成 0。
同时很显然的一点是，如果我关了某个点的灯，一定没有其它的关灯组合能达到相同的效果。这一点可以严格证明并且不难。
于是我们得到一个结论：我们一定会关掉最优方案中的灯，如果中途误操作了其它的灯，我们必须再按一次将其造成的影响复原。
令 \(f_i\) 为使「剩余 \(i\) 盏要操作的灯」变到「剩余 \(i-1\) 盏要操作的灯」所需的期望次数。不难得到转移方程：
移项得
然后就可以愉快地 dp 了。注意 dp 的初始状态是 \(f_{n+1}=0\)（即到剩余 \(n\) 盏要操作的灯不需要任何步数）。
令最优方案中至少需要操作 \(q\) 盏灯，最后答案即 \(f_q+f_{q-1}+...+f_{k+1}+k\)。特别地，当 \(q \leq k\) 时，答案即为 \(q\)。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#define LL long long
#define Maxn 100010
#define MOD 100003
using namespace std;
inline int read() {
int x = 0, f = 1;
char c = getchar();
while(c < ‘0‘ || c > ‘9‘) {
if(c == ‘-‘) f = -1;
c = getchar();
}
while(‘0‘ <= c && c <= ‘9‘) {
x = x * 10 + c - ‘0‘;
c = getchar();
}
return x * f;
}
LL n, k, a[Maxn], f[Maxn], count;
vector <int> fac[Maxn];
LL Pow(LL a, LL b) {
LL ans = 1, base = a;
while(b) {
if(b & 1) ans = ans * base % MOD;
base = base * base % MOD;
b >>= 1;
}
return ans;
}
int main() {
n = read(); k = read();
for(int i = 1; i <= n; ++i) a[i] = read();
for(int i = 1; i <= n; ++i)
for(int j = i; j <= n; j += i)
fac[j].push_back(i);
for(int i = n; i; --i) {
if(a[i]) {
++count;
for(int j = 0; j < fac[i].size(); ++j) a[fac[i][j]] = a[fac[i][j]] ^ 1;
}
}
for(int i = n; i; --i) f[i] = ((n - i) * f[i + 1] % MOD + n) % MOD * Pow(i, MOD - 2) % MOD;
LL mul = 1;
for(int i = 1; i <= n; ++i) mul = mul * i % MOD;
if(k >= count) cout << count * mul % MOD << endl;
else {
LL sum = k;
for(int i = k + 1; i <= count; ++i) sum = (sum + f[i]) % MOD;
cout << sum * mul % MOD << endl;
}
return 0;
}
方法一
第一次暴力计算 \(\sum_{r=1}^nf(1,r)\)。考虑 \(f(1,x)\) 变到 \(f(2,x)\) 会形成的影响。
显然，第二次比第一次少了一个节点 \(1\)。我们和令 \(1\) 相连的点按照编号顺序为 \(v_1,v_2,...v_p\)。显然，如果 \(v_1 \in [2,x]\)，不会有任何影响。如果还有 \(v_2 \in [2,x]\)，则少了一个点 \(1\) 会使连通块 \(+1\)，如果还有 \(v_3 \in [2,x]\)，则少了一个点 \(1\) 会使连通块 \(+2\) …… 以此类推。
如果 \(v_1,v_2, ... ,v_p \notin [2,x]\)，则显然少了一个点 \(1\) 连通块个数会 \(-1\)。
因此我们在第一次暴力计算后，继续推着走就是了。每次 \(l\) 自增转移的时间为 \(O(1)\)。
然后就可以愉快的解决了。第一次暴力计算时由于要用并查集所以总复杂度为 \(O(n \log n)\)。
方法二 （法二来自徐神）
关注贡献。我们知道，一条边会使得树的连通块数量 \(-1\)。
对于一条连接 \(u,v\) 的边，他的会为所有满足 \(p \leq u < v \leq q\) 的 \(f(p,q)\) 贡献 \(-1\)，总贡献即为 \(-u \times (n-v+1)\)。
因此最终答案即为
总复杂度 \(O(n)\)。
原文：https://www.cnblogs.com/sqrtyz/p/13418701.html