T1 寿司餐厅

Description

太长了挂个链接算惹

Solution

就拿这个题来梳理一下网络流中的最大权闭合子图模型吧。

用最小割，我们先要定义好某个点在残量网络中与源点相连的意义。在最大权闭合子图模型中，我们认为某点 $x$ 与源点在残量网络中未被割去，则该点最后会选在闭合子图中，反之则不会。所以可得：

• 源点向正权点连边，容量即为点权。
• 负权点向汇点连边，容量为点权的相反数。
• 原图中的边容量为 INF 。因为一选俱选。

这样跑出来的最小割表示应去除的贡献和应加上的代价。用总正权值减去之就好了。

如果把区间看成点，这个题实际上就是最大权闭合子图——选择大区间必须选择小区间，而选择小区间不必选择大区间。只不过每个长度为 $1$ 的区间额外有代价而已。对于选择多个但至多计算一次的 $x^2$ ，我们可以对于特定的代号建个节点，专门表示这个贡献。

然后直接跑最大流就行啦。

做这个题关键要看出来「物品」究竟是什么。不应是一个个「寿司」，而是一个「寿司区间」。

Code

const int I = 1e3 + 5, N = 2e4, M = 6e4;
using namespace std;
int n, m, S, T, num = 1;
int a[I], cnt[I], d[I][I];
int head[N], nt[M], to[M], cap[M], lab[N];
bool BFS(){
    for(int i = S; i <= T; ++i) lab[i] = 0;
    queue<int>q;q.push(S);lab[S] = 1;
    while (!q.empty()){
        int u = q.front();q.pop();
        for(int i = head[u];i; i = nt[i]){
            int v = to[i];
            if(!cap[i] or lab[v]) continue;
            lab[v] = lab[u] + 1, q.push(v);
            if(v == T) return true;
        }
    }
    return false;
}
int dinic(int p, int flow){
    if(p == T) return flow;
    int res = flow;
    for(int i = head[p]; i and res; i = nt[i]){
        int v = to[i];
        if(!cap[i] or lab[v] != lab[p] + 1) continue;
        int k = dinic(v, min(res, cap[i]));
        if(!k) lab[v] = 0;
        else res -= k, cap[i] -= k, cap[i ^ 1] += k;
    }
    return flow - res;
}
void Add(int x, int y, int z){
    ++num, nt[num] = head[x], head[x] = num, to[num] = y, cap[num] = z;
    ++num, nt[num] = head[y], head[y] = num, to[num] = x, cap[num] = 0;
}
int id(int i, int j){return (i - 1) * n + j;}
int main(){

    r(n, m);
    for(int i = 1; i <= n; ++i) r(a[i]), ++cnt[a[i]];
    for(int i = 1; i <= n; ++i)
    for(int j = i; j <= n; ++j)
        r(d[i][j]);
    S = 0, T = n * n + 1001;
    int ans = 0;
    for(int i = 1; i <= n; ++i)
    for(int j = i + 1; j <= n; ++j){
        int now = id(i, j); 
        Add(now, id(i + 1, j), oo);
        Add(now, id(i, j - 1), oo);
        if(d[i][j] > 0) Add(S, now, d[i][j]), ans += d[i][j];
        else Add(now, T, -d[i][j]);
    }
    for(int i = 1, now; i <= n; ++i){
        now = id(i, i);
        Add(now, n * n + a[i], oo);
        Add(now, T, a[i]);
        if(d[i][i] > 0) Add(S, now, d[i][i]), ans += d[i][i];
        else Add(now, T, -d[i][i]);
    }
    for(int i = 1; i <= 1e3; ++i)
        if(cnt[i])
            Add(n * n + i, T, m * i * i);
    int flow = 0;
    while(BFS())
        while(flow = dinic(S, oo)) ans -= flow;
    w(ans);
    return 0;
}

T2 期末考试

Description

懒得写挂个链接算惹

Solution

乍一看以为是 DP ，因为如果求出满足所有课程都在 $t$ 时刻以前的最小不满意度之和 f[p] ，结合一下学生的要求就可以轻易得到答案。
冷静分析一手，发现在确定要求时间下让移动课程的不满意度之和最小似乎可以直接贪心。也就是分析一下 A 和 B 的大小关系就可以了。然后各种时间什么的可以做前缀和优化一下。复杂度 $\mathcal{O}(n\log_2n)$ 。

Code

