J

二分多源BFS 切比雪夫距离

01矩阵，最多把一个0变成1，然后每个1每一秒会把曼哈顿距离为1的相邻0变成1，问变成全1的最小时间？

注意到肯定是越早越困难，越晚越容易，答案具有单调性，可以二分变成全1的时间。

从多个源点出发的染色，故check里考虑多源bfs，发现我们从所有1出发bfs，只能走mid秒的话，可能有的0还没变成1。而我们又有一次染色的机会，所以我们就是要检查能否找到一个点，初始时变成1，然后从这个点出发bfs mid步，能覆盖所有这些还未被染色的0

也就是能否找到一个点，到所有未被染色的点的曼哈顿距离不超过mid。

曼哈顿距离，可以坐标变换后变成切比雪夫距离， alt

所以就转化成了求

$\max(\max(|x_0-x_i|,|y_0-y_i|))$

等价于

$\max(\max(|x_0-x_i|),max(|y_0-y_i|))$

对于每个维度求到一个集合内所有点的最大距离，实际上只用维护这个集合内的最大值最小值，取max即可。

故可以遍历图上所有初始0，枚举把哪个变成1，以这个点为 $(x_0,y_0)$ 计算上式，如果至少存在一个上式不超过mid，check就返回true

#include <bits/stdc++.h>
#define int long long

using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using graph = vector<vector<pii>>;
using ugraph = vector<vector<int>>;
constexpr int N = 2E5 + 5;
constexpr double eps = 1E-8;
constexpr int inf = 0x3f3f3f3f;
constexpr ll INF = 1E18;

int walk[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
vector<vector<int>> bfs(int n, int m, vector<vector<char>> &g) {
    queue<pii> q;
    vector<vector<int>> dist(n + 1, vector<int>(m + 1, INF));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (g[i][j] == '1') {
                q.emplace(i, j);
                dist[i][j] = 0;
            }
        }
    }
    while (not q.empty()) {
        auto [i, j] = q.front();
        q.pop();
        for (auto [x, y] : walk) {
            int u = i + x, v = j + y;
            if (u < 1 or u > n or v < 1 or v > m) continue;
            if (dist[u][v] != INF) continue;
            dist[u][v] = dist[i][j] + 1;
            q.emplace(u, v);
        }
    }
    return dist;
}

int bfs2(int n, int m, vector<vector<char>> &g) {
    queue<pii> q;
    vector<vector<int>> dist(n + 1, vector<int>(m + 1, INF));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (g[i][j] == '1') {
                q.emplace(i, j);
                dist[i][j] = 0;
            }
        }
    }
    while (not q.empty()) {
        auto [i, j] = q.front();
        q.pop();
        for (auto [x, y] : walk) {
            int u = i + x, v = j + y;
            if (u < 1 or u > n or v < 1 or v > m) continue;
            if (dist[u][v] != INF) continue;
            dist[u][v] = dist[i][j] + 1;
            q.emplace(u, v);
        }
    }
    int Max = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) Max = max(Max, dist[i][j]);
    return Max;
}

bool check(int mid, int n, int m, vector<vector<char>> &g, vector<vector<int>> &dist) {
    vector<pii> points;
    for (int i = 1; i <= n; i++) {
        for (int j = 1;j <=m; j++) {
            if (dist[i][j] > mid) {
                points.emplace_back(i, j);
            }
        }
    }
    int maxu = -INF, minu = INF, maxv = -INF, minv = INF;
    for (auto [i, j] : points) {
        int u = i + j;
        int v = i - j;
        maxu = max(maxu, u);
        minu = min(minu, u);
        maxv = max(maxv, v);
        minv = min(minv, v);
    }
    if (points.empty()) return true;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (g[i][j] == '1') continue;
            int u = i + j, v = i - j;
            int du = max(abs(u - maxu), abs(u - minu));
            int dv = max(abs(v - maxv), abs(v - minv));
            int d = max(du, dv);
            if (d <= mid) return true;
        }
    }
    return false;
}

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<char>> g(n + 1, vector<char>(m + 1));
    bool have = false;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> g[i][j];
            if (g[i][j] == '1') have = true;
        }
    }
    if (not have) {
        g[(n+1)/2][(m+1)/2] = '1';
        int ans = bfs2(n, m, g);
        cout << ans << "\n";
        return;
    }
    auto dist = bfs(n, m, g);
    int lo = 0, hi = n*m, ans = hi;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (check(mid, n, m, g, dist)) {
            ans = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T = 1;
    for (int ttt = 1; ttt <= T; ++ttt) {
        solve();
    }
    return 0;
}

