2025牛客暑期多校训练营5-做题&补题记录

好像还是赤石场。我们牛客多校是这样的。

---

I Block Combination Minimal Perimeter

Guess。做完了。

/*

This code template was updated by Yukii_P on 2025/4/4.

*/
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 1
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

#ifndef ONLINE_JUDGE
#define debug(...) std::cerr << #__VA_ARGS__ << " = "; dbg1(__VA_ARGS__)
void dbg2() { std::cerr << "\n"; }
template<typename T, typename... T2>
void dbg2(T x, T2... args) {
    std::cerr << ", " << x;
    dbg2(args...);
}
template<typename T, typename... T2>
void dbg1(T x, T2... args) {
    std::cerr << x;
    dbg2(args...);
}
#else
#define debug(...) 
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 2e5 + 10;
constexpr int MOD = 998244353;

void solve() {
    int n;
    cin >> n;
    n--;
    cout << 4 + (4 * (n - n / 2) + 2 * (n / 2)) << "\n";
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

/*

  _  _                            _____             _               _               _    
 | \| |    ___    _ _      ___   |_   _|    _ _    (_)    __ __    (_)    __ _     | |   
 | .` |   / _ \  | ' \    |___|    | |     | '_|   | |    \ V /    | |   / _` |    | |   
 |_|\_|   \___/  |_||_|   _____   _|_|_   _|_|_   _|_|_   _\_/_   _|_|_  \__,_|   _|_|_  
_|"""""|_|"""""|_|"""""|_|     |_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""| 
"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-' 

(Font: ASCII - Train)

"El Psy Kongroo." -- Hououin Kyoma

"私は極色カスタ推しです...だが、狽音ウルシと夜鳴トバリも推す :)" -- Yukii_P

*/

E Mysterious XOR Operation

按位考虑贡献。把所有数按照当前位奇偶、最低位到当前位所有1的个数的奇偶分成四组计数。贡献数量就是最低位到当前位1的个数奇偶相同的当前位奇的数量乘当前位偶的数量，两组分别相乘再相加。贡献的权值是2的k次方，k是当前位数。

/*

This code template was updated by Yukii_P on 2025/4/4.

*/
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

#ifndef ONLINE_JUDGE
#define debug(...) std::cerr << #__VA_ARGS__ << " = "; dbg1(__VA_ARGS__)
void dbg2() { std::cerr << "\n"; }
template<typename T, typename... T2>
void dbg2(T x, T2... args) {
    std::cerr << ", " << x;
    dbg2(args...);
}
template<typename T, typename... T2>
void dbg1(T x, T2... args) {
    std::cerr << x;
    dbg2(args...);
}
#else
#define debug(...) 
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 2e5 + 10;
constexpr int MOD = 998244353;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    i64 ans = 0;
    for (int k = 0; k < 31; ++k) {
        i64 c[4]{};
        int mask = (1 << k) - 1;
        for (auto x : a) {
            int j = (x >> k) & 1;
            int cnt = __builtin_popcount(x & mask);
            if (j & 1) {
                if (cnt & 1) c[0]++;
                else c[1]++;
            } else {
                if (cnt & 1) c[2]++;
                else c[3]++;
            }
        }
        ans += (1LL << k) * (c[0] * c[2] + c[1] * c[3]);
    }
    cout << ans << "\n";
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

/*

  _  _                            _____             _               _               _    
 | \| |    ___    _ _      ___   |_   _|    _ _    (_)    __ __    (_)    __ _     | |   
 | .` |   / _ \  | ' \    |___|    | |     | '_|   | |    \ V /    | |   / _` |    | |   
 |_|\_|   \___/  |_||_|   _____   _|_|_   _|_|_   _|_|_   _\_/_   _|_|_  \__,_|   _|_|_  
_|"""""|_|"""""|_|"""""|_|     |_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""| 
"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-' 

(Font: ASCII - Train)

"El Psy Kongroo." -- Hououin Kyoma

"私は極色カスタ推しです...だが、狽音ウルシと夜鳴トバリも推す :)" -- Yukii_P

*/

J Fastest Coverage Problem

不染色拿到最大距离，然后二分答案。check时把曼哈顿距离转切比雪夫距离，其实就是把菱形转矩形区域，然后取所有合法矩形的交集，如果存在一个0在这个交集内就合法。

/*

This code template was updated by Yukii_P on 2025/4/4.

*/
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

#ifndef ONLINE_JUDGE
#define debug(...) std::cerr << #__VA_ARGS__ << " = "; dbg1(__VA_ARGS__)
void dbg2() { std::cerr << "\n"; }
template<typename T, typename... T2>
void dbg2(T x, T2... args) {
    std::cerr << ", " << x;
    dbg2(args...);
}
template<typename T, typename... T2>
void dbg1(T x, T2... args) {
    std::cerr << x;
    dbg2(args...);
}
#else
#define debug(...) 
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 2e5 + 10;
constexpr int MOD = 998244353;

int dx[]{0, 0, 1, -1};
int dy[]{1, -1, 0, 0};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n + 1, vector<int>(m + 1));
    vector<vector<int>> d(n + 1, vector<int>(m + 1, inf));
    queue<tuple<int, int, int>> q;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> a[i][j];
        }
    }
    auto bfs = [&]() {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (a[i][j]) {
                    q.emplace(i, j, 0);
                }
            }
        }
        while (q.size()) {
            auto [x, y, t] = q.front();
            q.pop();
            if (d[x][y] <= t) continue;
            d[x][y] = t;
            for (int i = 0; i < 4; ++i) {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx <= 0 || nx > n || ny <= 0 || ny > m || a[nx][ny]) continue;
                q.emplace(nx, ny, t + 1);
            }
        }
    };
    bfs();
    int mx = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            mx = max(mx, d[i][j]);
        }
    }
    auto check = [&](int t) {
        int xmin = -inf, xmax = inf;
        int ymin = -inf, ymax = inf;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (d[i][j] <= t) continue;
                int u = i + j, v = i - j;
                xmin = max(xmin, u - t);
                xmax = min(xmax, u + t);
                ymin = max(ymin, v - t);
                ymax = min(ymax, v + t);
                if (xmin > xmax || ymin > ymax) return false;
            }
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (a[i][j]) continue;
                int u = i + j, v = i - j;
                if (u >= xmin && u <= xmax && v >= ymin && v <= ymax) return true;
            }
        }
        return false;
    };

    int l = 0, r = mx;
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << "\n";
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