const int N = 1e5 + 5;
using namespace std;
int n, m, a[N], b[N];
unsigned long long A, B, C, sa[N], sb[N]; 
int main(){

    r(A, B, C, n, m);
    for(int i = 1; i <= n; ++i) r(a[i]);
    for(int i = 1; i <= m; ++i) r(b[i]);
    sort(a + 1, a + n + 1);
    sort(b + 1, b + m + 1);
    for(int i = 1; i <= n; ++i) sa[i] = sa[i - 1] + a[i];
    for(int i = 1; i <= m; ++i) sb[i] = sb[i - 1] + b[i];
    unsigned long long ans = 1e19; 
    for(int i = 1, nowa = 0, nowb = 0; i <= 1e5; ++i){
        while(nowa < n and a[nowa + 1] == i) ++ nowa;
        while(nowb < m and b[nowb + 1] == i) ++ nowb;
        unsigned long long tot = (- sa[nowa] + 1ull * nowa * i) * C;
        if(A >= B)
            tot += (sb[m] - sb[nowb] - 1ull * (m - nowb) * i) * B;
        else{
            unsigned long long t1 = 1ull * nowb * i - sb[nowb], t2 = sb[m] - sb[nowb] - 1ull * (m - nowb) * i;
            tot += min(t1, t2) * A;
            if(t2 > t1) tot += (t2 - t1) * B;
        }
        ans = min(ans, tot);
    }
    w(ans);
    return 0;
}

T3 组合数问题

Description

给定 $n, p, k, r$ ，求下式的值：

$(\sum_{i=0}^{\infin}\binom{ik+r}{nk}) \mod{p}$

$1\leq n \leq 10^9,0\leq r < k\leq 50,2\leq p\leq 2^{30}-1$

Solution

做组合数题目常用的 trick 就是先找组合意义变为具体的一个问题，再尝试求递推式。
本题的组合含义就是在 $nk$ 个物品中选出 $x$ 个物品（满足 $x\equiv r\pmod{k}$ ）的方案数。
设 f[i][j] 表示在 $i$ 个物品中选出 $\text{mod }k$ 意义下的 $j$ 个物品的方案数。递推式就是组合数递推式。转移可以用矩阵乘法来优化。并且这个矩阵是循环矩阵，可以进一步优化。
复杂度 $\mathcal{O}(k^2\log_2n)$ 。

Code

const int K = 55;
using namespace std;
long long n , p, k, r;
struct matrix{
	long long x[K];
	void clear(){memset(x, 0, sizeof x);}
	matrix operator *(const matrix &b){
		matrix d;d.clear();
		for(int i = 0; i < k; ++i)
		for(int j = 0; j < k; ++j)
			d.x[(i + j) % k]=(d.x[(i + j) % k] + (x[i] * b.x[j]) % p) % p;
		return d;
	}
}s, f;
int main(){
	
	cin>> n >> p >> k >>r;
	if(k != 1)
		s.x[0] = s.x[k - 1] = 1;
	else s.x[0]=2 % p;
	f.x[0] = 1;
	long long t = n * k;
	while(t)
		f=(t & 1) ? f * s : f, t >>= 1, s = s * s;
	cout<< f.x[r] << endl;
	return 0;
}	

T4 分手是祝愿

Description

太长了挂个链接算惹

Solution

首先有一个重要性质：每一个按钮都是独一无二，不可被其他按钮组合起来取代的。
这个性质有点意思，对于删去因数/倍数的题目都是如此。所以说做这种带有 「选择」性质的东西，要记得考虑每种选择是否是独特的，如果不是，那么何种情况下可以被取代。
那么从大到小枚举可以预处理出所有必须选的按钮，剩下的就是必须不选的。
问题转化为了子问题：$n$ 个按钮，每次随机按一个，必须按中某 $m$ 个，求期望次数。
设 f[p] 表示从必须按 $p$ 次到必须按 $p-1$ 次的期望次数，则有

$f_p = \frac{p}{n} + \frac{n-p}{n}(f_{p+1} + f_{p} + 1)$

毕竟如果按错了还得按回来。
然后就转化成了一个关于 f[p] 的递推式，暴力求就好了。$k$ 的限制讨论一下就行了。
复杂度 $\mathcal{O}(n\log_2n)$ 。

