我是越来越摆了，一下午就改了一道题；而且这么菜，看了半天的题解做法还没看懂。又是被暴踩的一天。
T1 树染色
比较套路的想法是考虑当前以 \(u\) 为根的子树，考虑第一次选择 \(u\) 子树内的叶节点，此时我们必须选择 \(u\) 以上的节点作为链顶，这会对方案数产生贡献。
考虑通过第一条链划分子问题，设第一条链经过 \(u\) 的儿子为 \(v\) ，此时 \(u\) 子树选择的第一条链相当于在 \(v\) 子树内选择的第一条链，对于 \(u\) 的其他儿子，这条链不会影响其子树内的决策，但是可以确定其子树内选择的第一条链的链顶方案数产生的贡献。
设 \(f_{u,0/1}\) 表示当前考虑以 \(u\) 为根的子树，不考虑当前子树内第一条链的链顶方案数产生的贡献，第一条链颜色为黑 / 白时，子树的美观度之和。
转移考虑枚举 \(u\) 子树内第一条链经过 \(u\) 的儿子 \(v\) ，同时计算链之间的顺序关系造成的贡献，设 \(leaf_u\) 为 \(u\) 子树内叶节点的数量，那么有：
\[f_{u,0}=\sum_{v}f_{v,0}(\prod_{p\ne v}(a_if_{p,0}+b_if_{p,1})deep_u)(leaf_u-1)!(\prod_{p}\tfrac{1}{(leaf_p-[v=p])!})
\]
直接 dp 即可。
code
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cassert>
using namespace std;
const int max1 = 5e5;
const int mod = 998244353;
int n;
struct Node
{
int v, A, B;
Node () {}
Node ( int __v, int __A, int __B )
{ v = __v, A = __A, B = __B; }
};
vector <Node> edge[max1 + 5];
int inv[max1 + 5], fac[max1 + 5], ifac[max1 + 5];
int leaf[max1 + 5], f[max1 + 5][2], g[max1 + 5][2];
int prod[max1 + 5][2];
void Dfs ( int now, int fa, int depth )
{
for ( auto p : edge[now] )
if ( p.v != fa )
Dfs(p.v, now, depth + 1);
int son = 0; leaf[now] = 0;
for ( auto p : edge[now] )
{
if ( p.v == fa )
continue;
++son;
prod[son][0] = prod[son][1] = (1LL * p.A * f[p.v][0] + 1LL * p.B * f[p.v][1]) % mod * ifac[leaf[p.v]] % mod;
leaf[now] += leaf[p.v];
}
if ( !son )
{
leaf[now] = 1;
f[now][0] = f[now][1] = depth;
g[now][0] = g[now][1] = 1;
}
else
{
prod[0][0] = prod[son + 1][1] = 1;
for ( int i = 1; i <= son; i ++ )
prod[i][0] = 1LL * prod[i - 1][0] * prod[i][0] % mod;
for ( int i = son; i >= 1; i -- )
prod[i][1] = 1LL * prod[i + 1][1] * prod[i][1] % mod;
f[now][0] = f[now][1] = g[now][0] = g[now][1] = son = 0;
for ( auto p : edge[now] )
{
if ( p.v == fa )
continue;
++son;
g[now][0] = (g[now][0] + 1LL * p.A * g[p.v][0] % mod * prod[son - 1][0] % mod * prod[son + 1][1] % mod * ifac[leaf[p.v] - 1] % mod * fac[leaf[now] - 1]) % mod;
g[now][1] = (g[now][1] + 1LL * p.B * g[p.v][1] % mod * prod[son - 1][0] % mod * prod[son + 1][1] % mod * ifac[leaf[p.v] - 1] % mod * fac[leaf[now] - 1]) % mod;
f[now][0] = (f[now][0] + 1LL * p.A * g[p.v][0] % mod * depth % mod * prod[son - 1][0] % mod * prod[son + 1][1] % mod * ifac[leaf[p.v] - 1] % mod * fac[leaf[now] - 1]) % mod;
f[now][1] = (f[now][1] + 1LL * p.B * g[p.v][1] % mod * depth % mod * prod[son - 1][0] % mod * prod[son + 1][1] % mod * ifac[leaf[p.v] - 1] % mod * fac[leaf[now] - 1]) % mod;
}
}
return;
}
int main ()
{
freopen("treecolor.in", "r", stdin);
freopen("treecolor.out", "w", stdout);
scanf("%d", &n);
for ( int i = 2, x, y, A, B; i <= n; i ++ )
{
scanf("%d%d%d%d", &x, &y, &A, &B);
edge[x].push_back(Node(y, A, B));
edge[y].push_back(Node(x, A, B));
}
inv[1] = 1;
for ( int i = 2; i <= n; i ++ )
inv[i] = 1LL * (mod - mod / i) * inv[mod % i] % mod;
fac[0] = ifac[0] = 1;
for ( int i = 1; i <= n; i ++ )
{
fac[i] = 1LL * fac[i - 1] * i % mod;
ifac[i] = 1LL * ifac[i - 1] * inv[i] % mod;
}
Dfs(1, 0, 0);
printf("%d\n", (g[1][0] + g[1][1]) % mod);
return 0;
}
T2 关路灯
首先考虑询问给定 \([L,R,s]\) 如何处理，一个比较显然的想法是一次跳完一整个方向，设当前节点为 \(now\) ，前驱为 \(pre\) ，后继为 \(suf\) ，不妨设 \(x_{now}-x_{pre}>x_{suf}-x_{now}\) ，那么此时我们一定需要向后跳，比较自然的想法是找到 \(suf\) 后第一个点 \(i\) ，满足 \(x_{i+1}-x_{i}>x_{now}-x_{pre}\) ，那么到达点 \(i\) 后，我们可能转向，考虑再进行一步操作，最终移动到的位置只可能是 \(pre\) 或 \(i+1\) ，设 \(p\) 为当前点与前驱，后继距离的较大值，容易发现 \(p\) 翻倍了。循环进行这个过程，那么当前点的移动会被划分为 \(O(\log w)\) 次移动。
考虑处理 \([L,R]\) 内每个点对当前询问的贡献，比较显然的是每个点都会在一个时刻第一次到达左右端点，此时进行的操作就是从当前端点跳到另一个端点，如果我们可以统计每个点在这个时刻的贡献，那么答案也就不难计算了。
直接预处理每个点到达 \(1\) 或 \(n\) 的所有移动，由于一个点会被拆分为 \(O(\log w)\) 次移动，设第 \(i\) 次移动当前点控制的区间为 \([L,R]\) ，不难发现一次移动只会改变 \([L,R]\) 中一个指针，假设当前点首先触碰到询问的右端点，那么这个时刻一定发生在控制区间右端点的移动过程中，具体来讲就是第一个包含当前询问右端点的区间，当然由于当前点可能先触碰到左端点，因此需要检查当前点对应的区间左端点 \(L\) 是否大于询问左端点。
显然有一种扫描线的思路，以统计先触碰到询问右端点的点的贡献为例，实现的操作就是在当前点控制区间右端点移动过程中删除上一个区间，插入下一个区间，统计所有满足控制区间左端点大于询问左端点的点的贡献。
code
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int max1 = 1e5, max2 = 3e5;
int n, m, x[max1 + 5];
struct Question
{
int pos, id;
Question () {}
Question ( int __pos, int __id )
{ pos = __pos, id = __id; }
};
vector <Question> qusL[max1 + 5], qusR[max1 + 5];
long long ans[max2 + 5];
struct Option
{
int pos;
long long val;
Option () {}
Option ( int __pos, long long __val )
{ pos = __pos, val = __val; }
};
vector <Option> optL[max1 + 5], optR[max1 + 5];
struct ST_List
{
int list[max1 + 5][20];
void Build ()
{
list[1][0] = 0x3f3f3f3f;
for ( int i = 2; i <= n; i ++ )
list[i][0] = x[i] - x[i - 1];
for ( int k = 1; (1 << k) <= n; k ++ )
for ( int i = 1; i + (1 << k) - 1 <= n; i ++ )
list[i][k] = max(list[i][k - 1], list[i + (1 << (k - 1))][k - 1]);
}
int Query_Front ( int now, int x )
{
for ( int i = 20; i >= 0; i -- )
if ( now - (1 << i) + 1 >= 1 && list[now - (1 << i) + 1][i] < x )
now -= 1 << i;
return now;
}
int Query_Back ( int now, int x )
{
for ( int i = 20; i >= 0; i -- )
if ( now + (1 << i) - 1 <= n && list[now][i] < x )
now += 1 << i;
return now;
}
}ST;
struct Data
{
long long sum;
int cnt;
Data () {}
Data ( long long __sum, int __cnt )
{ sum = __sum, cnt = __cnt; }
Data operator + ( const Data &A ) const
{ return Data(sum + A.sum, cnt + A.cnt); }
Data operator - ( const Data &A ) const
{ return Data(sum - A.sum, cnt - A.cnt); }
};
struct Bit
{
#define lowbit(now) ( now & -now )
Data tree[max1 + 5];
void Build ()
{
for ( int i = 0; i <= n; i ++ )
tree[i] = Data(0LL, 0);
return;
}
void Insert ( int now, const Data &x )
{
while ( now <= n )
{
tree[now] = tree[now] + x;
now += lowbit(now);
}
return;
}
Data Query ( int now )
{
Data res = Data(0LL, 0);
while ( now )
{
res = res + tree[now];
now -= lowbit(now);
}
return res;
}
Data Query ( int L, int R )
{
return Query(R) - Query(L - 1);
}
}Tree;
int main ()
{
freopen("light.in", "r", stdin);
freopen("light.out", "w", stdout);
scanf("%d%d", &n, &m);
for ( int i = 1; i <= n; i ++ )
scanf("%d", &x[i]);
for ( int i = 1, L, R; i <= m; i ++ )
{
scanf("%d%d", &L, &R); ans[i] = 1LL * ( R - L + 1 ) * ( x[R] - x[L] );
if ( L != R )
{
if ( R - L != 1 )
{
qusR[R].push_back(Question(L, i));
qusL[L].push_back(Question(R, i));
}
}
}
ST.Build();
for ( int i = 1; i <= n; i ++ )
{
int L = i, R = i, now = i; long long sum = 0;
while ( true )
{
if ( L == 1 || R == n )
break;
int pre = x[now] - x[L - 1], suf = x[R + 1] - x[now];
if ( pre < suf )
{
int p = ST.Query_Front(L, suf);
optL[L - 1].push_back(Option(R, sum + x[now]));
optL[p - 1].push_back(Option(-R, sum + x[now]));
sum += x[now] - x[p];
L = now = p;
}
else
{
int p = ST.Query_Back(R + 1, pre + 1) - 1;
optR[R + 1].push_back(Option(L, sum - x[now]));
optR[p + 1].push_back(Option(-L, sum - x[now]));
sum += x[p] - x[now];
R = now = p;
}
}
}
Tree.Build();
for ( int i = 1; i <= n; i ++ )
{
for ( auto v : optR[i] )
{
if ( v.pos > 0 )
Tree.Insert(v.pos, Data(v.val, 1));
else
Tree.Insert(-v.pos, Data(-v.val, -1));
}
for ( auto v : qusR[i] )
{
Data d = Tree.Query(v.pos + 1, n);
ans[v.id] += d.sum + 1LL * d.cnt * x[i];
}
}
Tree.Build();
for ( int i = n; i >= 1; i -- )
{
for ( auto v : optL[i] )
{
if ( v.pos > 0 )
Tree.Insert(v.pos, Data(v.val, 1));
else
Tree.Insert(-v.pos, Data(-v.val, -1));
}
for ( auto v : qusL[i] )
{
Data d = Tree.Query(1, v.pos - 1);
ans[v.id] += d.sum - 1LL * d.cnt * x[i];
}
}
for ( int i = 1; i <= m; i ++ )
printf("%lld\n", ans[i]);
return 0;
}
T3 树状数组
考虑 dp ，设 \(f_{i,j,k}\) 表示当前考虑 \(a\) 序列前 \(i\) 个数，当前生成的 \(x\) 从 \(R\) 的第 \(j\) 位开始失配，失配位后面存在 \(k\) 个位置为 \(1\) 的方案数。
先考虑统计答案，容易发现比较大小的过程实质上就是取出当前两个数的二进制 lcp ，比较下一位的大小即可，因此这样设计状态可以直接计算答案。
考虑转移，如果 \(a_i=0\) ，如果 \(k\ne 0\) ，显然转移到 \(f_{i,j,k-1}\) ，如果 \(k=0\) ，容易发现此时 \(x\) 是可以唯一确定的，因此直接对 \(x\) 进行操作，暴力求解转移到的状态即可； \(a_i=1\) 同理。
钦定 \(a_i=0\) 只需要预处理前后缀 dp 直接拼接即可。
code
#include <cstdio>
#include <algorithm>
using namespace std;
const int max1 = 1e5, max2 = 20;
const int mod = 998244353;
int n, k, lim;
char s[max1 + 5];
int id[max2 + 5][max2 + 5], total;
int trans[max2 * max2 + 5][2];
int f[max1 + 5][max2 * max2 + 5], g[max1 + 5][max2 * max2 + 5];
#define lowbit(x) (x & -(x))
int Option0 ( int x )
{
return x - lowbit(x);
}
int Option1 ( int x )
{
return x + lowbit((1 << k) - 1 - x);
}
int Find ( int x )
{
for ( int i = k - 1; i >= 0; i -- )
if ( ((x ^ lim) >> i) & 1 )
return id[i][__builtin_popcount(x & ((1 << i) - 1))];
return 0;
}
void Add ( int &x, int y )
{
x += y;
if ( x >= mod )
x -= mod;
return;
}
int main ()
{
freopen("fenwick.in", "r", stdin);
freopen("fenwick.out", "w", stdout);
scanf("%d%d%d%s", &n, &k, &lim, s + 1);
for ( int i = 0; i < k; i ++ )
for ( int j = 0; j <= i; j ++ )
id[i][j] = ++total;
for ( int i = 0; i < k; i ++ )
{
for ( int j = 0; j <= i; j ++ )
{
if ( !j )
trans[id[i][j]][0] = Find(Option0(((lim >> i) ^ 1) << i));
else
trans[id[i][j]][0] = id[i][j - 1];
if ( j == i )
trans[id[i][j]][1] = Find(Option1((((lim >> i) ^ 1) << i) | ((1 << i) - 1)));
else
trans[id[i][j]][1] = id[i][j + 1];
}
}
trans[Find(lim)][0] = Find(Option0(lim));
trans[Find(lim)][1] = Find(Option1(lim));
f[0][Find(0)] = 1;
for ( int i = 1; i <= n; i ++ )
{
for ( int S = 0; S <= total; S ++ )
{
if ( s[i] != '1' )
Add(f[i][trans[S][0]], f[i - 1][S]);
if ( s[i] != '0' )
Add(f[i][trans[S][1]], f[i - 1][S]);
}
}
for ( int i = 0; i <= lim; i ++ )
g[n + 1][Find(i)] = 1;
for ( int i = n; i >= 1; i -- )
{
for ( int S = 0; S <= total; S ++ )
{
if ( s[i] != '1' )
Add(g[i][S], g[i + 1][trans[S][0]]);
if ( s[i] != '0' )
Add(g[i][S], g[i + 1][trans[S][1]]);
}
}
for ( int i = 1; i <= n; i ++ )
{
if ( s[i] == '1' )
puts("0");
else
{
int ans = 0;
for ( int S = 0; S <= total; S ++ )
Add(ans, 1LL * f[i - 1][S] * g[i + 1][trans[S][0]] % mod);
printf("%d\n", ans);
}
}
return 0;
}