/*

  _  _                            _____             _               _               _    
 | \| |    ___    _ _      ___   |_   _|    _ _    (_)    __ __    (_)    __ _     | |   
 | .` |   / _ \  | ' \    |___|    | |     | '_|   | |    \ V /    | |   / _` |    | |   
 |_|\_|   \___/  |_||_|   _____   _|_|_   _|_|_   _|_|_   _\_/_   _|_|_  \__,_|   _|_|_  
_|"""""|_|"""""|_|"""""|_|     |_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""| 
"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-' 

(Font: ASCII - Train)

"El Psy Kongroo." -- Hououin Kyoma

"私は極色カスタ推しです...だが、狽音ウルシと夜鳴トバリも推す :)" -- Yukii_P

*/

K Perfect Journey

FMT做or卷积。思洋做的。常数有点大，m2*2m被卡，最后极限改成mlogm2m过了。题解说不能建树，要用别的性质，复杂度可以做到m2m，就行了。还没补，有空一定。唉。

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;
using i32 = int;
using i64 = long long;
using i128 = __int128;

template<typename T1,typename T2>
ostream& operator<<(ostream& o,const tuple<T1,T2>& t){
	return o<<"("<<get<0>(t)<<","<<get<1>(t)<<")";
}

template<typename T1,typename T2,typename T3>
ostream& operator<<(ostream& o,const tuple<T1,T2,T3>& t){
	return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";
}

template<typename T,const size_t S>
ostream& operator<<(ostream& o,const array<T,S>& arr){
	for(int i=(o<<"[",0);i<S;++i)o<<arr[i]<<(i+1<S?",":"");
	return o<<"]\n";
}

template<typename T>
ostream& operator<<(ostream& o,const vector<T>& vec){
	for(int i=(o<<"[",0);i<vec.size();++i)o<<vec[i]<<(i+1<vec.size()?",":"");
	return o<<"]\n";
}

template<typename T=int>
T read(){
	T res{0},f{1};
	char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){res=(res<<3)+(res<<1)+(ch^'0'),ch=getchar();}
	return res*f;
}

constexpr int M = 2e5+5, N = 1<<22, mod = 998244353;
constexpr double pi = acos(-1), eps = 1e-9;

template<bool type>
void FMT(int n,ll a[]){
	int m=1<<n;
	if constexpr(type){
		for(int i=1;i<m;i<<=1){
			for(int s=0;s<m;++s){
				if(s&i)continue;
				a[s^i]=(a[s^i]+a[s])%mod;
			}
		}
	}
	else{
		for(int i=1;i<m;i<<=1){
			for(int s=0;s<m;++s){
				if(s&i)continue;
				a[s^i]=(a[s^i]-a[s]+mod)%mod;
			}
		}
	}
	
	return;
}

ll a[N],b[N],t[N];

ll qpow(ll x,ll y){
	ll res=1;
	for(;y;y>>=1){
		if(y&1)res=res*x%mod;
		x=x*x%mod;
	}
	return res;
}

ll inv(ll x){
	return qpow(x,mod-2);
}

vector<array<int,2>> E;
vector<int> G[M];
vector<array<int,2>> route;