const int N = 1e5 + 5, mod = 1e5 + 3;
using namespace std;
int n, k, tot;
int a[N], t[N], f[N], inv[N];
int main(){

    r(n, k);
    long long fac = 1;
    for(int i = 1; i <= n; ++i)
        r(a[i]), fac = fac * i % mod;
    inv[1] = 1;
    for(int i = 2; i <= n; ++i)
        inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
    for(int i = n; i >= 1; --i){
        int tmp = 0;
        for(int j = i; j <= n; j += i)
            tmp = tmp ^ t[j];
        a[i] ^= tmp;
        t[i] = a[i] == 1; tot += t[i]; 
    }
    if(tot <= k) 
        return w(1ll * tot * fac % mod), 0;
    f[n] = 1;
    for(int i = n - 1; i >= 1; --i)
        f[i] = 1ll * (n + 1ll * (n - i) * f[i + 1] % mod) * inv[i] % mod;
    long long ans = k;
    for(int i = k + 1; i <= tot; ++i)
        ans += f[i];
    w(ans * fac % mod);
    return 0;
}

T5 相逢是问候

Description

懒得写挂个链接算惹

Solution

就拿这个题来梳理一下扩展欧拉定理吧。

扩展欧拉定理的内容：

$c^q\equiv \begin{cases} c^{q\text{ mod } \varphi(p)}\ \ \ \ \ \ \ \ \ \ \gcd(c,p) = 1\\ c^{q\text{ mod }\varphi(p)+\varphi(p)} \ \ \ \gcd(c,p)\ne 1\cap q \ge \varphi(p)\\ c^{q}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \gcd(c,p)\ne 1 \cap q < \varphi(p) \end{cases} \mod{p}$

特别留意 $q\ge\varphi(p)$ 的情况。

首先可以发现，下述形式的幂次塔在足够高的时候会恒等于一个值。

$c^{(c^{(c^{(\cdots)})})}\ \mod{p}$

原因是利用扩展欧拉定理对指数不断用 $\varphi(p)$ 取模，最终 $\varphi(p)=1$ ，此时幂次塔再高也等于 $0$ 。可以证明幂次塔最高 $\mathcal{O}(\log_2p)$ 层。

于是可以得到做此题的大致流程：先暴力算幂次塔的答案，假设为 $x$ 。 在幂次塔不高时对修改位置暴力计算，在幂次塔超过一定阈值时钦定此位置为 $x$ 。这样复杂度是 $n\log_2p$ 的。

现在问题在于如何暴力计算。当然不能简单的快速幂，因为每次我们存下来的是上次幂完对 $p$ 取模的值而非对 $\varphi(p)$ 取模的值。注意到 $c$ 和 $a_i$ 都是给定的，我们可以先预处理出来 $c^{(c^{(\cdots c^{a_i})})}\text{ mod } p$ 。

预处理的时候需要一个快速幂，所以复杂度是 $\mathcal{O}(n\log_2^3p)$ ，这就很不好。但是由于底数固定，我们可以用光速幂。注意到我们无论是预处理幂次塔值还是预处理暴力，幂次出来后仍然是指数，所以在光速幂时处理出来的值也要用扩展欧拉定理来处理，而不是直接取模。

所以总复杂度 $\mathcal{O}(n\log_2^2n)$ 。

Code

