A. Flip Flop Sum

枚举修改的位置。复杂度 \(O(n)\) 。

int a[N];
inline void work() {
    int n = rd(), sum = 0, dlt = -4;
    for (int i = 1; i <= n; ++i) {
        a[i] = rd(); sum += a[i];
        if (i > 1) dlt = max(dlt, -2 * (a[i] + a[i - 1]));
    }
    printf("%d\n", sum + dlt);
}

B. The Forbidden Permutation

枚举不符合要求的位置，移动有两种策略：

• 使 \(pos(a_i)\ge pos(a_{i + 1})\) ，操作次数 \(pos(a_{i+1})-pos(a_i)\)
• 使 \(pos(a_{i+1})>pos(a_i)+d\) ，需要保证 \(d+2\le n\) ，操作次数 \(pos(a_i)+d-pos(a_{i+1}) + 1\)

复杂度 \(O(n)\) 。

int p[N], a[N];
inline void work() {
    int n = rd(), m = rd(), d = rd(), ans = 1e9;
    rep(i, 1, n) p[rd()] = i;
    rep(i, 1, m) a[i] = rd();
    rep(i, 2, m) {
        if (p[a[i]] > p[a[i - 1]] && p[a[i]] <= p[a[i - 1]] + d) {
            ans = min(ans, p[a[i]] - p[a[i - 1]]);
            if (d + 2 <= n)ans = min(ans, d - (p[a[i]] - p[a[i - 1]]) + 1);
        } else {puts("0"); return;}
    }
    printf("%d\n", ans);
}

C. Flexible String

枚举修改的字符集，有 \({10\choose k}\) 种方案，然后 \(O(n)\) 计算在这些字符变成通配符的情况下答案的值。

#define N 100007

char s[N], t[N];

int a[N], n, k, tot;

map<char, int> id;

inline void work() {
    n = rd(); k = rd(); 
    tot = 0; id.clear();
    scanf("%s", s + 1);
    scanf("%s", t + 1);
    rep(i, 1, n) {
        if (!id[s[i]]) id[s[i]] = ++tot;
        a[i] = id[s[i]] - 1;
    }
    if (tot <= k) {
        printf("%lld\n", 1ll * n * (n + 1) / 2); 
        return;
    }

    ll ans = 0; 
    vector<int> ok(tot, 0);
    rep(i, 1, k) ok[tot - i] = 1;
    do {
        int len = 0;
        ll tmpans = 0;
        rep(i, 1, n) 
            if (ok[a[i]] || s[i] == t[i]) ++len;
            else {
                tmpans += 1ll * len * (len + 1) / 2; 
                len = 0;
            } 
        tmpans += 1ll * len * (len + 1) / 2;
        ans = max(ans, tmpans);
    } while(next_permutation(all(ok)));
    printf("%lld\n", ans);
}

D. Flexible String Revisit

首先一次操作只会让不同的个数 \(+1/-1\) ，所以只跟不同的个数有关，经典的 Markov 链，求首访时间。

设 \(t[i]\) 表示有 \(i\) 个不同的状态首次到达 \(0\) 状态的期望步数，有： \[ t[0]=0\\ t[i]=1+\frac{i}{n}\times t[i - 1] + \frac{n-i}{n}\times t[i+1],\ 1<i\le n \] 由于 \(t[0]=0\) 已知，所以先按照 \(i=0\dots n\) 的顺序扫描，把 \(t[i]\) 整理成只和 \(t[i+1]\) 有关的形式。

然后由于 \(t[n]\) 中到 \(t[n+1]\) 的系数 \(\frac{n-i}{n}=0\) ，所以 \(t[n]\) 的值已经求得，再逆着扫回来即可。

答案就是 \(t[\text{两字符串初始不同的位置数}]\) ，复杂度 \(O(n)\) 。

#define N 1000007
#define mod 998244353
 
inline int fpow(int x, int t = mod - 2) {
    int res = 1;
    for (; t; t >>= 1, x = 1ll * x * x % mod)
        if (t & 1) res = 1ll * res * x % mod;
    return res;
}
 
char s[N], t[N];
 
int f[N], dlt[N], k[N];
 