K

FWT 倍增/二分

要集齐一个集合的所有元素，每个路线包含一些元素，问最少选几个路线能集齐所有元素？路线数最少的方案有几种？

元素个数很少，可以状压。但路线很多，枚举每个路线，枚举所有状态进行转移，是 $O(k2^m)$ 的，肯定不行。

实际上这是个经典问题，状压求全集，如果每次只增加一个元素，dp可做，复杂度 $O(m2^m)$ ，但是每次增加全集的一个子集，如果增加次数还很多，用dp的方式就不可做了。

所以这里就不能用dp。

当你发现一般思路怎么优化都不可能过的时候，往往意味着要上科技了。这题就是要上科技。

很多dp转移实际上就是 $change(i,j)=k$ ，表示状态 $i$ 遇到 $j$ 可以转移到状态 $k$ ，那么转移 $dp_k+=f(dp_i,dp_j)$ ，也就是可以通过 $dp_i,dp_j$ 计算出一个对 $dp_k$ 的贡献

对于这种问题，如果这个 $change$ 函数是加法，或者 $and,or,xor$ 这些运算，并且计算的是方案数，也就是 $f$ 函数就是 $f(x,y)=x*y$ ，服从乘法原理。我们就可以把这个问题转化成卷积

比如如果在一个序列里选两个元素加起来，求和为不同值的方案数，也就是若 $x+y=z$ ，则 $f_z+=f_x$ ，此时就可以 $FFT$ 变换，然后卷积一次，再变换回来。就能得到每个和值的方案数

如果是 $x 按位或 y=z$ ，那么可以用 $FWT$ 来变换

回到本题，注意到每次转移实际上就是两个状态取并集，方案数相乘。可以用 $FWT$ 然后卷积。每次卷积就是增加一个路径。我们想知道最少选几个路径可以得到全集，也就是看卷积多少次后，逆变换回来，全集的系数不为0

注意到这个次数是单调的，也就是卷积次数越多，选的路径越多，越可能得到全集，故考虑二分卷积次数。 $check$ 时计算卷积mid次后，逆变换回来，全集的系数，检查是否为0

略卡常，故二分次数有讲究。注意如果一个路径加进来，不会给状态增加新的元素，那其实可以不加这个路径。所以最优方案里，每一条路径都至少给状态贡献了一个新元素。故最优方案的路径数不会超过 $m$ 个，所以卷积次数也不会超过 $m$ ，我们二分卷积次数的上界可以设成 $m$ 。这可以大大减少常数。

复杂度为 $O(log(m)m2^m)$