const int N = 5e4 + 5, M = 65, S = 32767;
using namespace std;
int n, m, c, mod, cnt, dig;
int a[N], phi[M], pro[N][M];
long long q0[M][S + 1], q1[M][S + 1];
int check(long long n, int p){
    return  n >= p ? n % p + p : n ;
}
void Prework(){
    for(int i = 0; i <= cnt; ++i){
        q0[i][0] = q1[i][0] = 1;
        for(int j = 1; j <= S; ++j) q0[i][j] = check(q0[i][j - 1] * c, phi[i]);
        q1[i][1] = check(q0[i][S] * c, phi[i]);
        for(int j = 2; j <= S; ++j) q1[i][j] = check(q1[i][j - 1] * q1[i][1], phi[i]);  
    }
}
int Q(int x, int t){
    return check(q0[t][x & S] * q1[t][x >> 15], phi[t]); 
}
int calcpow(int d, int x, int t){       // 计算幂次
    if(!x) return check(d, phi[t]);
    if(t == cnt) return 1;
    int v = Q(calcpow(d, x - 1, t + 1), t);
    return v;
}
int calcphi(int x){                     // 计算幂次塔
    int up = sqrt(x), ret = x;
    for(int i = 2; i <= up; ++i)
        if(x % i == 0){
            ret = ret / i * (i - 1);
            while(x % i == 0) 
                x /= i;
        }
    if(x != 1) 
        ret = ret / x * (x - 1);
    return ret;
}   
int query(int t){
    if(t == cnt) return 0;
    return Q(query(t + 1) + phi[t + 1], t);
}
namespace SEG{
#define mid (l + r >> 1)
#define ls p << 1, l, mid
#define rs p << 1 | 1, mid + 1, r
    int t[N << 2], s[N << 2], tag[N << 2];
    void update(int p){
        t[p] = (t[p << 1] + t[p << 1 | 1]) % mod;
        tag[p] = tag[p << 1] & tag[p << 1 | 1];
    }
    void build(int p = 1, int l = 1, int r = n){
        if(l == r) return t[p] = a[l] % mod, tag[p] = 0, void();
        build(ls), build(rs);
        update(p);
    }
    void modify(int p, int l, int r, int nl, int nr){
        if(l > nr or r < nl) return;
        if(l >= nl and r <= nr and tag[p]) return; 
        if(l == r){
            ++ s[p];
            t[p] = pro[l][s[p]];
            if(s[p] == cnt + 1) 
                tag[p] = 1;
            return;
        }
        modify(ls, nl, nr);
        modify(rs, nl, nr);
        update(p);
    }   
    int query(int p, int l, int r, int nl, int nr){
        if(l > nr or r < nl) return 0;
        if(l >= nl and r <= nr) return t[p];
        return (query(ls, nl, nr) + query(rs, nl, nr)) % mod;
    }
}
int main(){

    r(n, m, mod, c);
    phi[0] = mod;
    while(phi[cnt] != 1) 
        phi[cnt + 1] = calcphi(phi[cnt]), cnt ++;
    Prework();
    dig = query(0);
    for(int i = 1; i <= n; ++i)
        r(a[i]); 
    for(int i = 1; i <= n; ++i){
        pro[i][0] = a[i];
        for(int j = 1; j <= cnt + 1; ++j)
            pro[i][j] = calcpow(pro[i][0], j, 0) % mod;
        pro[i][0] %= mod;
    }
    SEG::build();
    int tp, L, R;
    for(int i = 1; i <= m; ++i){
        r(tp, L, R);
        if(tp == 0) SEG::modify(1, 1, n, L, R);
        else w(SEG::query(1, 1, n, L, R));
    }
    return 0;
}

T6 摧毁树状图

Description

这个的题面是真的长

Solution

做这道题权当练习换根 DP 吧。写完真的感觉对树上路径/链的问题的换根的理解上升了一个档次。

题目就是要求两条边不相交的路径，满足删去路径后全树剩下来的连通块数最大。
首先考虑两条链只有两种位置关系：交于一点/不相交。对于这两种情况，我们分开考虑再合并最优解。
对于第一种情况，我们可以先钦定交点 $x$ ，然后再求 $x$ 的四个相邻连通块，满足这四个连通块是在仅存在一条通向交点的链的情况下可分裂出的连通块数为所有相邻块中的前四大。
对于第二种情况，我们可以枚举一个点，求出该点子树内必经这个点的路径中能造成分裂出来的最大连通块数和除去该子树以外的部分在一条路径的情况下能分裂出来的最大连通块数，并将这两部分合起来。

注意：上述所说的连通块和链都可以退化成一个点。

上述两种情况都可以通过换根 DP 解决。

需要的信息很多，我们一条一条列出来，并根据需要的信息和转移设状态。对于一个有 $a$ 个子节点的子树 $p$ ：
首先，我们需要知道在 $p$ 的子树中，去掉一条包含 $p$ 的链可以实现的最大连通块数。不妨设其为 g[p] 。我们不仅需要最大的，还需要删除某个点后前四大的连通块，为了区分是否可以仅删除 $p$ 点，我们设这个为 gmx[p][4] 。考虑 g[p] 的转移：

$g_p =\max(a,\text{gmx}_{p,0}+a-1)$

另外，我们需要知道在 $p$ 的子树内，删去一条必经 $p$ 点的路径后最大的连通块数，我们设其为 h[p] 。考虑 h[p] 的转移：

$h_p = \max(g_p,\text{gmx}_{p,0}+\text{gmx}_{p,1}+a-2)$