//int f[21][M];
//int depth[M];
//void dfs(int u){
//	depth[u]=depth[f[0][u]]+1;
//	for(int i=1;i<=20;++i){
//		f[i][u]=f[i-1][f[i-1][u]];
//	}
//	for(auto v:G[u]){
//		if(v==f[0][u])continue;
//		f[0][v]=u;
//		dfs(v);
//	}
//};
//
//int lca(int u,int v){
//	if(depth[u]>depth[v])swap(u,v);
//	for(int d=depth[v]-depth[u],i=0;i<=20;++i){
//		if((d>>i)&1)v=f[i][v];
//	}
//	if(u==v)return u;
//	for(int i=20;~i;--i){
//		if(f[i][u]!=f[i][v]){
//			u=f[i][u];
//			v=f[i][v];
//		}
//	}
//	return f[0][u];
//};

int col[23][M];
void dfs2(int x,int u,int fa){
	col[x][u]=1;
	for(auto v:G[u]){
		if(v==fa)continue;
		dfs2(x,v,u);
	}
}

void solve(){
	int n,m,k;
//	cin>>n>>m>>k;
	n=read(),m=read(),k=read();
//	int i=1;
	E.resize(n-1);
	for(auto& [u,v]:E){
//		cin>>u>>v;
		u=read(),v=read();
//		u=i,v=++i;
		G[u].emplace_back(v);
		G[v].emplace_back(u);
	}
	vector<int> key(m);
//	for(auto& i:key)cin>>i,--i;
	for(auto& i:key)i=read()-1;
//	iota(key.begin(),key.end(),1);
	route.resize(k);
//	for(auto& [u,v]:route)cin>>u>>v;
	for(auto& [u,v]:route)u=read(),v=read();
//	route=E;
	
//	dfs(1);
	
//	vector<ll> a(1<<m);
	int tot=0;
	for(int z=0;auto& i:key){
		auto& [x,y]=E[i];
		dfs2(z++,x,y);
	}
	int mxc=0;
	for(auto& [u,v]:route){
		int cur=0;
		for(int i=0;i<m;++i){
			cur<<=1;
			cur|=(col[i][u]!=col[i][v]);
		}
		tot|=cur;
		a[cur]++;
		mxc=max(mxc,__builtin_popcount(cur));
	}
	mxc=m-mxc+1;
//	for(auto& [u,v]:route){
//		int w=lca(u,v);
//		int cur=0;
//		for(auto& i:key){
//			cur<<=1;
//			auto& [x,y]=E[i];
//			if(depth[x]>depth[y])swap(x,y);
//			if(depth[y]<=max(depth[u],depth[v])&&depth[x]>=depth[w]){
//				if(depth[y]<=depth[u]&&lca(y,u)==y)cur|=1;
//				else if(depth[y]<=depth[v]&&lca(y,v)==y)cur|=1;
//			}
//		}
//		tot|=cur;
//		a[cur]++;
//	}
	int mm=(1<<m)-1;
	if(tot!=mm){
		cout<<"-1\n";
		return;
	}
	
	ll ans=a[mm];
	if(ans){
		cout<<"1 "<<ans<<"\n";
		return;
	}
//	vector<int> c(1<<m);
//	for(int s=0;s<(1<<m);++s){
//		c[s]=a[s]!=0;
//	}
	FMT<1>(m,a);
//	auto b=a;
//	auto t=b;
//	for(int s=0;s<(1<<m);++s){
//		b[s]=a[s];
//	}
	ll tt=1;
	int ans0=2;
	vector<ll> fac(30);
	fac[0]=1;
	for(int i=1;i<30;++i)fac[i]=fac[i-1]*i%mod;
	for(int l=2,r=mxc;l<=r;){
		int mid=(l+r)>>1;
		for(int s=0;s<(1<<m);++s){
			t[s]=qpow(a[s],mid)%mod;
		}
		FMT<0>(m,t);
		if(t[mm]){
			ans=t[mm]*inv(fac[mid])%mod;
			ans0=mid;
			r=mid-1;
		}
		else l=mid+1;
	}
//	for(;;++ans0){
//		if(ans0>mxc){
//			cout<<"-1\n";
//			return;
//		}
//		tt=tt*ans0%mod;
//		for(int s=0;s<(1<<m);++s){
//			b[s]=a[s]*b[s]%mod;
//			t[s]=b[s];
//		}
//		FMT<0>(m,t);
//		if(t[mm]){
//			ans=t[mm]*inv(tt)%mod;
//			break;
//		}
////		FMT<0>(m,b);
////		ll inv0=inv(ans0);
////		for(int s=0;s<(1<<m);++s){
////			if(c[s]){
////				b[s]=0;
////			}
////			else if(b[s]){
////				b[s]=b[s]*inv0%mod;
////				c[s]=1;
////			}
////		}
////		cout<<b;
////		if(b.back()){
////			ans=b.back();
////			break;
////		}
////		FMT<1>(m,b);
//	}
	cout<<ans0<<" "<<ans<<"\n";
	
	return;
}

int main() {
//	ios::sync_with_stdio(false);
//	cin.tie(0);
	
	int t{1};
//	cin>>t;
	while(t--){
		solve();
	}
	
	return 0;
}