CF513E2 Subarray Cuts
一开始还以为有什么神仙性质，找了半天发现性质不好，要考虑一些暴力点的做法了
相邻两段和之差的绝对值，这个限制很难处理
我们只能考虑把贡献拆开，如果把每段的位置与和标在一张折线图上，我们发现这张图中的「山峰」产生 \(+2\) 的贡献，「山谷」产生 \(-2\) 的贡献，中间的部分贡献为 \(0\)（两端贡献为 \(1/-1\)，特殊处理）
最大化，目标与限制方向相同，直接拆绝对值，DP 每段产生哪种贡献，就算不合法也不会比原来答案更大
设 \(f(i,j,s=0/1/2/3)\) 表示当前到了第 \(i\) 个数，选了 \(j\) 段，当前段的状态为 \(s\) 的最大价值
\(s=0\)：此段（可以为空）贡献为 \(0\)，且前面一段贡献为「山峰」
\(s=1\)：此段（可以为空）贡献为 \(0\)，且前面一段贡献为「山谷」
\(s=2\)：取到「山峰」，贡献为正
\(s=3\)：取到「山谷」，贡献为负
这样我们枚举当前数是新增一段还是接着上一段转移
注意，贡献为 \(0\) 包含了这个数在最终方案中根本不在段中的情况，即继承了上个空段，但段数 \(+1\) 时段不为空
不过好像能证明中间空段肯定不优（
int main()
{
read(n, k);
for(int i = 1; i <= n; ++i) read(a[i]);
memset(f, -0x3f, sizeof(f));
for(int i = 0; i <= n; ++i) f[i][0][0] = f[i][0][1] = 0;
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= k && j <= i; ++j)
{
int xi = (j == 1 || j == k) ? 1 : 2;
f[i][j][2] = max(f[i - 1][j][2], f[i - 1][j - 1][1]) + a[i] * xi;
f[i][j][3] = max(f[i - 1][j][3], f[i - 1][j - 1][0]) - a[i] * xi;
f[i][j][0] = max(f[i - 1][j][0], f[i][j][2]); // 可以继续不取，也可以是接下来的根本不在段内，贡献也为 0
f[i][j][1] = max(f[i - 1][j][1], f[i][j][3]);
if(xi == 2) // 可以单独开一段在中间，贡献为 0，但首尾不行
f[i][j][0] = max(f[i][j][0], f[i - 1][j - 1][0]), f[i][j][1] = max(f[i][j][1], f[i - 1][j - 1][1]);
}
}
printf("%d", max(f[n][k][0], f[n][k][1]));
return 0;
}
CF578D LCS Again
以为有什么高妙的 DP 做法，后来发现是分类讨论……
枚举哪一个位置不在 \(LCS\) 中，把连续一段相同字母缩成一个考虑，去除它们中的任意一个等价
再考虑这个字母变成什么，插入到哪里，这里钦定它不能插入跟它字母相同的段的中间和前面一个位置，对于每种字母 \(c\)，它有 \(n-cnt_c\) 种插入方法，对于每个段，枚举 \(c\)，总共有 \(m(n-1)\) 种方法
主要问题是去重
它插入所在这段前面一个字符的前面会与那个段的字符插入它这段第一个字符的后面重复，答案 \(-1\)
如果前面有形如 \(ababa\dots\) 这样的段，那么它插入前面也会与前面的插入后面重复，而且发现有且仅有这一种情况会重，直接暴力求出长度即可，注意这包含了上面的情况
int main()
{
cin >> n >> m >> (s + 1);
for(int i = 1; i <= n; ++i) ++sum[s[i] - 'a' + 1];
for(int i = 1, j = 1; i <= n; i = j)
{
while(j <= n && s[j] == s[i]) ++j;
book[i] = 1;
}
for(int i = 1, j = 0; i <= n; ++i)
{
if(i > 2 && s[i] == s[i - 2]) ++j; // abab...ab j = len - 2
else j = 0; // no abab...ab,only delete 1
if(book[i]) ans += n * (m - 1) - j - 1; // - (len - 1) = - (j + 1)
} // only moving itself and changing it to s[i-1] would be counted twice, they have len-1 choices in total
printf("%lld", ans + 1); // the begin should + 1
return 0;
}
CF757F Team Rocket Rises Again
好家伙支配树板子呢，我第一次听说这个东西
思路肯定是求多少点到 \(s\) 的最短路必须经过 \(x\)，把每个点放在它到 \(s\) 最短路上距离 \(s\) 最远的必经之点的后面，形成树形结构
删掉点 \(x\) 后，它子树内的都会变，建树就完了
DAG 的支配树求法：
先求出每个点到 \(s\) 的最短路，在最短路图上拓扑排序，那么假设连向 \(x\) 的点在支配树上的位置已经确定，它们都必经的点才是 \(x\) 必经的点，因此，\(fa_x\) 应是这些点的 \(lca\)
\(lca\) 可以支持动态加叶子，倍增即可，复杂度 \(O(n\log n)\)
void dij(int st)
{
memset(dis, 0x3f, sizeof(dis));
priority_queue<pll, vector<pll>, greater<pll> > heap;
dis[st] = 0, heap.push({0, st});
while(!heap.empty())
{
ll x = heap.top().se; heap.pop();
if(book[x]) continue;
book[x] = 1;
for(pll y : edge[x])
if(dis[y.fi] > dis[x] + y.se)
{
dis[y.fi] = dis[x] + y.se;
heap.push({dis[y.fi], y.fi});
}
}
}
int getlca(int x, int y)
{
if(dep[x] < dep[y]) swap(x, y);
for(int i = 18; i >= 0; --i)
if(f[i][x] && dep[f[i][x]] >= dep[y]) x = f[i][x];
if(x == y) return x;
for(int i = 18; i >= 0; --i)
if(f[i][x] && f[i][y] && f[i][x] != f[i][y]) x = f[i][x], y = f[i][y];
return f[0][x];
}
int main()
{
read(n, m, s);
for(int i = 1; i <= m; ++i)
{
read(u, v, w);
edge[u].pb({v, w}), edge[v].pb({u, w});
}
dij(s);
for(int i = 1; i <= n; ++i) id[i] = i, sum[i] = 1;
sort(id + 1, id + n + 1, [&](const ll x, const ll y){return dis[x] < dis[y];});
for(int i = 1; i <= n; ++i)
{
if(dis[id[i]] > inf) {ed = i - 1; break;}
for(pll j : edge[id[i]])
if(dis[j.fi] + j.se == dis[id[i]]) dag[j.fi].pb({id[i], j.se}), ++in[id[i]];
}
queue<int> q; // 支配树 dag 上的模板（为什么我从没听说过这个东西
q.push(s);
while(!q.empty())
{
int x = q.front(); q.pop();
for(int i = 1; i <= 18; ++i) f[i][x] = f[i - 1][f[i - 1][x]];
dep[x] = dep[f[0][x]] + 1, lin[++cnt] = x;
for(pll y : dag[x])
{
--in[y.fi];
if(in[y.fi] == 0) q.push(y.fi);
f[0][y.fi] = f[0][y.fi] ? getlca(f[0][y.fi], x) : x;
}
}
for(int i = cnt; i > 0; --i) sum[f[0][lin[i]]] += sum[lin[i]];
for(int i = 2; i <= cnt; ++i) ans = max(ans, sum[lin[i]]);
cout << ans;
return 0;
}
CF248E Piglet's Birthday
乍一看没什么思路，但是发现拿走的蜜罐都被吃了，放到另一个货架上不会对那个货架的概率产生影响
想维护每个货架 \(x\) 上被吃的蜜罐个数为 \(i\) 的概率 \(p_{x,i}\)，但这样放到 \(v\) 上能给 \(v\) 打标记，从 \(u\) 拿出来时枚举拿出的被吃的蜜罐数量，再枚举原来的数量，复杂度为 \(O(a_i^2)\)
但是这样万一往 \(u\) 上放了很多被吃的，枚举的复杂度就错了
正难则反，发现没吃的蜜罐逐渐减少，改为维护没吃的蜜罐，这样每个货架上 \(a_i\) 不会多余起始的，类似更新，复杂度为 \(O(qa_i^2)\)
double calc(int x, int y)
{
double res = 1;
for(int i = x; i > x - y; --i) res = res * (double)i;
for(int i = 1; i <= y; ++i) res = res / (double)i;
return res;
}
int main()
{
read(n);
for(int i = 1; i <= n; ++i) read(a[i]), p[i].resize(a[i] + 1), p[i][a[i]] = 1, sum += p[i][0];
for(int i = 0; i <= 500100; ++i)
{
c[i][0] = 1;
for(int j = 1; j <= 5 && j <= i; ++j) c[i][j] = calc(i, j);
}
read(q);
while(q--)
{
read(u, v, k);
vector<double> tmp(a[u] + 1);
for(int x = 0; x <= a[u] && x < p[u].size(); ++x)
{
for(int i = 0; i <= k && i <= x; ++i)
tmp[x - i] += p[u][x] * c[a[u] - x][k - i] / c[a[u]][k] * c[x][i];
}
sum -= p[u][0], sum += tmp[0], p[u] = tmp;
a[u] -= k, a[v] += k;
cout << sum << "\n";
}
return 0;
}
CF464D World of Darkraft - 2
唉怎么每种装备独立且等价还看不出来……
我们只需要讨论一种装备，期望 \(\times k\) 即可
设 \(f(i,j)\) 表示当前已经执行了 \(i\) 次操作，当前等级为 \(j\) 时的期望收益
但是每种装备依然可能升 \(n\) 级，复杂度为 \(O(n^2)\) 不可接受
继续考虑，发现精度要求不高，而到了后面升级的概率越来越小，可以忽略
因此只需要考虑 \(O(\sqrt n)\) 以内的级别即可
int main()
{
cin >> n >> k;
pr = (double)1 / (double)k;
for(int i = 1; i <= n; ++i, cur ^= 1)
{
memset(f[cur], 0, sizeof(f[cur]));
for(int j = 1; j <= n && j <= 800; ++j)
{
f[cur][j] += pr / (double)(j + 1) * (f[cur ^ 1][j + 1] + j); // 升一级
f[cur][j] += pr / (double)(j + 1) * ((double)j * f[cur ^ 1][j] + (double)j * (j + 1) / (double)2.0); // 未升级
f[cur][j] += (1 - pr) * f[cur ^ 1][j]; // 升级别人的
}
}
printf("%.12f", f[cur ^ 1][1] * (double)k);
return 0;
}
CF113D Museum
很多情况下都把期望转化为概率，但很少见概率转成期望的吧？
随机游走，我们一般都是求的期望步数
在这里如果设定的终点不同，转移方程也就不同，设 \(f(i,j)\) 表示两人一人在 \(i\)，另一人在 \(j\) 的概率，高斯消元直接做，枚举终点加上每次解方程是 \(O(n^7)\) 的
换个思路，我们如果将在任何一处相遇视为游走结束，那么结束位置在 \(x\) 的概率，就是两个人均在 \(x\) 这个状态被达到的期望步数，因为贡献系数总是 \(1\)
于是高斯消元求 \(f(i,j)\) 这个状态的期望出现次数，复杂度 \(O(n^6)\)
当然这题还有很多神奇做法，比如两人走了很多步的概率较小，设 \(P(x,i,j)\) 表示走了 \(x\) 步时状态为 \((i,j)\) 的概率，转移很多步直到精度能接受，可以使用矩阵乘法加速，复杂度 \(O(n^6(-\log \epsilon))\)
然后暴力枚举终点的做法好像也能过
void gauss()
{
for(int i = 1; i <= n * n; ++i)
{
int nw = i;
for(int j = i + 1; j <= n * n; ++j)
if(fabs(f[j][i]) > fabs(f[nw][i])) nw = j;
for(int j = 1; j <= n * n + 1; ++j) swap(f[i][j], f[nw][j]);
for(int j = 1; j <= n * n; ++j)
{
if(i == j) continue;
double divv = f[j][i] / f[i][i];
for(int k = 1; k <= n * n + 1; ++k) f[j][k] -= f[i][k] * divv;
}
}
}
int main()
{
cout << fixed << setprecision(10);
cin >> n >> m >> a >> b;
for(int i = 1; i <= m; ++i) cin >> u >> v, g[u][v] = g[v][u] = 1, ++deg[u], ++deg[v];
for(int i = 1; i <= n; ++i) cin >> p[i], pr[i] = (double)1 / (double)deg[i];
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j) id[i][j] = (i - 1) * n + j;
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= n; ++j)
{
--f[id[i][j]][id[i][j]];
for(int k = 1; k <= n; ++k)
for(int l = 1; l <= n; ++l)
{
if(l == k) continue;
double p1 = 0, p2 = 0;
p1 = g[i][k] ? (1 - p[k]) * pr[k] : (i == k ? p[k] : 0);
p2 = g[j][l] ? (1 - p[l]) * pr[l] : (j == l ? p[l] : 0);
f[id[i][j]][id[k][l]] += p1 * p2;
}
if(i == a && j == b) --f[id[i][j]][n * n + 1];
}
}
gauss();
for(int i = 1; i <= n; ++i) cout << f[id[i][i]][n * n + 1] / f[id[i][i]][id[i][i]] << " ";
return 0;
}
CF1363F Rotating Substrings
循环移位可以看作是每次把一个字符插入到它前面的某个位置
我一开始脑抽了，以为可以任意插入，想了半天发现以为求 \(LCS\) 就行了
考虑一个字符什么时候被放到前面，当 \(s\) 中后面它出现的次数大于 \(t\) 对应位置后面它出现的次数，就必须挪动，还给前面
为了使代价不重复计算，当 \(s\) 尝试与 \(t\) 匹配，发现 \(s\) 前面字符更少，意味着它会从后面拿一个，看作是借了一个就不再有代价
因此设 \(f(i,j)\) 表示 \(s\) 的前缀 \(i\) 加上一些后与 \(t\) 的前缀 \(1\sim j\) 匹配的最小代价
随时都能花费 \(1\) 的代价还给前面，因为多还了不优，不影响答案，如果 \(s_i=t_j\) 那就刚好不用动，匹配长度能直接增加，如果 \(s\) 前面 \(t_j\) 更少，那从后面借一个，不用代价，但需要借才能借，否则后面还不上
void mian()
{
cin >> n >> (s + 1) >> (t + 1);
for(int i = 0; i < 26; ++i)
for(int j = 1; j <= n; ++j) sums[i][j] = sumt[i][j] = 0;
for(int i = 1; i <= n; ++i)
{
for(int j = 0; j < 26; ++j) sums[j][i] = sums[j][i - 1], sumt[j][i] = sumt[j][i - 1];
++sums[s[i] - 'a'][i], ++sumt[t[i] - 'a'][i];
}
for(int i = 0; i < 26; ++i)
if(sumt[i][n] != sums[i][n]) {print(-1), putchar('\n'); return;}
for(int i = 1; i <= n; ++i)
for(int j = 0; j <= n; ++j) f[i][j] = inf;
for(int i = 1; i <= n; ++i)
for(int j = i; j <= n; ++j)
{
f[i][j] = min(f[i][j], f[i - 1][j] + 1); // 还给前面
if(s[i] == t[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]); // 直接匹配
if(sums[t[j] - 'a'][i] <= sumt[t[j] - 'a'][j - 1]) f[i][j] = min(f[i][j], f[i][j - 1]); // 借一个
}
print(f[n][n]), putchar('\n');
}
CF603E Pastoral Oddities
很高兴的是自己看出了 key observation，那就是如果每一个连通块有偶数个点是有解的充要条件
必要性显然，连通块中的度数和一定是偶数
充分性是考虑取出连通块中的一棵生成树，则在树上从叶子到根匹配即可构造方案
然后答案可以整体二分，但是修改的贡献不能拆开，还有二维的限制，一是边权，二是加入的时间，不能仅仅只是处理完后递归右边然后简单的撤销
这题还有一个性质：答案单调不增，意味着答案在值域 \([l,r]\) 时，询问也是一个区间 \([ql,qr]\)
把它刻画到二维平面上，横轴是加入时间，纵轴是边权，每次查询我们要保证它代表的左下角矩形中所有边已经加入，对于每层二分，即边权 \(<l\)，加入时间 \(<ql\) 的边已经加入
每层我们为保证时间复杂度，只能扫描当前代表矩形的边，这样能动态按时间 \(ql\sim qr\) 加入边权 \(\le mid\) 的边，看在哪个时刻 \(x\) 满足
当然你会发现，查询时矩形依然少了一块，边权在 \([l,mid]\) 且加入时间 \(<ql\) 的边，这时扫描 \([l,mid]\) 先加入即可
之后撤回新增的修改
然后递归到左边，边权在 \([mid+1,r]\) 内，询问区间为 \([ql,x-1]\)，此时还是要先加入边权在 \([l,mid]\) 且加入时间 \(<ql\) 的边
递归到右边，边权在 \([l,mid]\) 内，询问区间为 \([x,qr]\)，要新加入边权 \(<l\) 且修改时间在 \([l,x)\) 内的边
每次都要用可撤销并查集撤回新增修改，分治中每层复杂度只与区间长度相关，复杂度 \(O(n\log^2 n)\)
注意比较边的大小时要按排序后在序列上的位置，因为可能很多边边权相同但跨过了分治中心 \(mid\)
struct node {int x, y, fax, sizy, tot;}stk[M * 18];
struct DSU
{
int fa[N], siz[N], sum;
void init() {for(int i = 1; i <= n; ++i) fa[i] = i, siz[i] = 1; sum = n;}
int find(int x) {return fa[x] != x ? find(fa[x]) : x;}
void merge(int x, int y)
{
x = find(x), y = find(y);
if(x == y) return;
if(siz[x] > siz[y]) swap(x, y);
stk[++top] = {x, y, fa[x], siz[y], sum};
sum -= (siz[x] & 1) + (siz[y] & 1);
fa[x] = y, siz[y] += siz[x], sum += (siz[y] & 1);
}
void rollback(node x) {fa[x.x] = x.fax, siz[x.y] = x.sizy, sum = x.tot;}
}dsu;
void solve(int l, int r, int ql, int qr) // 当前边的编号 < ql 且 val < l 的边已经全部加入
{ // 刻画到二维平面上，每次递归前保证矩形左下角已经加入，每次加入的是一块矩形
if(l > r || ql > qr) return;
if(l == r)
{
for(int i = ql; i <= qr; ++i) ans[i] = l;
return;
}
int mid = (l + r) >> 1, nw = top, nl = qr + 1;
for(int i = l; i <= mid; ++i)
if(val[i] < ql) dsu.merge(u[val[i]], v[val[i]]);
for(int i = ql; i <= qr; ++i)
{
if(fid[i] <= mid) dsu.merge(u[i], v[i]);
if(!dsu.sum) {nl = i; break;}
}
while(top > nw) dsu.rollback(stk[top--]);
for(int i = l; i <= mid; ++i)
if(val[i] < ql) dsu.merge(u[val[i]], v[val[i]]);
solve(mid + 1, r, ql, nl - 1);
while(top > nw) dsu.rollback(stk[top--]);
for(int i = ql; i < nl; ++i) // 比较的应该是在序列上排好序后的位置，因为大小会重复，会出现在 mid 后但大小相同的情况
if(fid[i] < l) dsu.merge(u[i], v[i]);
solve(l, mid, nl, qr);
while(top > nw) dsu.rollback(stk[top--]);
}
int main()
{
read(n, m);
for(int i = 1; i <= m; ++i) read(u[i], v[i], w[i]), val[i] = i;
sort(val + 1, val + m + 1, [&](const int x, const int y){return w[x] < w[y];});
for(int i = 1; i <= m; ++i) fid[val[i]] = i;
dsu.init();
solve(1, m + 1, 1, m);
for(int i = 1; i <= m; ++i) print(ans[i] <= m ? w[val[ans[i]]] : -1), putchar('\n');
return 0;
}
CF809E Surprise me!
跟路径有关问题想到点分治，把 \(\varphi(a_ia_j)\) 拆开就好了
\(\varphi\) 不是完全积性函数，把它展开，\(\varphi(a_i)=a_i\prod_{k}(1-\frac 1 {p_k})\)，\(\varphi(a_ia_j)\) 会重复的部分在于它们可能有公因子，多乘了 \(1-\frac 1 p\)
所以推一下式子可知 \(\varphi(a_ia_j)=\dfrac{\varphi(a_i)\varphi(a_j)}{\varphi(\gcd(a_i,a_j))}\gcd(a_i,a_j)\)
点分治后，贡献看作是
\[\dfrac{\varphi(a_i)\varphi(a_j)}{\varphi(\gcd(a_i,a_j))}\gcd(a_i,a_j)(dis_i+dis_j) \\ = (\varphi(a_i)\varphi(a_j)dis_i+\varphi(a_i)\varphi(a_j)dis_j)\dfrac{\gcd(a_i,a_j)}{\varphi(\gcd(a_i,a_j))} \]对于每个 \(\gcd\)，把可能的 \(\varphi(a_i)dis_i\) 与 \(\varphi(a_i)\) 的和存起来，即枚举 \(a_i\) 的因数 \(d\)，加入贡献到 \(sum_d\) 中
查询则查询 \(a_j\) 的因数 \(d\)，求出当 \(\gcd(a_i,a_j)\) 为 \(d\) 的倍数时，\(\varphi(a_i)\varphi(a_j)dis_i+\varphi(a_i)\varphi(a_j)dis_j\) 的和
最后容斥一下，求出恰好为 \(d\) 时的和，乘上 \(\frac d{\varphi(d)}\) 即可
由于 \(a\) 为排列，所以枚举因数总的复杂度为 \(O(n\ln n)\)，复杂度 \(O(n\log n\ln n)\)
我一开始脑抽了，坚持要在查询时容斥，这样大概是 \(O(n\times d^2(n))\)，但我不知道它具体的级别，\(n=2\times 10^5\) 时输出了一下，大概有 \(2\times 10^7\)，带只 \(\log\) 需要大力卡常
求那个和也可以把是 \(d\) 倍数的点拉出来建虚树，不过没点分治好写
void init()
{
for(int i = 1; i <= n; ++i)
for(int j = i; j <= n; j += i) fac[j].pb(i);
inv[0] = 1;
for(int i = 1; i <= n; ++i) inv[i] = qmi(i, mod - 2);
phi[1] = 1;
for(ll i = 2; i <= n; ++i)
{
if(!st[i]) prime[++cnt] = i, phi[i] = i - 1;
for(ll j = 1; j <= cnt && i * prime[j] <= n; ++j)
{
st[i * prime[j]] = 1;
if(i % prime[j] == 0) {phi[i * prime[j]] = phi[i] * prime[j]; break;}
phi[i * prime[j]] = phi[i] * phi[prime[j]];
}
}
}
void findrt(int x, int fa)
{
siz[x] = 1; int res = 0;
for(int y : edge[x])
if(y != fa && !vis[y]) findrt(y, x), siz[x] += siz[y], res = max(res, siz[y]);
res = max(res, tot - siz[x]);
if(res <= mn) mn = res, root = x;
}
void getroot(int x) {findrt(x, 0), tot = siz[x], mn = N, root = x, findrt(x, 0);}
void upd(int x, int op)
{
for(int i : fac[a[x]])
{
sum[0][i] = add(sum[0][i], op ? phi[a[x]] * dis[x] % mod : mod - phi[a[x]] * dis[x] % mod);
sum[1][i] = add(sum[1][i], op ? phi[a[x]] : mod - phi[a[x]]);
}
}
void qry(int x)
{
for(int i : fac[a[x]])
ans[i] = add(ans[i], add(sum[0][i] * phi[a[x]] % mod, sum[1][i] * phi[a[x]] % mod * dis[x] % mod));
}
void dfs(int x, int fa, int op)
{
dis[x] = dis[fa] + 1;
if(op < 2) upd(x, op);
else qry(x);
for(int y : edge[x])
if(y != fa && !vis[y]) dfs(y, x, op);
}
void solve(int x)
{
vis[x] = 1;
dis[x] = 0, upd(x, 1);
for(int y : edge[x])
if(!vis[y]) dfs(y, x, 2), dfs(y, x, 1);
for(int y : edge[x])
if(!vis[y]) dfs(y, x, 0);
upd(x, 0);
for(int y : edge[x])
if(!vis[y]) getroot(y), solve(root);
}
int main()
{
read(n);
for(int i = 1; i <= n; ++i) read(a[i]);
for(int i = 1; i < n; ++i) read(u, v), edge[u].pb(v), edge[v].pb(u);
init();
getroot(1), solve(root);
for(ll i = n; i > 0; --i)
for(ll j = i + i; j <= n; j += i) ans[i] = add(ans[i], mod - ans[j]);
ll res = 0;
for(ll i = 1; i <= n; ++i) res = add(res, ans[i] * i % mod * inv[phi[i]] % mod);
cout << res * 2ll % mod * inv[n] % mod * inv[n - 1] % mod;
return 0;
}
CF814E An unavoidable detour for home
不会数数，\(O(n^3)\) 的做法比 \(O(n^5)\) 好写多了！
考虑分层加入点，上一层会剩下一些剩 \(1/2\) 度的点用来连下一层，其余剩下的边则两两配对
预处理处 \(g(i,j)\) 表示有 \(i\) 个点有 \(1\) 条边，\(j\) 个点有 \(2\) 条边时配对方案数
本来可以随便选，但度数为 \(2\) 的点不能连成自环，也不能两个这样的点连出重边
方案数 = 随便选 - 有自环 - 无自环但有重边
所以预处理出 \(h(i,j)\) 表示这样配对时有自环的方案数，还是枚举自环个数容斥
\(g\) 也同理容斥，注意度数为 \(2\) 的点两条边匹配没有顺序，还需除以 \(2^j\)
重头戏是 \(dp(i,j,k)\) 的转移，表示上一层有 \(j\) 个剩 \(1\) 度的点，\(k\) 个剩 \(2\) 度的点，下一层加 \(i\) 个点后，这一层连完的方案数
枚举 \(i\) 个点中用完了 \(x\) 个 \(2\) 度点，用了 \(y\) 个 \(2\) 度点的一条边，用 \(g\) 再乘上一坨长长的式子转移
最后设 \(f(i,j,k)\) 表示共用 \(i\) 个点，上一层剩 \(j\) 个 \(1\) 度点，\(k\) 个二度点的方案数，枚举新的一层放 \(u\) 个点转移
答案为 \(\sum f(n,j,k)\times g(j,k)\)
复杂度 \(O(n^5)\)，但快的难以置信，优化一下 \(j,k\) 的设计即可优化到 \(O(n^4)\)
int main()
{
read(n);
for(int i = 1; i <= n; ++i) read(d[i]);
for(int i = 1; i <= n; ++i) s[0][i] = s[0][i - 1], s[1][i] = s[1][i - 1], ++s[d[i] - 2][i];
fact[0] = invf[0] = pw[0] = 1, V = n * 2;
for(ll i = 1; i <= V; ++i) fact[i] = fact[i - 1] * i % mod, pw[i] = pw[i - 1] * 2ll % mod;
invf[V] = qmi(fact[V], mod - 2);
for(ll i = V - 1; i > 0; --i) invf[i] = invf[i + 1] * (i + 1) % mod;
for(ll i = 0; i <= V; ++i)
{
c[i][0] = 1;
for(ll j = 1; j <= i; ++j) c[i][j] = add(c[i - 1][j - 1], c[i - 1][j]);
}
for(ll i = 0; i <= n; ++i)
{
dwn[i][0] = 1;
for(ll j = 1; j <= i; ++j) dwn[i][j] = dwn[i][j - 1] * (i - j + 1) % mod;
}
sum[0] = 1;
for(ll i = 2; i <= V; i += 2) sum[i] = sum[i - 2] * (i - 1) % mod;
for(ll i = 0; i <= n; i += 2)
for(ll j = 1; j <= n; ++j)
{
for(ll k = 1; k <= j; ++k) // 有自环方案数
{
ll nw = c[j][k] * sum[(j - k) * 2 + i] % mod;
h[i][j] = add(h[i][j], (k & 1) ? nw : mod - nw);
}
}
g[0][0] = 1;
for(ll i = 0; i <= n; i += 2)
for(ll j = 0; j <= n; ++j)
{
if(!i && !j) continue;
g[i][j] = add(sum[j * 2 + i], mod - h[i][j]);
ll tmp = 0; // 有重边但无自环
for(ll k = 1; k + k <= j; ++k)
{
ll lsh = c[j][k * 2] * sum[k * 2] % mod * pw[k] % mod * add(sum[(j - k * 2) * 2 + i], mod - h[i][j - k * 2]) % mod;
tmp = add(tmp, (k & 1) ? lsh : mod - lsh);
}
g[i][j] = add(g[i][j], mod - tmp) * qmi(pw[j], mod - 2) % mod; // 无重边且无自环
}
for(ll i = 1; i <= n; ++i) // 新增 i 个，上层有 j 个点剩 1 度，k 个点剩 2 度
for(ll x = 0; x + x <= i && x <= s[1][n]; ++x)
for(ll y = 0; y <= s[1][n] && x + x + y <= i; ++y)
{
ll tmp = c[i][x * 2] * fact[x * 2] % mod * qmi(pw[x], mod - 2) % mod * fact[y] % mod * c[i - x * 2][y] % mod;
ll st = i - 2 * x - y; if((st & 1) != (i & 1)) ++st;
for(ll j = st; j <= n; j += 2)
for(ll k = x + y; k <= s[1][n] && k + j <= n; ++k)
dp[i][j][k] = add(dp[i][j][k], c[k][x] * dwn[j][i - 2 * x - y] % mod * c[k - x][y] % mod * tmp % mod * g[j - (i - x * 2 - y) + y][k - x - y] % mod);
}
if(d[1] == 2) f[3][s[0][3] - s[0][1]][s[1][3] - s[1][1]] = 1;
else f[4][s[0][4] - s[0][1]][s[1][4] - s[1][1]] = 1;
if(d[1] == 3 && n <= 3) {printf("0"); return 0;}
for(int i = d[1] == 2 ? 3 : 4; i < n; ++i) // f[i][j][k]：共 i 个点，上层有 j 个点剩 1 度，k 个点剩 2 度
{
for(int j = 0; j <= i; ++j)
for(int k = 0; j + k <= i; ++k)
if(f[i][j][k])
{
for(int u = 1; u <= n - i; ++u) // 新增 u 个
{
ll s0 = s[0][i + u] - s[0][i], s1 = s[1][i + u] - s[1][i];
f[i + u][s0][s1] = add(f[i + u][s0][s1], f[i][j][k] * dp[u][j][k] % mod);
}
}
}
for(int j = 0; j <= n; j += 2)
for(int k = 0; k <= s[1][n] && j + k <= n; ++k) ans = add(ans, f[n][j][k] * g[j][k] % mod);
cout << ans;
return 0;
}
CF198D Cube Snake
这种硬构造题，写起来像大模拟的，还是似一似比较好
对于每个 \(k\in[1,n]\) 都要满足，启发我们需要递归构造
我们需要构造一个 \(n\times n\times(n+1)\) 的长方体，满足它去掉上顶面或下底面后剩的正方体编号连续，答案则输出长方体去掉上顶面
我们构造的起点在 \((1,1,1)\)，终点在 \((n+1,1,n)\)
先根据 \(n\) 的奇偶性，分类讨论，铺满上顶面和下底面，起点挪到 \((1,1,n)\)，终点挪到 \((n+1,1,1)\)
然后剥掉最前面的一面，即 \(j=1\) 的那面，还要保证起点和终点在小长方体 \(n\times(n+1)\) 这面的对角线上
那就把起点直接挪到 \((2,1,1)\)，终点再根据奇偶性，分类讨论，绕完剩下格子到 \((n,1,n)\)
旋转坐标系后把小长方体放进来即可
注意当 \(n=2\) 时由于剥去一面时起点和终点绕不开，需手动构造
复杂度 \(O(n^4)\)
vector<vector<vector<int> > > construct(int x)
{
vector<vector<vector<int> > > a;
a.resize(x + 2);
for(vector<vector<int> > &i : a)
{
i.resize(x + 1);
for(vector<int> &j : i) j.resize(x + 1);
}
if(x == 1)
{
a[1][1][1] = 1, a[2][1][1] = 2;
return a;
}
vector<vector<vector<int> > > b = construct(x - 1);
int ed = x * x * (x + 1), nw = sq(x);
auto build = [&](int cur, int layer) -> void
{
if(x & 1)
{
for(int i = 1; i <= x - 2; ++i)
if((i - 1) & 1)
for(int j = x; j > 0; --j) a[layer][j][i] = ++cur;
else
for(int j = 1; j <= x; ++j) a[layer][j][i] = ++cur;
for(int i = x; i > 0; --i)
if((x - i + 1) & 1) a[layer][i][x - 1] = ++cur, a[layer][i][x] = ++cur;
else a[layer][i][x] = ++cur, a[layer][i][x - 1] = ++cur;
}
else
{
for(int i = 1; i <= x; ++i)
if((i - 1) & 1)
for(int j = x; j > 0; --j) a[layer][j][i] = ++cur;
else
for(int j = 1; j <= x; ++j) a[layer][j][i] = ++cur;
}
};
build(0, 1), ed -= nw, build(ed, x + 1);
if(x == 2)
{
a[2][1][1] = 6, a[2][1][2] = 5, a[2][2][2] = 8, a[2][2][1] = 7, a[3][2][2] = 9, a[3][2][1] = 10, a[3][1][1] = 11, a[3][1][2] = 12;
return a;
}
for(int i = x; i > 0; --i) a[2][1][i] = ++nw;
if(x & 1)
{
for(int i = x; i > 2; --i)
if((x - i) & 1)
for(int j = x - 1; j > 0; --j) a[i][1][j] = ed--;
else
for(int j = 1; j < x; ++j) a[i][1][j] = ed--;
for(int i = 3; i <= x; ++i) a[i][1][x] = ed--;
}
else
{
for(int i = 1; i <= x; ++i)
if(i & 1)
for(int j = x; j > 2; --j) a[j][1][i] = ed--;
else
for(int j = 3; j <= x; ++j) a[j][1][i] = ed--;
}
for(int i = 1; i <= x; ++i)
for(int j = 1; j < x; ++j)
for(int k = 1; k < x; ++k) a[k + 1][j + 1][i] = b[i][j][k] + nw;
return a;
}
int main()
{
cin >> n;
ans = construct(n);
for(int i = 1; i <= n; ++i, putchar('\n'))
for(int j = 1; j <= n; ++j, putchar('\n'))
for(int k = 1; k <= n; ++k) print(ans[i][j][k]), putchar(' ');
return 0;
}
CF273E Dima and Game
自己做出来的博弈题！
首先状态只与差有关，而且差 \(x\) 每次只能变成 \(\lfloor\frac x 3\rfloor\) 或 \(x-\lfloor\frac x 3\rfloor\)
每一组都是独立的子游戏，想到把 \(sg\) 值异或起来就能知道胜负
每个状态只有两个前驱，\(sg\) 值在 \([0,2]\) 之间，最后 DP 时只需要设 \(f(i,j)\) 表示前 \(i\) 组，\(sg\) 异或和为 \(j\) 的方案数
问题在于值域很大，怎样快速求出 \(sg\) 值为 \(a\) 的差 \(x\) 的数量
手玩半天，硬是看不出什么规律，但发现 \(sg\) 相同的连续段是越来越长
打表惊奇发现它只有 \(101\) 段
那就把它们打成表，每次枚举每段，能求出 \(sg=a\) 的组数
DP 即可
\(n\) 还可以出的更大，这个题就很迷，官方题解至今都没有
bitset<N> is1, is2;
int cnt, n, p, sum[3], f[4][N];
int a[110][2] = {{0, 0}, {1, 0}, {3, 1}, {4, 2}, {5, 1}, {7, 2}, {9, 0}, {13, 1}, {15, 2}, {19, 0}, {27, 1}, {39, 2},
{40, 0}, {57, 2}, {58, 1}, {81, 2}, {85, 0}, {120, 2}, {121, 1}, {174, 2}, {179, 0}, {255, 2},
{260, 1}, {363, 2}, {382, 0}, {537, 2}, {544, 1}, {780, 2}, {805, 0}, {1146, 2}, {1169, 1}, {1632, 2},
{1718, 0}, {2415, 2}, {2447, 1}, {3507, 2}, {3622, 0}, {5154, 2}, {5260, 1}, {7341, 2}, {7730, 0}, {10866, 2},
{11011, 1}, {15780, 2}, {16298, 0}, {23190, 2}, {23669, 1}, {33033, 2}, {34784, 0}, {48894, 2}, {49549, 1}, {71007, 2},
{73340, 0}, {104352, 2}, {106510, 1}, {148647, 2}, {156527, 0}, {220020, 2}, {222970, 1}, {319530, 2}, {330029, 0}, {469581, 2},
{479294, 1}, {668910, 2}, {704371, 0}, {990087, 2}, {1003364, 1}, {1437882, 2}, {1485130, 0}, {2113113, 2}, {2156822, 1}, {3010092, 2},
{3169669, 0}, {4455390, 2}, {4515137, 1}, {6470466, 2}, {6683084, 0}, {9509007, 2}, {9705698, 1}, {13545411, 2}, {14263510, 0}, {20049252, 2},
{20318116, 1}, {29117094, 2}, {30073877, 0}, {42790530, 2}, {43675640, 1}, {60954348, 2}, {64185794, 0}, {90221631, 2},
{91431521, 1}, {131026920, 2}, {135332446, 0}, {192557382, 2}, {196540379, 1}, {274294563, 2}, {288836072, 0},
{405997338, 2}, {411441844, 1}, {589621137, 2}, {608996006, 0}, {866508216, 2}, {884431705, 1}, {(int)1e9 + 1, 0}};
#ifdef Kelly
int sg(int x) {return is1[x] ? 1 : (is2[x] ? 2 : 0);}
int mex(int x, int y) {if(x > y) swap(x, y); return x == 0 ? (y == 1 ? 2 : 1) : 0;}
int calc(int i) {int x = mex(sg(i / 3), sg(i - i / 3)); is1[i] = (x == 1), is2[i] = (x == 2); return x;}
#endif
int add(int a, int b) {return a + b >= mod ? a + b - mod : a + b;}
int get(int x, int y) {return (1ll * (x + y) * (y - x + 1) / 2) % mod;}
int main()
{
#ifdef Kelly
for(int i = 3, j = i; i <= 1e9; )
{
while(j <= 1e9 && calc(j) == calc(i)) ++j;
printf("{%d, %d}, ", i, calc(i));
i = j, ++cnt;
if(cnt % 10 == 0) printf("\n");
}
cerr << cnt << "\n";
#endif // 打表程序
cin >> n >> p;
for(int i = 1; i <= 102; ++i)
{
if(a[i][0] >= p) break;
int r = min(a[i + 1][0] - 1, p - 1), l = a[i][0];
sum[a[i][1]] = add(sum[a[i][1]], get(p - r, p - l));
}
f[0][0] = 1;
for(int i = 1; i <= n; ++i)
for(int j = 0; j < 4; ++j)
for(int k = 0; k < 3; ++k) f[j ^ k][i] = add(f[j ^ k][i], 1ll * f[j][i - 1] * sum[k] % mod);
cout << add(f[1][n], add(f[2][n], f[3][n]));
return 0;
}
CF625E Frog Fights
不好评价，CF 上出这种好想不好写的题目感觉会被骂
发生反超的一定是相邻的青蛙，先算出相邻两只的反超距离，然后丢入堆中，每次取出堆顶，看那只最远能反超到哪里，用环形链表维护青蛙的相对位置，删除被反超的，并重新计算改变了相邻关系的反超时间
每只青蛙最多删除一次，复杂度 \(O(n\log n)\)，计算时间的部分简直一坨，改变 \(a\) 后还要记录原来跳到的距离
ll jump(ll x, ll t)
{
ll y = nxt[x], nx = pos[x] + lasdis[x] + (t - tim[x]) * a[x], ny = pos[y] + lasdis[y] + (t - tim[y]) * a[y];
if(pos[x] > pos[y]) ny += m;
if(t && x < y)
{
if(nx >= ny - a[y]) return t;
}
if(nx >= ny) return t;
if(x < y && nx + a[x] >= ny) return t + 1;
if(a[x] <= a[y]) return inf;
return t + (ny - nx + a[x] - a[y] - 1 - (x < y ? a[x] : 0)) / (a[x] - a[y]) + (x < y ? 1 : 0);
}
void del(ll x) {nxt[pre[x]] = nxt[x], pre[nxt[x]] = pre[x], book[x] = 1;}
int main()
{
read(n, m);
for(int i = 1; i <= n; ++i) read(pos[i], a[i]), id[i] = i;
sort(id + 1, id + n + 1, [&](const int x, const int y){return pos[x] < pos[y];});
for(int i = 1; i <= n; ++i) nxt[id[i]] = id[i % n + 1], pre[id[i]] = id[i - 1 ? i - 1 : n];
for(int i = 1; i <= n; ++i) heap.insert({has[i] = jump(i, 0), i});
while(!heap.empty())
{
pii x = *heap.begin(); heap.erase(x);
if(x.fi >= inf) break;
if(book[x.se] || has[x.se] != x.fi) continue;
T = x.fi, lasdis[x.se] += a[x.se] * (T - tim[x.se]), tim[x.se] = T;
while(nxt[x.se] != x.se)
{
ll tmp = jump(x.se, T);
if(tmp <= x.fi)
{
--a[x.se], a[x.se] = max(0ll, a[x.se]);
del(nxt[x.se]);
}
else
{
heap.insert({has[x.se] = tmp, x.se});
ll y = pre[x.se], lsh = jump(y, T); heap.erase({has[y], y});
heap.insert({has[y] = lsh, y});
break;
}
}
}
for(int i = 1; i <= n; ++i) ans += !book[i];
print(ans), putchar('\n');
for(int i = 1; i <= n; ++i)
if(!book[i]) print(i), putchar(' ');
return 0;
}
CF830E Perpetual Motion Machine
只允许你把 \(d_i\) 设置为非负整数相当于已经告诉你设为 \(<1\) 的小数没用
分每个连通块考虑，有一个有解即把其它的全部设为 \(0\) 即可
如果某个连通块内边数 \(\ge\) 点数，直接把 \(d_i\) 全设为 \(1\)
否则连通块是一棵树，全设为 \(1\) 时刚好少了一个贡献
发现若把某个 \(d_i\) 从 \(1\) 改为 \(2\)，会增加 度数 \(-3\) 的贡献，因此只要有一个度数 \(\ge 4\) 的节点，直接把它改成 \(2\)
还发现如果有两个三度点，则把它们路径上的点改成 \(2\) 也行
如果是一条链，不管怎样肯定无解
发现现在只剩下有一个三度点，且它下面挂了三条链的情况
分析某一条链，假设有三个点权值为 \(d_1,d_2,d_3\)，那么贡献为 \(d_1d_2+d_2d_3-d_1^2-d_2^2-d_3^2\)
把 \(d_1,d_3\) 看成定值，则是 \(-d_2^2+(d_1+d_3)d_2-d_1^2-d_3^2\)，发现当 \(d_2=\frac{d_1+d_3}2\) 时最大
也就是说，链上的数一定是等差数列
假设长度为 \(n\) 的等差数列的公差为 \(c\)，三度点的值为 \(d\)
如果在叶子后面加上 \(0\)，则 \(c=\dfrac{d}{n+1}\)
\[\sum_{i=1}^n(d-(i-1)c)(d-ic)-\sum_{i=1}^{n} (d-ic)^2 \\ = \sum_{i=1}^n c(d-ic) = \frac n{2n+2}d^2 \]所以
\[\sum_n \frac n{2n+2}d^2 -d^2\ge 0 \\ \sum_{n}\frac n{2n+2} \ge 1 \]考虑构造，发现 \(n\) 为 \((2,2,2)\) 时，\(d=3,c=1\)，为 \((1,3,3)\) 时，\(d=4,c=2,1,1\)，为 \((1,2,5)\) 时，\(d=6,c=3,2,1\)
然后直接构造即可，复杂度 \(O(n)\)
void clear()
{
idx = cnt = tot = top = 0;
for(int i = 0; i <= n; ++i) col[i] = deg[i] = vis[i] = book[i] = dep[i] = nxt[i] = 0, edge[i].clear();
}
void dfs(int x, int fa, int c)
{
col[x] = c, ++tot, tmp.pb(x);
for(int y : edge[x])
if(!col[y]) dfs(y, x, c);
}
void Dfs(int x, int fa, int g)
{
stk[++top] = x, vis[x] = 1;
if(x == g)
for(int i = 1; i <= top; ++i) book[stk[i]] = 1;
for(int y : edge[x])
if(y != fa && !vis[y]) Dfs(y, x, g);
--top;
}
void DFS(int x, int fa)
{
dep[x] = 1;
for(int y : edge[x])
if(y != fa) nxt[x] = y, DFS(y, x), dep[x] = dep[y] + 1;
}
int work(int x)
{
cnt = tot = top = 0, tmp.clear(), dfs(x, 0, ++idx);
for(int i : tmp) cnt += deg[i];
cnt >>= 1;
if(cnt >= tot)
{
puts("YES");
for(int i = 1; i <= n; ++i) printf(col[i] == idx ? "1 " : "0 ");
return 1;
}
int mx = 0, sum = 0, id = 0;
for(int i : tmp) deg[i] > mx ? (mx = deg[i], id = i) : mx, sum += (deg[i] >= 3);
if(mx >= 4)
{
puts("YES");
for(int i = 1; i <= n; ++i) printf(col[i] == idx ? (i == id ? "2 " : "1 ") : "0 ");
return 1;
}
if(sum >= 2)
{
for(int i = tmp.size() - 1; i >= 0; --i)
if(deg[tmp[i]] == 3 && tmp[i] != id) {Dfs(tmp[i], 0, id); break;}
puts("YES");
for(int i = 1; i <= n; ++i) printf(col[i] == idx ? (book[i] ? "2 " : "1 ") : "0 ");
return 1;
}
if(mx < 3) return 0;
for(int i : edge[id]) DFS(i, id);
sort(edge[id].begin(), edge[id].end(), [&](const int x, const int y){return dep[x] < dep[y];});
if(dep[edge[id][0]] >= 2)
{
book[id] = 3;
for(int x : edge[id])
for(int i = 2; i > 0; --i) book[x] = i, x = nxt[x];
}
else if(dep[edge[id][1]] >= 3)
{
book[id] = 4, book[edge[id][0]] = 2;
for(int i = 1; i <= 2; ++i)
for(int x = edge[id][i], j = 3; j > 0; --j) book[x] = j, x = nxt[x];
}
else if(dep[edge[id][1]] >= 2 && dep[edge[id][2]] >= 5)
{
book[id] = 6, book[edge[id][0]] = 3, book[edge[id][1]] = 4, book[nxt[edge[id][1]]] = 2;
for(int x = edge[id][2], i = 5; i > 0; --i) book[x] = i, x = nxt[x];
}
else return 0;
puts("YES");
for(int i = 1; i <= n; ++i) printf("%d ", book[i]);
return 1;
}
void mian()
{
clear();
read(n, m);
for(int i = 1; i <= m; ++i)
{
read(u, v), ++deg[u], ++deg[v];
edge[u].pb(v), edge[v].pb(u);
}
for(int i = 1; i <= n; ++i)
if(!col[i])
if(work(i)) {puts(""); return;}
puts("NO");
}
CF446D DZY Loves Games
如果我们知道从每个陷阱处 \(i\) 走到下一个陷阱 \(j\) 的概率 \(p_{i,j}\)，那么再求出 \(1\) 走到每个陷阱点且不经过其它陷阱的概率，把 \(p\) 用矩阵快速幂求出 \(p^{k-2}\)，得到了从每个陷阱处出发扣了 \(k-2\) 条生命到 \(n\) 的概率，把它乘上 \(1\) 到它扣一条生命的概率累加到答案
求 \(p_{i,j}\) 的过程，需要知道某个非陷阱点 \(i\) 走到陷阱点 \(j\) 且不经过其它陷阱点的概率 \(f_{i,j}\)
\(p_{i,j}=\frac 1 {deg_i}\sum_{(i,v)\in E}f_{v,j}\)
我们枚举终点 \(j\)，\(f_{j,j}=1\)，对于其它陷阱点 \(x\)，\(f_{x,j}=0\)，对于非陷阱点 \(i\)，\(f_{i,j}=\frac 1 {deg_i}\sum_{(v,i)\in E}f_{v,j}\)
转移有环，需要高斯消元，但这样复杂度为 \(O(n^4)\)
发现对于每个不同的 \(j\)，只是陷阱点在等号右边的系数变化，于是矩阵接上的系数向量变成 \(cnt\) 列的系数矩阵，一次高斯消元即可全部求出这 \(cnt\) 个方程组的解
复杂度为 \(O(n^3+cnt^3\log k)\)
注意由于这里全是小数运算，精度在矩阵乘多次后爆炸了，高斯消元时不能用 \(eps\) 判为 \(0\) 即跳过，可能微小的数对结果影响很大
struct matrix
{
double a[N][N];
double * operator[](const int x) {return a[x];}
}g, to, I;
matrix operator * (const matrix &x, const matrix &y)
{
matrix res;
memset(res.a, 0, sizeof(res.a));
for(int i = 1; i <= cnt; ++i)
for(int u = 1; u <= cnt; ++u)
if(fabs(x.a[i][u]) >= eps)
for(int j = 1; j <= cnt; ++j) res[i][j] += x.a[i][u] * y.a[u][j];
return res;
}
void gauss(matrix &x)
{
for(int i = 1; i <= n; ++i)
{
int nw = i;
for(int j = i + 1; j <= n; ++j)
if(fabs(x[j][i]) > fabs(x[nw][i])) nw = j;
for(int j = 1; j <= n + cnt; ++j) swap(x[i][j], x[nw][j]);
for(int j = 1; j <= n; ++j)
{
if(i == j) continue;
double divv = x[j][i] / x[i][i];
for(int u = 1; u <= n + cnt; ++u) x[j][u] -= x[i][u] * divv;
}
}
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= cnt; ++j) x[i][n + j] /= x[i][i];
}
matrix qmi(matrix x, int b)
{
matrix res = I;
for(; b; b >>= 1, x = x * x) if(b & 1) res = res * x;
return res;
}
int main()
{
read(n, m, k);
for(int i = 1; i <= n; ++i)
{
read(book[i]);
if(book[i]) id[i] = ++cnt;
}
for(int i = 1; i <= m; ++i)
{
read(u, v), ++deg[u], ++deg[v];
++G[u][v], ++G[v][u];
}
for(int i = 1; i <= n; ++i) pr[i] = (double)1 / (double)deg[i];
for(int i = 1; i <= n; ++i) // P[i \to a] don't lose live at spl except a
{
if(book[i]) {g[i][i] = g[i][n + id[i]] = 1; continue;}
for(int j = 1; j <= n; ++j)
if(G[i][j]) g[i][j] = (double)G[i][j] * pr[i];
g[i][i] -= 1;
}
gauss(g);
for(int i = 1; i <= n; ++i)
if(book[i])
for(int j = 1; j <= n; ++j) // P[i \to j] just lose one live at j
if(book[j])
for(int u = 1; u <= n; ++u)
if(G[i][u]) to[id[i]][id[j]] += g[u][n + id[j]] * G[i][u] * pr[i];
for(int i = 0; i <= cnt; ++i) I[i][i] = 1;
to = qmi(to, k - 2);
for(int i = 1; i <= n; ++i)
if(book[i]) ans += g[1][n + id[i]] * to[id[i]][id[n]];
printf("%.8f", ans);
return 0;
}
CF494E Sharti
太神秘的博弈论
首先棋盘翻转游戏可以看作是每个初始时被涂黑的格子在棋盘上只有它是黑色时的子游戏的组合
自然它的 \(sg\) 值就是所有格子 \(sg\) 值的异或和
问题变成了求每个格子的 \(sg\) 值
打表或者手玩，发现格子 \((x,y)\) 的 \(sg\) 值是 \(\min\{\operatorname{lowbit}(x),\operatorname{lowbit}(y),\operatorname{greatbit}(k)\}\)
给出一个归纳证明：
记 \(s_i=\bigoplus_{j=1}^i \operatorname{lowbit}(i)\)
\(s_{2^k}=2^{k}\)，可以考虑每一位的贡献
\(s_1\sim s_{2^k}\) 组成的集合恰为 \([0,2^k-1]\)
证明考虑对 \(k\) 归纳，当 \(k=1\) 时成立，当 \(k>1\) 时，\(s_1\sim s_{2^{k-1}}\) 组成的集合是 \([0,2^{k-1}-1]\)，那么考虑 \(2^{k-1}+1\sim 2^k\) 中的数，它们相对于 \(1\sim 2^{k-1}\) 加上了 \(2^{k-1}\)，只改变了最后一位，因此单独截出这一段做前缀异或，应当就是 \([0,2^{k-1}-1]\)，\(s_{2^{k-1}+1}\sim s_{2^k}\) 就是把这一段异或上 \(s_{2^{k-1}}\)，即 \(2^{k-1}\)，因此 \([0,2^{k-1}-1]\cup [2^{k-1},2^{k}-1]=[0,2^k-1]\)
假设归纳到了 \((x,y)\)，在 \((x,y)\) 左上角的格子的 \(sg\) 值已经是上面所述
那么
\[sg(x,y)=\operatorname{mex}_{i=1}^{\min\{x,y,k\}} \bigoplus_{x-i+1\le l\le x,y-i+1\le r\le y}sg(l,r) \]考虑以 \((x,y)\) 为右下角，边长为 \(a\) 的正方形，它关于对角线对称，因此只用考虑对角线上的 \(sg\) 值
我们先不管 \(k\) 的限制，假设 \(\operatorname{lowbit}(x)=2^n<\operatorname{lowbit}(y)\)，应该说明的是 \(sg(l,r)\) 取遍 \([0,\operatorname{lowbit}(x))\) 且没有 \(\operatorname{lowbit}(x)\)
当 \(i<2^n\) 时，\(\operatorname{lowbit}(x-i)=\operatorname{lowbit}(i)\)，那么只要 \(a\) 取遍 \([1,2^n]\)，得到的 \(\bigoplus_{i=1}^{a-1} \operatorname{lowbit}(x-i)\) 的并集就是 \([0,2^n-1]\)
没有 \(2^n\) 则考虑反证法，假设我们找到了一个 \(a\le k\)，使 \(\bigoplus_{i=1}^{a-1} \operatorname{lowbit}(x-i)=2^n\)，则对于 \(j\ne n\)，\(2^j\) 要出现偶数次，\(2^n\) 加上 \(x\) 自己也应该出现偶数次
由上面可得 \(a>2^n\)，设 \(b=\lceil\frac{a}{2^n}\rceil\)，\(2^d=\operatorname{lowbit}(b)\)
那么 \(2^d\times 2^n\le b\times 2^n\le a\le k\)，即 \(2^{d+n}\le k\)
那么 \(\frac b {2^d}\) 肯定是奇数
原来参考的证明现在看不到了，证不下去了，反正后面大概是证出了奇偶性矛盾，评价是不如打表
有了这个结论，不同的 \(sg\) 值只有 \(O(\log n)\) 个，考虑容斥，求出 \(sg(x,y)\ge 2^i\) 的数量，这要求 \(x,y\) 均为 \(2^i\) 的倍数，比较好做，直接把矩形的顶点转换坐标，扫描线求矩形面积并即可
其实只要某个值 \(sg\) 的数量为奇数就先手必胜了，这意味着 \(sg(x,y)\ge 2^i\) 的数量至少有一个奇数，反之后手必胜，\(sg(x,y)\ge 2^i\) 的数量也全是偶数，只需要直接判断奇偶性即可，复杂度 \(O(m\log m\log n)\)
struct mdy {int l, r, val;};
vector<mdy> upd[N << 1];
struct info {int mn, mncnt;};
struct lsh
{
int cnt, a[N << 1];
void clear() {for(int i = 1; i <= cnt; ++i) upd[i].clear(); cnt = 0;}
void ins(int x) {a[++cnt] = max(x, 1);}
void build() {sort(a + 1, a + cnt + 1), cnt = unique(a + 1, a + cnt + 1) - (a + 1);}
int find(int val) {return lower_bound(a + 1, a + cnt + 1, val) - a;}
}lx, ly;
info operator + (const info &x, const info &y)
{
return {min(x.mn, y.mn), (x.mn <= y.mn ? x.mncnt : 0) + (y.mn <= x.mn ? y.mncnt : 0)};
}
struct segtree
{
int tag[N << 3]; info node[N << 3];
int ls(int x) {return x << 1;}
int rs(int x) {return x << 1 | 1;}
void pushup(int x) {node[x] = node[ls(x)] + node[rs(x)];}
void upd(int x, int val) {node[x].mn += val, tag[x] += val;}
void pushdown(int x) {upd(ls(x), tag[x]), upd(rs(x), tag[x]), tag[x] = 0;}
void build(int l, int r, int p)
{
tag[p] = 0;
if(l == r) return void(node[p] = {0, ly.a[l + 1] - ly.a[l]});
int mid = (l + r) >> 1;
build(l, mid, ls(p)), build(mid + 1, r, rs(p));
pushup(p);
}
void update(int l, int r, int val, int nl, int nr, int p)
{
if(l <= nl && nr <= r) return upd(p, val);
int mid = (nl + nr) >> 1;
pushdown(p);
if(mid >= l) update(l, r, val, nl, mid, ls(p));
if(mid < r) update(l, r, val, mid + 1, nr, rs(p));
pushup(p);
}
}tree;
int work(int w)
{
lx.clear(), ly.clear();
int lim = (1 << w);
for(int i = 1; i <= m; ++i)
if(((p[i].a + lim - 1) >> w) <= (p[i].c >> w) && ((p[i].b + lim - 1) >> w) <= (p[i].d >> w))
lx.ins((p[i].a + lim - 1) >> w), lx.ins((p[i].c >> w) + 1), ly.ins((p[i].b + lim - 1) >> w), ly.ins((p[i].d >> w) + 1);
lx.ins(1), ly.ins(1), lx.build(), ly.build(), lx.a[lx.cnt + 1] = ly.a[ly.cnt + 1] = V + 1;
tree.build(1, ly.cnt, 1);
int ans = 0;
for(int i = 1; i <= m; ++i)
if(((p[i].a + lim - 1) >> w) <= (p[i].c >> w) && ((p[i].b + lim - 1) >> w) <= (p[i].d >> w))
{
int ln = ly.find((p[i].b + lim - 1) >> w), rn = ly.find((p[i].d >> w) + 1) - 1;
upd[lx.find((p[i].a + lim - 1) >> w)].pb({ln, rn, 1}), upd[lx.find((p[i].c >> w) + 1)].pb({ln, rn, -1});
}
for(int i = 1; i <= lx.cnt; ++i)
{
for(mdy x : upd[i]) tree.update(x.l, x.r, x.val, 1, ly.cnt, 1);
if((lx.a[i + 1] - lx.a[i]) & 1)
ans = (ans + V - (tree.node[1].mn ? 0 : (tree.node[1].mncnt & 1))) & 1;
}
return ans;
}
int main()
{
read(n, m, k);
for(int i = 1; i <= m; ++i) read(p[i].a, p[i].b, p[i].c, p[i].d);
for(int i = 0; i <= 30 && (1 << i) <= k; ++i)
if(work(i)) {puts("Hamed"); return 0;}
puts("Malek");
return 0;
}
CF478E Wavy numbers
看到数据范围，想到根号分治，当 \(n>10^7\) 时，可以暴力枚举 \(n\) 的倍数并判断
当 \(n\le 10^7\) 时，就得想办法求
二分答案后数位 DP 不太可以，位数太多，且必须记录 \(\bmod n\) 的余数，空间时间都不够
于是接着分治，先预处理出前 \(7\) 位符合要求的数，并且把可能和后 \(7\) 位拼接的数按开头数字，上升/下降，除以 \(n\) 的余数塞入 vector，之后暴力枚举后 \(7\) 位，在对应 vector 中查找，如果刚好落在那就输出拼接后的数，否则 \(k\) 减去 vector 大小
时间复杂度 \(O(\sqrt n\times\log_{10}n )\)
注意直接开 \(10^7\) 个 vector 会爆空间，用 unordered_map 存这些即可，因为波浪数在 \(n\) 很大时除以 \(n\) 的余数无法取遍 \(0\sim n-1\)
上升还是下降的细节调了好久……
ll wavy(ll x)
{
if(x < 10) return 1;
ll st = x % 10;
x /= 10; ll op = x % 10 < st, tmp = op;
while(x)
{
if((x % 10 < st) != op || x % 10 == st) return 2;
op ^= 1, st = x % 10, x /= 10;
}
return tmp;
}
unordered_map<ll, vector<int> > num[2][10];
int main()
{
cin >> n >> k;
for(int i = 1; i <= V; ++i) w[i] = wavy(i);
if(n >= 1e7)
{
for(ll i = n; i <= (ll)1e14; i += n)
if(wavy(i) < 2)
{
--k;
if(!k) {cout << i; return 0;}
}
cout << -1; return 0;
}
for(int i = 1; i < V; ++i)
{
if(w[i] == 2) continue;
if(i % n == 0)
{
--k;
if(k == 0) {cout << i; return 0;}
}
if(i * 10 >= V / 10)
{
if((i / (V / 10) == 0 && (w[i] ^ 1)) || i / (V / 10))
num[i / (V / 10) ? (w[i] ^ 1) : 1][i / (V / 10)][i % n].pb(i);
}
}
for(ll i = 1; i < V; ++i)
{
if(w[i] == 2) continue;
ll st = 0, ed = 9;
w[i] ? (ed = i % 10 - 1) : (st = i % 10 + 1);
if(i < 10)
{
for(int j = 0; j <= 9; ++j)
{
if(j == i % 10) continue;
ll tmp = (n - i * V % n) % n;
if(num[i > j][j].find(tmp) == num[i > j][j].end()) continue;
ll nw = num[i > j][j][tmp].size();
if(k <= nw) {cout << num[i > j][j][tmp][k - 1] + i * V; return 0;}
k -= nw;
}
continue;
}
for(int j = st; j <= ed; ++j)
{
ll tmp = (n - i * V % n) % n;
if(num[w[i]][j].find(tmp) == num[w[i]][j].end()) continue;
ll nw = num[w[i]][j][tmp].size();
if(k <= nw) {cout << num[w[i]][j][tmp][k - 1] + i * V; return 0;}
k -= nw;
}
}
cout << -1;
return 0;
}
CF468D Tree
这种不好直接算的题要考虑拆开贡献
把贡献下放到每条边上，那么每条边最多被经过的次数是断开这条边后两个连通块大小较小值的 \(2\) 倍
问题是能否构造出上界
如果我们钦定了根为 \(root\)，那么只要在 \(root\) 的不同子节点的子树中的点配对即可，要使得完美匹配存在
发现当 \(root\) 是树的重心时，每个子树大小 \(\le \frac n 2\)，每个点会向其它子树中 \(>\frac n 2\) 个点连边，根据 Hall 定理，\(|S|\le |N(S)|\)， 存在完美匹配，而且可以这样考虑，如果一组匹配中有一对子树内的匹配，那把它与另一对点均不在这个子树中的匹配交换，就得到了合法匹配
所以以重心为根，从 \(1\sim n\) 贪心选取能匹配的点中字典序最小的
记录 \(root\) 的子节点 \(x\) 的子树中待匹配的左部点数量为 \(in_x\)，右部点数量为 \(out_x\)，初始时 \(in_x=out_x=siz_x\)
当前枚举到左部点 \(i\)，如果除 \(x\) 这棵子树外剩余的左部点数量 \(<out_x\)，即 \(n-i+1-in_x<out_x\)，\(in_x+out_x>n-i+1\) 时无解
所以用 set 维护 \(in_x+out_x\)，当最大值为 \(n-i+1\) 时，就必须选 \(x\) 子树中的右部点，否则可以选全局不在 \(i\) 所在子树内的编号最小右部点，特别的，如果 \(i\) 也在 \(x\) 内转化为无限制的情况
注意特判根节点，它可以与包括自己的任何点匹配
维护除自己所在子树内的点的编号最小值可以用线段树，每个位置上存子树中的最小值，单点修改，查询前缀和后缀最小值
set<pll> lim; set<int> match, res[N];
using iter = set<int>::iterator;
void dfs(int x, int fa)
{
int res = 0; siz[x] = 1;
for(pll y : edge[x])
if(y.fi != fa) dfs(y.fi, x), siz[x] += siz[y.fi], res = max(res, siz[y.fi]);
res = max(res, n - siz[x]);
if(res < mn) mn = res, root = x;
}
void Dfs(int x, int fa, int c)
{
col[x] = c, ++in[c], ++out[c], siz[x] = 1;
for(pll y : edge[x])
if(y.fi != fa) Dfs(y.fi, x, c), ans += 2ll * y.se * siz[y.fi], siz[x] += siz[y.fi];
}
struct segtree
{
int mn[N << 2];
int ls(int x) {return x << 1;}
int rs(int x) {return x << 1 | 1;}
void pushup(int x) {mn[x] = min(mn[ls(x)], mn[rs(x)]);}
void build(int l, int r, int p)
{
if(l == r) return void(mn[p] = res[l].empty() ? N : *res[l].begin());
int mid = (l + r) >> 1;
build(l, mid, ls(p)), build(mid + 1, r, rs(p));
pushup(p);
}
void update(int id, int val, int l, int r, int p)
{
if(l == r) return void(mn[p] = val);
int mid = (l + r) >> 1;
if(mid >= id) update(id, val, l, mid, ls(p));
else update(id, val, mid + 1, r, rs(p));
pushup(p);
}
int query(int l, int r, int nl, int nr, int p)
{
if(l > r) return N;
if(l <= nl && nr <= r) return mn[p];
int mid = (nl + nr) >> 1, res = N;
if(mid >= l) res = min(res, query(l, r, nl, mid, ls(p)));
if(mid < r) res = min(res, query(l, r, mid + 1, nr, rs(p)));
return res;
}
}tree;
int main()
{
read(n);
for(int i = 1; i < n; ++i)
{
read(u, v, w);
edge[u].pb({v, w}), edge[v].pb({u, w});
}
mn = N, dfs(1, 0);
for(pll x : edge[root]) Dfs(x.fi, root, x.fi), ans += 2ll * x.se * siz[x.fi];
lim.insert({1 + 1, 0}), in[0] = out[0] = 1, col[root] = 0;
for(int i = 1; i <= n; ++i) match.insert(i), res[col[i]].insert(i);
for(pll x : edge[root]) lim.insert({in[x.fi] + out[x.fi], x.fi});
tree.build(0, n, 1);
for(int i = 1; i <= n; ++i)
{
pll tmp = *lim.rbegin();
while(lim.size() > 1 && !out[tmp.se]) lim.erase(*lim.rbegin()), tmp = *lim.rbegin();
if(tmp.fi < n - i + 1 || tmp.se == col[i] || !out[tmp.se] || tmp.se == 0)
{
p[i] = min(tree.query(0, col[i] - 1, 0, n, 1), tree.query(col[i] + 1, n, 0, n, 1));
if(i == root && p[i] > root && match.find(root) != match.end()) p[i] = root;
}
else p[i] = *res[tmp.se].begin();
lim.erase({in[col[p[i]]] + out[col[p[i]]], col[p[i]]}), lim.erase({in[col[i]] + out[col[i]], col[i]});
--out[col[p[i]]], --in[col[i]], res[col[p[i]]].erase(p[i]), match.erase(p[i]);
lim.insert({in[col[p[i]]] + out[col[p[i]]], col[p[i]]}), lim.insert({in[col[i]] + out[col[i]], col[i]});
tree.update(col[p[i]], res[col[p[i]]].empty() ? N : *res[col[p[i]]].begin(), 0, n, 1);
}
print(ans), putchar('\n');
for(int i = 1; i <= n; ++i) print(p[i]), putchar(' ');
return 0;
}
CF763E Timofey and our friends animals
一开始以为可以线段树维护区间内前 \(k\) 个点和后 \(k\) 个点连通性状压后的结果，后来发现连通性会通过中间的点被影响……
但其实线段树可以做，直接维护区间的并查集，因为只需要暴力合并前 \(k\) 个和后 \(k\) 个，时间复杂度 \(O((n+q)\log nk^2)\)
当然更暴力的思路为回滚莫队，用可撤销并查集维护，每次右端点移动时加边，左端点移动完撤回即可，时间复杂度 \(O(q\sqrt n\log n)\)，常数小跑的很快
发现线段树做法，合并复杂度太高了，而且没有修改，可以考虑猫树分治，复杂度应该是 \(O(n\log nk^2+qk^2)\)
vector<int> ask[B + 10], rb;
struct DSU
{
int fa[N], siz[N], sum;
void init(int l, int r) {for(int i = l; i <= r; ++i) fa[i] = i, siz[i] = 1; rb.clear(); sum = 0;}
int find(int x) {return x != fa[x] ? find(fa[x]) : x;}
void merge(int x, int y, int op)
{
x = find(x), y = find(y); if(x == y) return;
if(siz[x] > siz[y]) swap(x, y);
if(op) rb.pb(x);
fa[x] = y, siz[y] += siz[x], ++sum;
}
void rollback(int x) {siz[fa[x]] -= siz[x], fa[x] = x, --sum;}
}dsu;
int main()
{
read(n, k, m);
for(int i = 1, u, v; i <= m; ++i)
{
read(u, v);
if(u > v) swap(u, v);
g[0][u] |= (1 << (v - u)), g[1][v] |= (1 << (v - u));
}
for(int i = 1; i <= n; ++i) blk[i] = (i - 1) / B + 1;
read(q);
for(int i = 1; i <= q; ++i) read(u[i], v[i]), ask[blk[u[i]]].pb(i);
for(int i = 1; i <= blk[n]; ++i) sort(ask[i].begin(), ask[i].end(), [&](const int x, const int y){return v[x] < v[y];});
for(int i = 1; i <= blk[n]; ++i)
{
dsu.init(1, n);
int ln = i * B + 1, rn = ln;
for(int x : ask[i])
{
if(v[x] < ln)
{
for(int y = v[x]; y >= u[x]; --y)
for(int j = 1; j <= k; ++j)
if(y + j <= v[x] && ((g[0][y] >> j) & 1)) dsu.merge(y, y + j, 1);
ans[x] = v[x] - u[x] + 1 - dsu.sum;
while(!rb.empty()) dsu.rollback(rb.back()), rb.pop_back();
continue;
}
while(rn <= v[x])
{
for(int j = 1; j <= k; ++j)
if(rn - j >= ln && ((g[1][rn] >> j) & 1)) dsu.merge(rn - j, rn, 0);
++rn;
}
rb.clear();
for(int y = ln - 1; y >= u[x]; --y)
for(int j = 1; j <= k; ++j)
if(y + j <= v[x] && ((g[0][y] >> j) & 1)) dsu.merge(y, y + j, 1);
ans[x] = v[x] - u[x] + 1 - dsu.sum;
while(!rb.empty()) dsu.rollback(rb.back()), rb.pop_back();
}
}
for(int i = 1; i <= q; ++i) print(ans[i]), putchar('\n');
return 0;
}
CF1267G Game Relics
肯定是先抽，而且抽会随着得到物品的增多而越来越不优，所以最后再一起把没抽到的买了
那什么时候不抽了呢？
关键结论是把买的价值分摊到每次购买上，每次购买的期望花费是 \(\frac{\sum c}{i}\)，即剩下价值的总和除以剩下的个数
购买可以看作随机从没拿到的物品中花费这么多代价得到一个，这和原来的购买是等价的，因为购买的顺序是不重要的，反正都是抽完后一起买
还有很关键的思路是我们直接期望 DP 很困难，但我们能根据期望的线性性，把每次转移时的代价累加
假设当前已经有 \(i\) 个总价值为 \(j\) 的物品，抽出下一个物品的期望代价是 \((\frac{n}{n-i}-1)\frac x 2+x\)，此时直接购买的代价看作 \(\frac{sum-j}{n-i}\)，比较这两个代价，选择较小的一个则是转移，累加至答案中
此时还要算出到达这种状态的概率，是一个背包，可以 \(O(n^2\sum c)\) 计算
概率 \(f(i,j)\) 的计算可以看作是方案数随时除以 \(n\choose i\)，也可以直接计算，下一步从 \(n-i\) 中选到指定的数的概率是 \(\frac{1}{n-i}\)，它插入序列中有 \(i+1\) 种方法
int main()
{
read(n, x);
for(int i = 1; i <= n; ++i) read(c[i]), ans += c[i];
f[0][0] = 1;
for(int i = 1; i <= n; ++i) // f[i][j] : P[number = i, \sum c = j]
for(int j = n - 1; j >= 0; --j)
for(int k = ans - c[i]; k >= 0; --k) f[j + 1][k + c[i]] += f[j][k] * (double)(j + 1) / (double)(n - j);
for(int i = 0; i < n; ++i) // now have i different relics
for(int j = 0; j < ans; ++j) // have \sum_i c_i = j
sum += min(x / 2 * (n / (double)(n - i) - 1) + x, (ans - j) / (double)(n - i)) * f[i][j];
printf("%.12f", sum);
return 0;
}
CF925E May Holidays
唉，卡常题，\(O(n\sqrt n)\) 跑的没有 \(O(n\sqrt n\log n)\) 快……
不太能 \(\mathrm{polylog}\) 的样子，考虑分块
发现重构比较方便，而且 \(O(nq)\) 暴力显然，计算每次修改带来的影响简单
考虑询问分块，每 \(B\) 个询问一组
此时前面我们已经得到了一棵有黑点也有白点的树，记每个点 \(lim_i=t_i+1-siz_i\)，看作是这一组中新的限制，每次修改可以看作是把它到根的路径上的点的 \(lim-1\)，当 \(lim\) 为 \(0\) 且是白点时计入答案
我们维护当前询问与上一次询问的变化量 \(sum_x\)，那么一次修改，会导致此时阈值为 \(1/-1\) 的白点变化，如果计算出此时每个点已经被加的值 \(del_i\)，那么对于修改点到根路径上 \(lim_i=-del_i/-del_i+1\) 的点，这次修改完状态会变
\(B\) 个询问点组成的虚树大小为 \(O(B)\)，意味着不同的 \(del\) 段只有 \(O(B)\) 段，我们可以把询问拆到每一段上，求这一段中 \(lim_i=x\) 的点的数量，转化为求到根路径上的数量再前缀和相减，重构时 dfs 离线求出，用桶记录，对每一段的每个询问是 \(O(1)\) 的
我们统计时，先只看原来的颜色，只统计原来是白色的，但一组中可能某个合法的白点变黑了就不能计算，也可能某个黑点变白了之后就应该计算，重构时暴力把每次修改颜色的那个点对后面询问 \(sum\) 的影响撤销，具体是分类讨论，如果原来是白点，那么讨论在它变黑和变回白的瞬间产生的变化以及把所有黑色时产生变化的瞬间撤销，黑点同理
这部分细节很多，具体看代码
重构则暴力修改颜色并计算出新的 \(lim\)，比较平凡
时间复杂度 \(O(\frac q B (B^2+n)+qB)\)，取 \(B=\sqrt n\) 时最优，复杂度为 \(O((n+q)\sqrt n)\)
实现时被常数折磨，如果每次询问存到 vector 中，vector 不析构释放空间的话空间复杂度会退化为 \(O(n\sqrt n)\)，会 MLE，析构释放空间后空间复杂度为 \(O(n\log n)\)，瓶颈是 ST 表，但是 vector 析构常数较大，因此我后来块长 \(B=1200\) 最快（析构次数不多），但还是卡不过去，于是把 vector 换成了指针分配内存，这样就直接预留好了内存，减少了 push_back 和析构的常数，卡过去了，当然我觉得这时块长应该调小一点
pii pool[(B + B + 10) * (B + B + 10)];
pii *ask[N];
inline int lca(int x, int y)
{
if(x == y) return x;
if(dfn[x] > dfn[y]) swap(x, y);
int l = dfn[x] + 1, r = dfn[y], v = lg[r - l + 1];
return dfn[rmq[v][l]] < dfn[rmq[v][r - (1 << v) + 1]] ? rmq[v][l] : rmq[v][r - (1 << v) + 1];
}
struct virtual_tree
{
vector<int> pnt; int fa[N], del[N], stk[N], top;
void clear()
{
for(int i : pnt) fa[i] = del[i] = 0;
fa[0] = del[0] = top = 0;
pnt.clear();
}
inline void ins(int x, const int &val, const int &fr)
{
for(; fa[x]; x = fa[x])
{
if(val > 0) ask[x][st[x]++] = {fr, -del[x]}, ask[fa[x]][st[fa[x]]++] = {-fr, -del[x]};
else ask[x][st[x]++] = {fr, -del[x] - val}, ask[fa[x]][st[fa[x]]++] = {-fr, -del[x] - val};
del[x] += val;
}
ask[x][st[x]++] = {fr, -del[x] - (val > 0 ? 0 : val)}, del[x] += val;
}
inline void build()
{
sort(p + 1, p + idx + 1, [&](const int x, const int y) -> int {return dfn[x] < dfn[y];});
idx = unique(p + 1, p + idx + 1) - (p + 1);
top = 0, stk[++top] = 1;
for(int i = 1; i <= idx; ++i)
{
int x = p[i];
if(x == 1) {pnt.pb(1); continue;}
int lc = lca(x, stk[top]); pnt.pb(x), pnt.pb(lc);
while(top > 1 && dfn[stk[top - 1]] > dfn[lc]) fa[stk[top]] = stk[top - 1], --top;
if(dfn[stk[top]] > dfn[lc]) fa[stk[top]] = lc, --top;
if(!top || stk[top] != lc) stk[++top] = lc;
stk[++top] = x;
}
sort(pnt.begin(), pnt.end()), pnt.resize(unique(pnt.begin(), pnt.end()) - pnt.begin());
for(int i = 2; i <= top; ++i) fa[stk[i]] = stk[i - 1];
sz = 0;
for(int x : pnt) ask[x] = pool + sz, sz += B + B + 5;
}
}vt;
void dfs(int x)
{
dfn[x] = ++cnt, rmq[0][cnt] = fa[x];
for(int y : edge[x]) dfs(y);
mxdfn[x] = cnt;
}
void Dfs(int x)
{
if(lim[x] <= n + 1) ++num[lim[x] + n + 1];
for(int j = 0; j < st[x]; ++j)
{
pii i = ask[x][j];
i.fi > 0 ? (sum[i.fi] += num[i.se + n + 1]) : (sum[-i.fi] -= num[i.se + n + 1]);
}
for(int y : edge[x]) Dfs(y);
if(lim[x] <= n + 1) --num[lim[x] + n + 1];
}
void DFS(int x)
{
siz[x] = vis[x] < 0 ? 1 : 0;
for(int y : edge[x]) DFS(y), siz[x] += siz[y];
lim[x] = vis[x] < 0 ? inf + t[x] - siz[x] + 1 : t[x] - siz[x] + 1;
}
inline void rebuild(const int x)
{
Dfs(1);
for(int i = 1; i <= n; ++i) clc[i] = st[i] = 0;
for(int i = x; i < x + B && i <= m; ++i)
{
int nw = q[i], res = lim[nw] > 1e7 ? lim[nw] - inf : lim[nw];
if(clc[nw]) continue;
clc[nw] = 1;
for(int j = x; j < x + B && j <= m; ++j)
{
int y = q[j], las = res;
if(dfn[y] >= dfn[nw] && dfn[y] <= mxdfn[nw]) res -= op[j];
if(y == nw)
{
vis[nw] = -vis[nw];
if((las <= 0 && vis[nw] == op[i]) || (res <= 0 && vis[nw] != op[i])) --sum[j];
}
else if(vis[nw] != op[i])
if((las <= 0 && res > 0) || (las > 0 && res <= 0)) sum[j] -= op[i];
}
}
for(int i = x; i < x + B && i <= m; ++i) ans[i] = ans[i - 1] + (op[i] > 0 ? sum[i] : -sum[i]);
DFS(1);
vt.clear();
}
int main()
{
read(n, m);
for(int i = 2; i <= n; ++i) read(fa[i]), edge[fa[i]].pb(i);
lg[0] = -1;
for(int i = 1; i <= n; ++i) read(t[i]), lim[i] = t[i] + 1, vis[i] = 1, lg[i] = lg[i >> 1] + 1;
for(int i = 1; i <= m; ++i) read(q[i]), op[i] = q[i] < 0 ? -1 : 1, q[i] = abs(q[i]);
dfs(1);
for(int j = 1; j <= 16; ++j)
for(int i = 1; i + (1 << j) - 1 <= n; ++i)
{
int ln = rmq[j - 1][i], rn = rmq[j - 1][i + (1 << (j - 1))];
rmq[j][i] = dfn[ln] < dfn[rn] ? ln : rn;
}
for(int i = 1; i <= m; i += B)
{
idx = 0;
for(int x = i; x <= m && x < i + B; ++x) p[++idx] = q[x];
vt.build();
for(int x = i; x <= m && x < i + B; ++x) vt.ins(q[x], -op[x], x);
rebuild(i);
}
for(int i = 1; i <= m; ++i) print(ans[i]), space();
fwrite(obuf, 1, ct, stdout);
return 0;
}
CF930E Coins Exhibition
难点在于不想容斥，骂的好，想到了就满脑子都是容斥
其实容斥硬分类讨论可以做，但太麻烦
肯定是得离散化，提出每段的端点
此时 naive 的想法是记录上一个 \(0\) 在第几段
但这种记录要考虑能否被只记录最后一段的状态，通过枚举转移点来替代
设 \(f(i,0/1/2)\) 表示第 \(i\) 段，这一段是全 \(0\)，全 \(1\)，有 \(0\) 且有 \(1\) 的方案数
\(f(i,2)\) 可以从前面任意状态转移，\(f(i,2)\gets (f(i-1,0)+f(i-1,1)+f(i-1,2))\times (2^{len}-2)\)
\(f(i,0)\) 则枚举上一个有 \(1\) 的段，这一段不能早于当前至少有一个 \(1\) 的段的最靠后的左端点，通过前缀和优化，\(f(i,0)\gets g(j,1)+g(j,2)\)
\(f(i,1)\) 同理
int main()
{
read(k, n, m);
for(int i = 1; i <= n; ++i) read(l[i], r[i]), lsh[++cnt] = l[i] - 1, lsh[++cnt] = r[i];
for(int i = n + 1; i <= n + m; ++i) read(l[i], r[i]), lsh[++cnt] = l[i] - 1, lsh[++cnt] = r[i];
lsh[++cnt] = 0, lsh[++cnt] = k, sort(lsh + 1, lsh + cnt + 1), cnt = unique(lsh + 1, lsh + cnt + 1) - (lsh + 1);
for(int i = 1; i <= n + m; ++i) lef[get(r[i])].pb({get(l[i] - 1), i > n});
f[1][2] = qzh[1][2] = 1, mnl[0] = mnl[1] = 0;
for(int i = 2; i <= cnt; ++i)
{ // f[i][0] lsh[i-1]+1~lsh[i] all 0 f[i][1] lsh[i-1]+1~lsh[i] all 1 f[i][2] lsh[i-1]+1~lsh[i] has 1 and 2
for(pii x : lef[i]) mnl[x.se] = max(mnl[x.se], x.fi);
f[i][2] = add(f[i - 1][0], f[i - 1][1], f[i - 1][2]) * add(qmi(2ll, lsh[i] - lsh[i - 1]), mod - 2) % mod;
f[i][0] = add(qzh[i - 1][1], qzh[i - 1][2], mod - qzh[mnl[1]][1], mod - qzh[mnl[1]][2]);
f[i][1] = add(qzh[i - 1][0], qzh[i - 1][2], mod - qzh[mnl[0]][0], mod - qzh[mnl[0]][2]);
qzh[i][0] = add(qzh[i - 1][0], f[i][0]), qzh[i][1] = add(qzh[i - 1][1], f[i][1]), qzh[i][2] = add(qzh[i - 1][2], f[i][2]);
}
cout << add(f[cnt][0], f[cnt][1], f[cnt][2]);
return 0;
}