最后，我们还需要知道删去不必经 $p$ 点的路径后最大的连通块数，我们设其为 f[p] 。在仅知道 f[] g[] h[] 的情况下并不好直接转移 f 。因为如果 p 的子节点 u 的 f[u] 的这条路径经过了点 $u$ ，$u$ 点不会计算在 $p$ 处连通块产生的贡献；若强制加一，则路径不经过点 $u$ 时，$p$ 点实质上没有增加贡献。所以我们需要规定此时的 f[p] 是否计算了在父节点以上连通块的贡献。设其为 f[p][0] 和 f[p][1] 。令 fmx[p] 为 $p$ 的所有子节点 $u$ 的最大 f[u][1] 值，则考虑 f[p] 的转移为：

$f_{p,0} = \max(\text{fmx}_p,h_p)\\ f_{p,1} =\max(\text{fmx}_p,h_p+1)$

然后换根就是借着 gmx[p] 和 fmx[p] 重新更新一下就好了。
复杂度 $\mathcal{O}(n)$ 。

Code

const int N = 1e5 + 5;
using namespace std;
int n, num, ans;
int deg[N], head[N], to[N << 1], nt[N << 1];
void Add(int x, int y){
    ++num, nt[num] = head[x], head[x] = num, to[num] = y, ++deg[x];
    ++num, nt[num] = head[y], head[y] = num, to[num] = x, ++deg[y];
}
int h[N], g[N], f[N][2], fmx[N][2], gmx[N][4]; 
void updg(int v, int p){
    for(int i = 0; i < 4; ++i)
        if(gmx[p][i] < v) swap(gmx[p][i], v);
}
void updf(int v, int p){
    for(int i = 0; i < 2; ++i)
        if(fmx[p][i] < v) swap(fmx[p][i], v);
}
void dp(int p, int fa){
    g[p] = h[p] = -oo;
    f[p][0] = f[p][1] = fmx[p][0] = fmx[p][1] = -oo;
    gmx[p][0] = gmx[p][1] = gmx[p][2] = gmx[p][3] = -oo;
    int cnt = 0;
    for(int i = head[p];i; i = nt[i]){
        int v = to[i]; if(v == fa) continue;
        dp(v, p), ++cnt;
        updf(f[v][1], p), updg(g[v], p);
    }
    g[p] = max(cnt, gmx[p][0] + cnt - 1);
    h[p] = max(g[p], gmx[p][0] + gmx[p][1] + cnt - 2);
    f[p][0] = max(fmx[p][0], h[p]);
    f[p][1] = max(fmx[p][0], h[p] + 1);
}
void rdp(int p, int fa){
    int now = deg[p];
    ans = max(ans, now);
    for(int i = 0; i < 4; ++i)
        ans = max(ans, now += gmx[p][i] - 1);
    int cnt = deg[p] - 1;
    for(int i = head[p];i; i = nt[i]){
        int v = to[i]; if(v == fa) continue;
        
        int tfmx = fmx[p][0], tgmx = gmx[p][0], tlmx = gmx[p][0] + gmx[p][1];
        if(tgmx == g[v]) tgmx = gmx[p][1], tlmx += gmx[p][2] - gmx[p][0];
        else if(gmx[p][1] == g[v]) tlmx += gmx[p][2] - gmx[p][1];
        if(tfmx == f[v][1]) tfmx = fmx[p][1]; 
        g[p] = max(cnt,  tgmx + cnt - 1);
        h[p] = max(g[p], tlmx + cnt - 2);
        f[p][0] = max(tfmx, h[p]);
        f[p][1] = max(tfmx, h[p] + 1);
        ans = max(ans, f[p][0] + h[v]); // attention the order 
        //如果是 h[p] + f[v][0] 就相当于钦定某条路径在令一条路径的某个点的子树内，会漏解。
        updf(f[p][1], v), updg(g[p], v); 
        rdp(v, p);
    }
}
int x;
void solve(){

    memset(head, 0, sizeof head);
    memset(deg , 0, sizeof deg );
    num = ans = 0;

    r(n);
    for(int i = 0, y; i < x; ++i)
        r(y), r(y);
    for(int i = 1, x, y; i < n; ++i)
        r(x, y), Add(x, y);
    dp(1, 0);
    rdp(1, 0);
    w(ans);
}
int main(){

    int T;r(T, x);
    while (T--)
        solve();
    return 0;
}