// 或 正1逆-1
void Or(vector<ll> & a, ll type, ll P, int n)
{ // 迭代实现，常数更小
    for (ll x = 2; x <= n; x <<= 1)
    {
        ll k = x >> 1;
        for (ll i = 0; i < n; i += x)
        {
            for (ll j = 0; j < k; j++)
            {
                (a[i + j + k] += a[i + j] * type % P) %= P;
            }
        }
    }
}
ll Or_single_rev(const vector<ll>& f, ll P, int x, int n) {
    ll res = 0;
    for (int y = x; y != 0; y = (y-1) & x) {  // 枚举所有非零子集 y ⊆ x
        int cnt = __builtin_popcount(x ^ y);
        ll coeff = (cnt % 2 == 0) ? 1 : (P-1);
        res = (res + f[y] * coeff) % P;
    }
    // 单独处理 y=0 的情况（如果 x 包含 0 这个子集）
    if ((x & 0) == 0) {  // 恒成立，简化为直接处理
        res = (res + f[0] * ((__builtin_popcount(x) % 2 == 0) ? 1 : (P-1))) % P;
    }
    return res;
}
int f[N][20],sum[25][N];
void solve()
{
    int n,m,k;
    cin >> n>>m>>k;
    vi lg(n+1);
    rep(i,2,n){
        lg[i]=lg[i/2]+1;
    }
    vi fac(n+1);
    fac[0]=1;
    rep(i,1,n){
        fac[i]=fac[i-1]*i%M2;
    }
     
    vvi g(n+1);
    vi u(n+1),v(n+1);
    rep(i,1,n-1){
        cin>>u[i]>>v[i];
        g[u[i]].push_back(v[i]);
        g[v[i]].push_back(u[i]);
    }
    vi d(n+1);
     
    auto &&dfs=[&](auto &&dfs,int u,int fa)->void{
        f[u][0]=fa;
        rep(i,1,lg[d[u]]){
            f[u][i]=f[f[u][i-1]][i-1];
        }
        for(int v:g[u]){
            if(v==fa)continue;
            d[v]=d[u]+1;
            dfs(dfs,v,u);
        }
    };
    dfs(dfs,1,0);
     
    auto lca=[&](int x,int y)->int{
        if (d[x] < d[y])
            swap(x, y);
        while (d[x] > d[y])
            x = f[x][lg[d[x] - d[y]]];
        if (x == y)
            return x;
        for (int i = lg[d[x]]; i >= 0; i--)
            if (f[x][i] != f[y][i])
                x = f[x][i], y = f[y][i];
        return f[x][0];
    };
     
    auto &&dfs1=[&](auto &&dfs1,int u,int fa,int idx)->void{
        for(int v:g[u]){
            if(v==fa)continue;
            sum[idx][v]+=sum[idx][u];
            dfs1(dfs1,v,u,idx);
        }
    };
    rep(i,1,m){
        int x;
        cin>>x;
        if(d[u[x]]>d[v[x]]){
            sum[i][u[x]]++;
        }
        else{
            sum[i][v[x]]++;
        }
        dfs1(dfs1,1,0,i);
    }
     
    vi p(1<<m);
    rep(i,1,k){
        int s,t;
        cin>>s>>t;
        int LCA=lca(s,t);
         
        int mask=0;
        rep(j,1,m){
            int tot=sum[j][s]+sum[j][t]-2*sum[j][LCA];
            if(tot){
                mask|=(1<<(j-1));
            }
        }
        p[mask]++;
//      cout<<mask<<' ';
    }
     
    Or(p,1,M2,1<<m);
     
    int l=0,r=m;
    int ans=0;
    auto check=[&](int x)->bool{
        vi t(1<<m);
        rep(i,0,(1<<m)-1){
            t[i]=power(p[i],x,M2);
        }
        Or(t,M2-1,M2,1<<m);
//      int res=Or_single_rev(t,M2,(1<<m)-1,1<<m);
//      cout<<x<<' '<<res<<'\n';
//      cout<<x<<' '<<t[(1<<m)-1]<<'\n';
        if(t[(1<<m)-1]){
            ans=t[(1<<m)-1];
            return 1;
        }
        return 0;
    };
    while(l<=r){
        int m=l+r>>1;
        if(check(m))r=m-1;
        else l=m+1;
    }
    if(l<=m)cout<<l<<' '<<ans*inv(fac[l],M2)%M2;
    else cout<<-1;
}