inline void calc(int n) {
    int bs = fpow(n);
    rep(i, 1, n) {
        int l = 1ll * i * bs % mod, r = 1ll * (n - i) * bs % mod;
        int cof = fpow((mod + 1 - 1ll * l * k[i - 1] % mod) % mod);
        dlt[i] = (1ll * dlt[i - 1] * l + 1) % mod * cof % mod;
        k[i] = 1ll * r * cof % mod;
    }
    f[n] = dlt[n];
    per(i, n - 1, 1) 
        f[i] = (dlt[i] + 1ll * f[i + 1] * k[i]) % mod;
}
 
inline void work() {
    int n = rd(); calc(n);
    scanf("%s", s + 1); scanf("%s", t + 1);
    int cnt = 0; rep(i, 1, n) cnt += (s[i] != t[i]);
    printf("%d\n", f[cnt]);
}

E. The Tree Has Fallen!

给一棵树 \((n\le 2\times 10^5)\) ，每个点有点权 \(a_u\ (a_u\le 10^9)\) ，\(q\ (q\le 2\times 10^5)\) 次询问：

树以 \(r_i\) 为根时，节点 \(v_i\) 子树内任选一些节点，点权异或最大值是多少？

看到询问肯定线性基了，先以 \(1\) 为根，处理出来每个点子树的线性基 \(subtree_u\) 。

询问讨论一下 \(r_i\) 和 \(v_i\) 的关系：

• \(r_i=v_i\) ，查询集合为全部点权，答案为 \(subtree_1\) 的表出最大值。
• \(r_i\) 不在 \(v_i\) 子树内，\(v_i\) 子树不变，则答案为 \(subtree_{v_i}\) 的表出最大值。
• \(r_i\) 在 \(v_i\) 子树内，则查询集合为所有点删掉 \(v_i\) 的包含 \(r_i\) 的儿子的子树。

因此需要完成：

• 查询 \(v_i\) 儿子中，包含 \(r_i\) 的是谁。
• 处理 \(out_u\) 表示删掉 \(u\) 子树的线性基。

这两个问题求 dfs 序后都可以解决，由于子树 dfs 序连续：

第一个对每个点记录所有儿子的 dfn ，然后在里面二分查找 \(\le dfn[r_i]\) 的最大的。

第二个处理按 dfs 序的前后缀线性基，再左右合并即可。

复杂度 \(O(n\log^2(\max a_u))\) 。

#define N 200007

struct linear_base {
    
    #define D 31
    
    int b[D];
    
    void clear() {memset(b, 0, sizeof(b));}
    
    void insert(int x) {
        for (int i = 30; ~i; --i)
            if ((x >> i) & 1) {
                if (b[i]) x ^= b[i];
                else {b[i] = x; break;}
            }
    }

    int max_xor() {
        int ans = 0;
        for (int i = 30; ~i; --i)
            if (b[i] && !((ans >> i) & 1)) ans ^= b[i];
        return ans;
    }

    linear_base operator + (const linear_base &obj) const {
        linear_base ret = obj;
        for (int i = 30; ~i; --i)
            if (b[i]) ret.insert(b[i]);
        return ret;
    }

} pre[N], suf[N], subtree[N], out[N];

int dfn[N], id[N], lst[N], a[N], tot;

vector<int> e[N], sondfn[N];

void dfs(int u, int fa) {
    sondfn[u].clear();
    subtree[u].clear();
    subtree[u].insert(a[u]);
    id[dfn[u] = ++tot] = u;
    for (auto v : e[u])
        if (v != fa) {
            dfs(v, u);
            subtree[u] = subtree[u] + subtree[v];
            sondfn[u].pb(dfn[v]);
        } 
    lst[u] = tot;
}

inline void work() {
    tot = 0;
    int n = rd();
    rep(i, 1, n) {a[i] = rd(); e[i].clear();}
    rep(i, 2, n) {int u = rd(), v = rd(); e[u].pb(v); e[v].pb(u);}
    
    dfs(1, 1);
    pre[0].clear(); suf[n + 1].clear();
    rep(i, 1, n) {pre[i] = pre[i - 1]; pre[i].insert(a[id[i]]);}
    per(i, n, 1) {suf[i] = suf[i + 1]; suf[i].insert(a[id[i]]);}
    rep(i, 1, n) out[i] = pre[dfn[i] - 1] + suf[lst[i] + 1];
    
    per(i, rd(), 1) {
        int r = rd(), v = rd();
        if (r == v) printf("%d\n", subtree[1].max_xor());
        else if (dfn[v] < dfn[r] && dfn[r] <= lst[v]) {
            int son = id[*--upper_bound(all(sondfn[v]), dfn[r])];
            printf("%d\n", out[son].max_xor());
        } else printf("%d\n", subtree[v].max_xor());
    }
}

