近两日我放过的歌：
第一次：花之塔《莉可丽丝》；
第二次：前前前世《你的名字》；
第三次：心跳《侦探已死》。
都是一些动漫中的歌曲，简单征求一下大家对这些歌的评价。（虽然有些番我也没看完）
T1 吃粮
设 \(f_i\) 表示在 \(i\) 节点找到狗粮的期望时间，容易发现存在以下转移：
\[\begin{aligned} f_{i}&=a_i\ (deg_i=1)\\ f_{i}&=\tfrac{1}{deg_i}(\sum_v f_{v}+f_{fa})+a_i\ (deg_i\ne 1) \end{aligned} \]于是一种非常暴力的方法是直接高斯消元，复杂度 \(O(n^3q)\) 。
考虑进行优化，容易发现对于任意节点 \(i\) ， \(f_i=k_if_{fa}+b_i\) ，考虑求解 \(k _i,b_i\) ，对于 \(deg_i=1\) 的节点，显然有 \(k_i=0,b_i=a_i\) ，对于 \(deg_i\ne 1\) 的节点，我们有
\[\begin{aligned} f_{i}&=\tfrac{1}{deg_i}(\sum_{v}(k_vf_i+b_v)+f_{fa})+a_i\\ deg_if_i&=\sum_v(k_vf_i+b_v)+f_{fa}+deg_ia_i\\ (deg_i-\sum_vk_v)f_i&=f_{fa}+\sum_vb_v+deg_ia_i \end{aligned} \]比较显然
\[\begin{cases} k_i=\tfrac{1}{deg_i-\sum_vk_v}\\ b_i=\tfrac{\sum_vb_v+deg_ia_i}{deg_i-\sum_vk_v} \end{cases} \]考虑在根节点进行消元，发现式子形态几乎完全相同，实际上答案就是直接递推得到的 \(b_1\) 。
于是我们得到了一个 \(O(nq\log w)\) 的优秀做法。
考虑进一步优化，容易发现每次修改不会改变 \(k_i\) ，而每个节点 \(u\) 的 \(deg_ia_i\) 会通过 \(\prod k_v\) 的系数贡献到 \(b_1\) ，其中 \(v\) 是 \(u\) 的祖先，由于每次修改只会影响 \(O(1)\) 个节点，因此答案的变化可以 \(O(1)\) 计算。
code
#include <cstdio>
#include <vector>
using namespace std;
const int max1 = 1e5;
const int mod = 998244353;
int n, q, a[max1 + 5];
int degree[max1 + 5], f[max1 + 5], prod[max1 + 5], ans;
vector <int> edge[max1 + 5];
void Add ( int &x, int y )
{
x = x + y;
if ( x >= mod )
x = x - mod;
return;
}
int Quick_Power ( int base, int p )
{
int res = 1;
while ( p )
{
if ( p & 1 )
res = 1LL * res * base % mod;
p >>= 1;
base = 1LL * base * base % mod;
}
return res;
}
void Dfs ( int now, int fa )
{
degree[now] = edge[now].size();
f[now] = 0;
for ( auto v : edge[now] )
{
if ( v == fa )
continue;
Dfs(v, now);
Add(f[now], f[v]);
}
if ( degree[now] == 1 )
f[now] = 0;
else
f[now] = Quick_Power(( degree[now] - f[now] + mod ) % mod, mod - 2);
return;
}
void Redfs ( int now, int fa )
{
if ( degree[now] == 1 )
prod[now] = prod[fa];
else
{
prod[now] = 1LL * prod[fa] * f[now] % mod;
for ( auto v : edge[now] )
{
if ( v == fa )
continue;
Redfs(v, now);
}
}
return;
}
int main ()
{
freopen("satisfy.in", "r", stdin);
freopen("satisfy.out", "w", stdout);
scanf("%d", &n);
for ( int i = 1; i <= n; i ++ )
scanf("%d", &a[i]);
for ( int i = 1, u, v; i <= n - 1; i ++ )
{
scanf("%d%d", &u, &v);
edge[u].push_back(v);
edge[v].push_back(u);
}
Dfs(1, 0);
prod[0] = 1;
Redfs(1, 0);
ans = 0;
for ( int i = 1; i <= n; i ++ )
ans = ( ans + 1LL * a[i] * degree[i] % mod * prod[i] % mod ) % mod;
printf("%d\n", ans);
int u, x;
scanf("%d", &q);
while ( q -- )
{
scanf("%d%d", &u, &x);
ans = ( ans - 1LL * a[u] * degree[u] % mod * prod[u] % mod + mod ) % mod;
a[u] = x;
ans = ( ans + 1LL * a[u] * degree[u] % mod * prod[u] % mod ) % mod;
printf("%d\n", ans);
}
return 0;
}
T2 平衡
我们首先可以进行缩点，考虑对于每个点建立代价函数，由于绝对值函数下凸，因此缩完点之后代价函数仍然下凸，导数单调不降。
考虑用分治法求解答案，对于一段连续的值域，我们考虑哪些点存在最优方案满足权值 \(\ge mid\) ，发现如果选择了一个点，那么这个点的后继也一定要选，那么选择出的点一定是一个闭合子图，将每个点的权值定义为这个点在 \(mid\) 处的导数，那么实际上我们需要选择一个最小权闭合子图。
简单证明一下，考虑反证，设 \(S\) 为原图中的最小权闭合子图，假设存在 \(T\) 满足其中所有元素权值小于 \(mid\) 时更优，不难发现 \(T\) 必然是一个闭合子图，因此 \(S-T\) 也是一个闭合子图，由于 \(S\) 为最小权闭合子图，因此 \(T\) 的代价函数在 \(mid\) 处的导数小于 \(0\) ，容易发现将 \(T\) 的最优方案中所有点的权值整体变大，答案一定可行且不劣。
类似整体二分，每次网络流找最小权闭合子图即可。
code
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cassert>
#include <iostream>
using namespace std;
const int max1 = 500;
const long long inf = 0x3f3f3f3f3f3f3f3f;
struct Graph1
{
int sum_point, s, t, w[max1 + 5];
struct Node
{ int next, v; long long flow; } edge[max1 * max1 * 2 + max1 * 4 + 5];
int head[max1 + 5], now[max1 + 5], sum_edge;
int que[max1 + 5], L, R, dis[max1 + 5];
bool vis[max1 + 5];
void Clear ()
{ sum_point = sum_edge = 0; return; }
int Create ( int val )
{ head[++sum_point] = 0; w[sum_point] = val; return sum_point; }
void Add ( int u, int v, long long flow )
{
edge[++sum_edge].v = v;
edge[sum_edge].flow = flow;
edge[sum_edge].next = head[u];
head[u] = sum_edge;
return;
}
void Add_Edge ( int u, int v, long long flow )
{ return Add(u, v, flow), Add(v, u, 0); }
bool Bfs ()
{
for ( int i = 1; i <= sum_point; i ++ )
dis[i] = 0x3f3f3f3f;
L = R = 1;
que[R] = s;
dis[s] = 0;
while ( L <= R )
{
int x = que[L++];
now[x] = head[x];
if ( x == t )
return true;
for ( int i = head[x]; i; i = edge[i].next )
{
int v = edge[i].v;
long long flow = edge[i].flow;
if ( flow && dis[v] == 0x3f3f3f3f )
{
dis[v] = dis[x] + 1;
que[++R] = v;
}
}
}
return false;
}
long long Dfs ( int x, long long sum )
{
if ( x == t )
return sum;
long long res, k;
res = 0;
for ( int i = now[x]; i && sum; i = edge[i].next )
{
now[x] = i;
int v = edge[i].v;
long long flow = edge[i].flow;
if ( flow && dis[v] == dis[x] + 1 )
{
k = Dfs(v, min(sum, flow));
if ( !k )
dis[v] = 0x3f3f3f3f;
else
{
edge[i].flow -= k;
if ( i & 1 )
edge[i + 1].flow += k;
else
edge[i - 1].flow += k;
res += k;
sum -= k;
}
}
}
return res;
}
void Dfs ( int now )
{
vis[now] = true;
for ( int i = head[now]; i; i = edge[i].next )
{
int v = edge[i].v, flow = edge[i].flow;
if ( flow && !vis[v] )
Dfs(v);
}
return;
}
long long Dinic ( vector <int> &choose, vector <int> ¬_choose )
{
long long ans = 0;
while ( Bfs() )
ans += Dfs(s, inf);
choose.clear();
not_choose.clear();
for ( int i = 1; i <= sum_point; i ++ )
vis[i] = false;
Dfs(s);
for ( int i = 1; i <= sum_point; i ++ )
{
if ( w[i] )
{
if ( vis[i] )
choose.push_back(w[i]);
else
not_choose.push_back(w[i]);
}
}
return ans;
}
}graph1;
struct Graph2
{
#define lson(now) ( now << 1 )
#define rson(now) ( now << 1 | 1 )
int n, m1, m2, w[max1 + 5], save[max1 + 5], len;
vector <int> edge[max1 + 5], new_edge[max1 + 5], val[max1 + 5], point[max1 * 4 + 5];
int dfn[max1 + 5], low[max1 + 5], dfs_clock, s[max1 + 5], top, belong[max1 + 5], cnt;
bool in[max1 + 5], is_edge[max1 + 5][max1 + 5];
int Map[max1 + 5], color[max1 + 5];
void Tarjan ( int x )
{
dfn[x] = low[x] = ++dfs_clock;
s[++top] = x;
in[x] = true;
for ( auto v : edge[x] )
{
if ( !dfn[v] )
{ Tarjan(v); low[x] = min(low[x], low[v]); }
else if ( in[v] )
{ low[x] = min(low[x], dfn[v]); }
}
if ( dfn[x] == low[x] )
{
++cnt;
int tmp;
do
{
tmp = s[top--];
belong[tmp] = cnt;
val[cnt].push_back(w[tmp]);
in[tmp] = false;
} while ( tmp != x );
}
return;
}
long long Solve ( int now, int L, int R )
{
if ( point[now].empty() )
return 0LL;
if ( L == R )
{
long long ans = 0;
for ( auto u : point[now] )
for ( auto v : val[u] )
ans += abs(save[L] - v);
return ans;
}
int mid = ( L + R >> 1 ) + 1;
graph1.Clear();
graph1.s = graph1.Create(0);
graph1.t = graph1.Create(0);
for ( auto u : point[now] )
{
int x = 0;
for ( auto v : val[u] )
{
if ( v < save[mid] )
++x;
else
--x;
}
Map[u] = graph1.Create(u);
if ( x < 0 )
graph1.Add_Edge(graph1.s, Map[u], -x);
else
graph1.Add_Edge(Map[u], graph1.t, x);
}
for ( auto u : point[now] )
for ( auto v : new_edge[u] )
if ( color[u] == color[v] )
graph1.Add_Edge(Map[u], Map[v], inf);
graph1.Dinic(point[rson(now)], point[lson(now)]);
for ( auto u : point[lson(now)] )
color[u] = lson(now);
for ( auto u : point[rson(now)] )
color[u] = rson(now);
return Solve(lson(now), L, mid - 1) + Solve(rson(now), mid, R);
}
void Read ()
{
freopen("balance.in", "r", stdin);
freopen("balance.out", "w", stdout);
scanf("%d%d%d", &n, &m1, &m2);
for ( int i = 1; i <= n; i ++ )
scanf("%d", &w[i]), save[i] = w[i];
sort(save + 1, save + 1 + n);
len = unique(save + 1, save + 1 + n) - ( save + 1 );
for ( int i = 1; i <= n; i ++ )
{ edge[i].clear(); dfn[i] = in[i] = 0; }
dfs_clock = top = cnt = 0;
for ( int i = 1, u, v; i <= m1; i ++ )
{
scanf("%d%d", &u, &v);
edge[u].push_back(v);
edge[v].push_back(u);
}
for ( int i = 1, u, v; i <= m2; i ++ )
{
scanf("%d%d", &u, &v);
edge[u].push_back(v);
}
for ( int i = 1; i <= n; i ++ )
if ( !dfn[i] )
Tarjan(i);
for ( int i = 1; i <= cnt; i ++ )
for ( int j = 1; j <= cnt; j ++ )
is_edge[i][j] = false;
for ( int i = 1; i <= cnt; i ++ )
new_edge[i].clear();
for ( int u = 1; u <= n; u ++ )
{
for ( auto v : edge[u] )
{
int x = belong[u], y = belong[v];
if ( x == y || is_edge[x][y] )
continue;
new_edge[x].push_back(y);
is_edge[x][y] = true;
}
}
point[1].clear();
for ( int i = 1; i <= cnt; i ++ )
point[1].push_back(i), color[i] = 1;
printf("%lld\n", Solve(1, 1, len));
return;
}
}graph2;
int main ()
{ graph2.Read(); return 0; }
T3 枸杞
我们对每张图预处理 \(val_{i,j}\) 表示在第 \(i\) 张图走 \(j\) 步，每次可以选择走或不走， \(j\) 步后回到初始点的方案数，比较简单的方法是利用邻接矩阵直接求解，复杂度为 \(O(Tn^3\max(k))\) ，容易发现最后统计答案只需要知道这个矩阵对角线处的值即可，而两个矩阵相乘对对角线求和的复杂度是 \(O(n^2)\) 的，因此可以对每个邻接矩阵预处理光速幂，然后 \(O(n^2)\) 查询，复杂度为 \(O(Tn^3\sqrt{\max(k)}+Tn^2k)\) ，假设当前询问为 \(l,r,k\) ，考虑求解答案，设 \(f(i)=\prod_{t=l}^rval_{t,i}\) ，设 \(g(t)\) 表示恰好走 \(t\) 步，每一步均选择过一张图移动的方案数，根据二项式反演，容易得到 \(g(t)=\sum_{i=0}^t\binom{t}{i}(-1)^{t-i}f(i)\) 。
那么答案（包含一步都不走的贡献）就是：
\[\begin{aligned} \sum_{t=0}^kg(t) &=\sum_{t=0}^k\sum_{i=0}^t\binom{t}{i}(-1)^{t-i}f(i)\\ &=\sum_{i=0}^k f(i)\sum_{t=i}^k\binom{t}{i}(-1)^{t-i} \end{aligned} \]设 \(h(i,k)=\sum_{t=i}^k\binom{t}{i}(-1)^{t-i}\) ， \(O(\max(k)^2)\) 预处理 \(h\) ，就可以做到 \(O(k)\) 查询。
考虑预处理所有答案，根据答案计算式：
\[\begin{aligned} \sum_{t=0}^kg(t) &=\sum_{t=0}^k\sum_{i=0}^t\binom{t}{i}(-1)^{t-i}f(i)\\ &=\sum_{t=0}^kt!\sum_{i=0}^t\tfrac{(-1)^{t-i}}{(t-i)!}\tfrac{f(i)}{i!} \end{aligned} \]发现可以 NTT 预处理，复杂度 \(O(T^2\max(k)\log\max(k))\) 。
code
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <ctime>
using namespace std;
const int max1 = 30, max2 = 2e5, lim = 1e4, B = 100;
const int mod = 998244353, gmod = 3;
int T, q;
void Add ( int &x, int y )
{
x = x + y;
if ( x >= mod )
x = x - mod;
return;
}
int Quick_Power ( int base, int p )
{
int res = 1;
while ( p )
{
if ( p & 1 )
res = 1LL * res * base % mod;
p >>= 1;
base = 1LL * base * base % mod;
}
return res;
}
struct Matrix
{
int size;
unsigned long long matrix[max1 + 5][max1 + 5];
void Identity ( int __size )
{
size = __size;
for ( int i = 1; i <= size; i ++ )
for ( int j = 1; j <= size; j ++ )
matrix[i][j] = i == j;
return;
}
void Read ()
{
int m;
scanf("%d%d", &size, &m);
Identity(size);
for ( int i = 1, u, v; i <= m; i ++ )
{ scanf("%d%d", &u, &v); matrix[u][v] = matrix[v][u] = 1; }
return;
}
Matrix operator * ( const Matrix &A ) const
{
Matrix res;
res.size = size;
for ( int i = 1; i <= size; i ++ )
{
for ( int j = 1; j <= size; j ++ )
{
res.matrix[i][j] = 0;
for ( int k = 1; k <= size >> 1; k ++ )
res.matrix[i][j] += matrix[i][k] * A.matrix[k][j];
res.matrix[i][j] %= mod;
for ( int k = ( size >> 1 ) + 1; k <= size; k ++ )
res.matrix[i][j] += matrix[i][k] * A.matrix[k][j];
res.matrix[i][j] %= mod;
}
}
return res;
}
}Graph[max1 + 5];
struct Light_Speed_Power
{
int size;
Matrix power1[B + 5], power2[B + 5];
void Build ( const Matrix &A )
{
size = A.size;
power1[0].Identity(A.size);
power2[0].Identity(A.size);
for ( int i = 1; i <= B; i ++ )
power1[i] = power1[i - 1] * A;
for ( int i = 1; i <= B; i ++ )
power2[i] = power2[i - 1] * power1[B];
return;
}
int Query ( int x )
{
int a = x % B, b = x / B;
__int128_t ans = 0;
for ( int i = 1; i <= size; i ++ )
for ( int k = 1; k <= size; k ++ )
ans += 1LL * power1[a].matrix[i][k] * power2[b].matrix[k][i];
return ans % mod;
}
}power;
int prod[max1 + 5][lim + 5][2];
int inv[lim + 5], fac[lim + 5], ifac[lim + 5];
struct Question
{ int L, R, k; } qus[max2 + 5];
int maxk;
int bit, total, rev[lim * 4 + 5];
unsigned long long w[lim * 4 + 5], iw[lim * 4 + 5];
unsigned long long f[lim * 4 + 5], g[lim * 4 + 5];
void Iterative_NTT ( unsigned long long A[], unsigned long long w[],int type, int len )
{
for ( int i = 0; i < len; i ++ )
if ( i < rev[i] )
swap(A[i], A[rev[i]]);
for ( int mid = 2, t = len >> 1; mid <= len; mid <<= 1, t >>= 1 )
{
for ( int i = 0; i < len; i += mid )
{
for ( int k = 0; k < mid >> 1; k ++ )
{
unsigned long long x = A[i + k], y = w[t * k] * A[i + ( mid >> 1 ) + k] % mod;
A[i + k] = x + y;
A[i + ( mid >> 1 ) + k] = x - y + mod;
}
}
}
for ( int i = 0; i < len; i ++ )
A[i] %= mod;
return;
}
int ans[max1 + 5][max1 + 5][lim + 5];
void Solve ( int L, int R )
{
for ( int i = maxk + 1; i < total; i ++ )
f[i] = 0;
for ( int i = 0; i <= maxk; i ++ )
f[i] = 1LL * prod[R][i][0] * prod[L - 1][i][1] % mod * ifac[i] % mod;
Iterative_NTT(f, w, 1, total);
for ( int i = 0; i < total; i ++ )
f[i] = 1LL * f[i] * g[i] % mod;
Iterative_NTT(f, iw, -1, total);
int P = Quick_Power(total, mod - 2);
for ( int i = 0; i <= maxk; i ++ )
f[i] = 1LL * f[i] * P % mod;
ans[L][R][0] = f[0];
for ( int i = 1; i <= maxk; i ++ )
{
ans[L][R][i] = 1LL * f[i] * fac[i] % mod;
Add(ans[L][R][i], ans[L][R][i - 1]);
}
for ( int i = 1; i <= maxk; i ++ )
Add(ans[L][R][i], mod - 1LL * prod[R][0][0] * prod[L - 1][0][1] % mod);
return;
}
int main ()
{
freopen("cholferry.in", "r", stdin);
freopen("cholferry.out", "w", stdout);
scanf("%d", &T);
for ( int i = 1; i <= T; i ++ )
Graph[i].Read();
scanf("%d", &q);
maxk = 0;
for ( int i = 1; i <= q; i ++ )
scanf("%d%d%d", &qus[i].L, &qus[i].R, &qus[i].k), maxk = max(maxk, qus[i].k);
for ( int i = 0; i <= maxk; i ++ )
prod[0][i][0] = prod[0][i][1] = 1;
for ( int i = 1; i <= T; i ++ )
{
power.Build(Graph[i]);
for ( int j = 0; j <= maxk; j ++ )
{
prod[i][j][0] = 1LL * power.Query(j) * prod[i - 1][j][0] % mod;
prod[i][j][1] = Quick_Power(prod[i][j][0], mod - 2);
}
}
inv[1] = 1;
for ( int i = 2; i <= maxk; i ++ )
inv[i] = 1LL * ( mod - mod / i ) * inv[mod % i] % mod;
fac[0] = 1, ifac[0] = inv[1];
for ( int i = 1; i <= maxk; i ++ )
fac[i] = 1LL * fac[i - 1] * i % mod,
ifac[i] = 1LL * ifac[i - 1] * inv[i] % mod;
bit = 1, total = 2;
while ( total < maxk + maxk + 1 )
total <<= 1, ++bit;
rev[0] = 0;
for ( int i = 1; i < total; i ++ )
rev[i] = rev[i >> 1] >> 1 | ( i & 1 ) << bit - 1;
w[0] = 1; w[1] = Quick_Power(3, ( mod - 1 ) / total);
for ( int i = 2; i < total; i ++ )
w[i] = 1LL * w[i - 1] * w[1] % mod;
iw[0] = 1; iw[1] = Quick_Power(Quick_Power(3, mod - 2), ( mod - 1 ) / total);
for ( int i = 2; i < total; ++i )
iw[i] = 1LL * iw[i - 1] * iw[1] % mod;
for ( int i = 0; i <= maxk; i ++ )
{
if ( i & 1 )
g[i] = 1LL * ( mod - 1 ) * ifac[i] % mod;
else
g[i] = ifac[i];
}
Iterative_NTT(g, w, 1, total);
for ( int L = 1; L <= T; L ++ )
for ( int R = L; R <= T; R ++ )
Solve(L, R);
for ( int i = 1; i <= q; i ++ )
printf("%d\n", ans[qus[i].L][qus[i].R][qus[i].k]);
return 0;
}