这里还有优化空间，注意到我们实际上只想知道全集的系数，并不用把整个值域都逆变换回来，只要能计算出全集逆变换的结果即可。这是可以在 $O(2^m)$ 时间内做到的，而全集都逆变换回来需要 $O(2^mlog(2^m))$

计算全集项的式子是这样的 alt 也可以直接枚举子集

ll Or_single_rev(const vector<ll>& f, ll P, int x, int n) {
    ll res = 0;
    for (int y = x; y != 0; y = (y-1) & x) {  // 枚举所有非零子集 y ⊆ x
        int cnt = __builtin_popcount(x ^ y);
        ll coeff = (cnt % 2 == 0) ? 1 : (P-1);
        res = (res + f[y] * coeff) % P;
    }
    // 单独处理 y=0 的情况（如果 x 包含 0 这个子集）
    if ((x & 0) == 0) {  // 恒成立，简化为直接处理
        res = (res + f[0] * ((__builtin_popcount(x) % 2 == 0) ? 1 : (P-1))) % P;
    }
    return res;
}

但注意这里有个计算集合大小的操作(popcount)，实际上也会带来一个 $log$ ，如果预处理的话可以去掉这个 $log$ ，变成严格 $O(2^m)$ ，否则跑的时间实际上和整个值域逆变换差不多

如果预处理了 $popcount$ ，单点逆变换的复杂度是 $O(log(m)2^m)$

实际上也没变快太多，因为预处理也要时间

// 或 正1逆-1
void Or(vector<ll> & a, ll type, ll P, int n)
{ // 迭代实现，常数更小
    for (ll x = 2; x <= n; x <<= 1)
    {
        ll k = x >> 1;
        for (ll i = 0; i < n; i += x)
        {
            for (ll j = 0; j < k; j++)
            {
                (a[i + j + k] += a[i + j] * type % P) %= P;
            }
        }
    }
}
int mask_cnt[1<<23];
ll Or_single_rev(const vector<ll>& f, ll P, int x, int n) {
    ll res = 0;
    for (int y = x; y != 0; y = (y-1) & x) {  // 枚举所有非零子集 y ⊆ x
        int cnt = mask_cnt[x^y];
        ll coeff = (cnt % 2 == 0) ? 1 : (P-1);
        res = (res + f[y] * coeff) % P;
    }
    // 单独处理 y=0 的情况（如果 x 包含 0 这个子集）
    if ((x & 0) == 0) {  // 恒成立，简化为直接处理
        res = (res + f[0] * ((mask_cnt[x] % 2 == 0) ? 1 : (P-1))) % P;
    }
    return res;
}
int f[N][20],sum[25][N];
void solve()
{
    int n,m,k;
    cin >> n>>m>>k;
    rep(i,0,(1<<m)-1){
        mask_cnt[i]=__builtin_popcount(i);
    }
     
    vi lg(n+1);
    rep(i,2,n){
        lg[i]=lg[i/2]+1;
    }
    vi fac(n+1);
    fac[0]=1;
    rep(i,1,n){
        fac[i]=fac[i-1]*i%M2;
    }
     
    vvi g(n+1);
    vi u(n+1),v(n+1);
    rep(i,1,n-1){
        cin>>u[i]>>v[i];
        g[u[i]].push_back(v[i]);
        g[v[i]].push_back(u[i]);
    }
    vi d(n+1);
     
    auto &&dfs=[&](auto &&dfs,int u,int fa)->void{
        f[u][0]=fa;
        rep(i,1,lg[d[u]]){
            f[u][i]=f[f[u][i-1]][i-1];
        }
        for(int v:g[u]){
            if(v==fa)continue;
            d[v]=d[u]+1;
            dfs(dfs,v,u);
        }
    };
    dfs(dfs,1,0);
     
    auto lca=[&](int x,int y)->int{
        if (d[x] < d[y])
            swap(x, y);
        while (d[x] > d[y])
            x = f[x][lg[d[x] - d[y]]];
        if (x == y)
            return x;
        for (int i = lg[d[x]]; i >= 0; i--)
            if (f[x][i] != f[y][i])
                x = f[x][i], y = f[y][i];
        return f[x][0];
    };
     
    auto &&dfs1=[&](auto &&dfs1,int u,int fa,int idx)->void{
        for(int v:g[u]){
            if(v==fa)continue;
            sum[idx][v]+=sum[idx][u];
            dfs1(dfs1,v,u,idx);
        }
    };
    rep(i,1,m){
        int x;
        cin>>x;
        if(d[u[x]]>d[v[x]]){
            sum[i][u[x]]++;
        }
        else{
            sum[i][v[x]]++;
        }
        dfs1(dfs1,1,0,i);
    }
     
    vi p(1<<m);
    rep(i,1,k){
        int s,t;
        cin>>s>>t;
        int LCA=lca(s,t);
         
        int mask=0;
        rep(j,1,m){
            int tot=sum[j][s]+sum[j][t]-2*sum[j][LCA];
            if(tot){
                mask|=(1<<(j-1));
            }
        }
        p[mask]++;
//      cout<<mask<<' ';
    }
     
    Or(p,1,M2,1<<m);
     
    int l=0,r=m;
    int ans=0;
    auto check=[&](int x)->bool{
        vi t(1<<m);
        rep(i,0,(1<<m)-1){
            t[i]=power(p[i],x,M2);
        }
//      Or(t,M2-1,M2,1<<m);
        int res=Or_single_rev(t,M2,(1<<m)-1,1<<m);
//      cout<<x<<' '<<res<<'\n';
//      cout<<x<<' '<<t[(1<<m)-1]<<'\n';
        if(res){
            ans=res;
            return 1;
        }
        return 0;
    };
    while(l<=r){
        int m=l+r>>1;
        if(check(m))r=m-1;
        else l=m+1;
    }
    if(l<=m)cout<<l<<' '<<ans*inv(fac[l],M2)%M2;
    else cout<<-1;
}