F. Maximizing Root

以 \(1\) 为根的树，每个节点有点权 \(a_u\ (a_u\le 10^3)\) ，最多 \(k\ (0\le k\le n\le 10^5)\) 次操作，每次操作：

• 选一个此前未选过的点 \(v\) ， 选择一个 \(v\) 子树内所有点权的公因数 \(x\) ，令 \(v\) 子树内所有点权 \(\times x\) 。

问最终 \(1\) 号点点权可能的最大值。

首先每个点只能操作一次，所以 \(a_1\) 最终最大变成 \(a_1^2\) 。

所以我们只需要考虑每个点的子树，在祖先节点操作时，保证子树内能提供 \(x\ (x\le 1000)\) 所需的最小次数。

因此设 \(f[u][x]\) 表示节点 \(u\) 子树内，后续祖先操作时，保证 \(u\) 子树内能提供 \(x\) 的最小操作次数。

• 若不操作 \(u\) ，则需要保证 \(x|a[u]\) ，此时方程为 \(f[u][x] = \sum f[son][x]\) 。
• 若操作 \(u\) ，此时需要找到某个最小的 \(y\) ，使得 \(x|y^2\) ，也就是子树里每个点都包含 \(y\) 的情况下，操作一次 \(u\) 足以让整个子树都包含 \(x\) ，这个预处理即可，称 \(y\) 为 \(mn[x]\) ，方程为 \(f[u][x]=1+\sum f[son][mn[x]]\) 。
• 此外，如果 \(mn[x]\) 不是 \(a[u]\) 的因数，则 \(f[u][x]\) 不合法。

最后枚举 \(1\) 号点操作时对应的 \(x\) 是几即可，复杂度 \(O(n\max a_u)\) 计算量约 \(10^8\) 。

#define N 100007

int f[N][1001], a[N], G, n, k, inf = 1e9;
 
vector<int> e[N];
 
int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}
 
inline void getmin(int &a, int b) {a = (a > b ? b : a);}
 
int mn[1001];
 
void dfs(int u, int fa) {
    for (auto v : e[u]) if (v != fa) dfs(v, u);
    f[u][1] = 0;
    rep(i, 2, 1000) {
        if (a[u] % i == 0) {
            f[u][i] = 0;
            for (auto v : e[u])
                if (v != fa) {f[u][i] += f[v][i]; getmin(f[u][i], inf);}
            int tmp = 1, tar = mn[i];
            for (auto v : e[u])
                if (v != fa) {tmp += f[v][tar]; getmin(tmp, inf);}
            getmin(f[u][i], tmp);
        } else if (a[u] % mn[i] == 0) {
            f[u][i] = 1;
            int tar = mn[i];
            for (auto v : e[u])
                if (v != fa) {f[u][i] += f[v][tar]; getmin(f[u][i], inf);}
        } else f[u][i] = inf;
    }
}
 
inline void work() {
    int n = rd(), k = rd(); G = 0;
    rep(i, 1, n) {a[i] = rd(); G = gcd(G, a[i]); e[i].clear();}
    rep(i, 2, n) {int u = rd(), v = rd(); e[u].pb(v); e[v].pb(u);}
    if (k == 0 || G == 1) {printf("%d\n", a[1]); return;}
    if (k == 1) {printf("%d\n", a[1] * G); return;}
    dfs(1, 1);
    per(i, a[1], 1)
        if (a[1] % i == 0) {
            int cnt = 0;
            for (auto v : e[1]) {
                cnt += f[v][i];
                getmin(cnt, inf);
            }
            if (cnt < k) {printf("%d\n", a[1] * i); return;}
        }
}   
 
int main() {
    rep(i, 1, 1000) rep(j, 1, 1000) if (j * j % i == 0) {mn[i] = j; break;}
    for (int t = rd(); t; --t) work();
    return 0;
}