另一种做法是倍增，理论上是 $O(log(m)2^m)$ ，但跑的要慢一些。思路就是倍增求卷积次数，预处理卷积 $2^i$ 次的结果，然后从大到小枚举2的幂次，把预处理的卷积结果合并，检查全集系数，如果不为0，说明大了，撤销这个合并，如果为0，说明还没超，保留这次合并。这类似lca倍增找父亲的过程。

但问题是每次合并倍增结果的过程常数有点大，还要预处理 $2^i$ 的结果，实际上跑的和二分差不多。

void Or(vector<ll> & a, ll type, ll P, int n)
{ // 迭代实现，常数更小
    for (ll x = 2; x <= n; x <<= 1)
    {
        ll k = x >> 1;
        for (ll i = 0; i < n; i += x)
        {
            for (ll j = 0; j < k; j++)
            {
                (a[i + j + k] += a[i + j] * type % P) %= P;
            }
        }
    }
}
int mask_cnt[1<<23];
ll Or_single_rev(const vector<ll>& f, ll P, int x, int n) {
    ll res = 0;
    for (int y = x; y != 0; y = (y-1) & x) {  // 枚举所有非零子集 y ⊆ x
//         int cnt = __builtin_popcount(x ^ y);
        int cnt=mask_cnt[x^y];
        ll coeff = (cnt % 2 == 0) ? 1 : (P-1);
        res = (res + f[y] * coeff) % P;
    }
    // 单独处理 y=0 的情况（如果 x 包含 0 这个子集）
    if ((x & 0) == 0) {  // 恒成立，简化为直接处理
        res = (res + f[0] * ((mask_cnt[x]% 2 == 0) ? 1 : (P-1))) % P;
    }
    return res;
}
int f[20][N],sum[25][N];
void solve()
{
    int n,m,k;
    cin >> n>>m>>k;
     
    rep(i,0,(1<<m)-1){
        mask_cnt[i]=__builtin_popcount(i);
    }
    vi lg(n+1);
    rep(i,2,n){
        lg[i]=lg[i/2]+1;
    }
    vi fac(n+1);
    fac[0]=1;
    rep(i,1,n){
        fac[i]=fac[i-1]*i%M2;
    }
     
    vvi g(n+1);
    vi u(n+1),v(n+1);
    rep(i,1,n-1){
        cin>>u[i]>>v[i];
        g[u[i]].push_back(v[i]);
        g[v[i]].push_back(u[i]);
    }
    vi d(n+1);
     
    auto &&dfs=[&](auto &&dfs,int u,int fa)->void{
        f[0][u]=fa;
        rep(i,1,lg[d[u]]){
            f[i][u]=f[i-1][f[i-1][u]];
        }
        for(int v:g[u]){
            if(v==fa)continue;
            d[v]=d[u]+1;
            dfs(dfs,v,u);
        }
    };
    dfs(dfs,1,0);
     
    auto lca=[&](int x,int y)->int{
        if (d[x] < d[y])
            swap(x, y);
        while (d[x] > d[y])
            x = f[lg[d[x] - d[y]]][x];
        if (x == y)
            return x;
        for (int i = lg[d[x]]; i >= 0; i--)
            if (f[i][x] != f[i][y])
                x = f[i][x], y = f[i][y];
        return f[0][x];
    };
     
    auto &&dfs1=[&](auto &&dfs1,int u,int fa,int idx)->void{
        for(int v:g[u]){
            if(v==fa)continue;
            sum[idx][v]+=sum[idx][u];
            dfs1(dfs1,v,u,idx);
        }
    };
    rep(i,1,m){
        int x;
        cin>>x;
        if(d[u[x]]>d[v[x]]){
            sum[i][u[x]]++;
        }
        else{
            sum[i][v[x]]++;
        }
        dfs1(dfs1,1,0,i);
    }
     
    vi p(1<<m);
    rep(i,1,k){
        int s,t;
        cin>>s>>t;
        int LCA=lca(s,t);
         
        int mask=0;
        rep(j,1,m){
            int tot=sum[j][s]+sum[j][t]-2*sum[j][LCA];
            if(tot){
                mask|=(1<<(j-1));
            }
        }
        p[mask]++;
//      cout<<mask<<' ';
    }
     
    Or(p,1,M2,1<<m);
    vvi pw(6,vi(1<<m));
    pw[0]=p;
    rep(i,1,5){
        rep(j,0,(1<<m)-1){
            pw[i][j]=pw[i-1][j]*pw[i-1][j]%M2;
        }
    }
    vi t(1<<m);
    int cnt=0;
    bool flag=1;
    for(int i=5;i>=0;i--){
        vi tt=t;
        if(flag){
            tt=pw[i];
        }
        else{
            for(int j=0;j<(1<<m);j++){
                tt[j]=tt[j]*pw[i][j]%M2;
            }
        }
//         Or(tt,M2-1,M2,1<<m);
        int res=Or_single_rev(tt,M2,(1<<m)-1,1<<m);
        if(!res){
            if(i==5){
                cout<<-1;
                return;
            }
            if(flag){
                t=pw[i];
                flag=0;
            }
            else{
                for(int j=0;j<(1<<m);j++){
                    t[j]=t[j]*pw[i][j]%M2;
                }
            }
            cnt|=1<<i;
        }
    }
    if(flag){
        t=pw[0];
    }
    else{
        for(int j=0;j<(1<<m);j++){
            t[j]=t[j]*pw[0][j]%M2;
        }
    }
    cnt++;
    int ans=Or_single_rev(t,M2,(1<<m)-1,1<<m);
    cout<<cnt<<' '<<ans*inv(fac[cnt],M2)%M2;
     
}

2025暑期第五场

J

K