2025 ICPC网络赛 II

The 2025 ICPC Asia East Continent Online Contest (II) - Dashboard - Contest - QOJ.ac

参考题解

https://zhuanlan.zhihu.com/p/1950637403929806516
https://zhuanlan.zhihu.com/p/1950647303397447122?share_code=xXFkS8dtjTCp&utm_psn=1950878150792811927

I DAG Query

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1010,mod=998244353;
int f[N];
int pre[N],suf[N],inv[N],fac[N];
int qpow(int b,int p=mod-2){
    int  res=1;
    while(p){
        if(p&1) res=res*b%mod;
        p>>=1;
        b=b*b%mod;
    }
    return res;
}
int Lagrange(int f[],int n,int x){
    if(x<=n) return f[x];
    int res=0;
    for(int i=0;i<=n+1;i++) fac[i]=suf[i]=inv[i]=pre[i]=0;
    fac[0]=suf[n+1]=inv[n+1]=1;
    pre[0]=(x+mod)%mod;
    for(int i=1;i<=n;i++){
         pre[i]=pre[i-1]*(x-i)%mod;
         pre[i]=(pre[i]+mod)%mod;
         fac[i]=fac[i-1]*i%mod;
    }
    inv[n]=qpow(fac[n]);
    for(int i=n;i>=0;i--){
        suf[i]=suf[i+1]*(x-i)%mod;
        suf[i]=(suf[i]+mod)%mod;
        if(i<n) inv[i]=inv[i+1]*(i+1)%mod;
    }
    if(n%2==0)res=(res+f[0]*suf[1]%mod*inv[n]%mod)%mod;
    else res=(res-f[0]*suf[1]%mod*inv[n]%mod+mod)%mod;
    for(int i=1;i<=n;i++){
        if((n-i)%2) res-=f[i]%mod*suf[i+1]%mod*pre[i-1]%mod*inv[i]%mod*inv[n-i]%mod;
        else res+=f[i]%mod*suf[i+1]%mod*pre[i-1]%mod*inv[i]%mod*inv[n-i]%mod;
        res=(res+mod)%mod;
    }
    return res;
}
signed main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
    }
    f[0]=0;
    for(int i=1;i<n;i++){
        cout<<"? "<<1<<' '<<n<<' '<<i<<endl;
        cin>>f[i];
    }
    int k;
    cout<<"!\n";
    cin>>k;
    cout<<Lagrange(f,n-1,k)<<endl;;
    return 0;
}

Arcane Behemoths

solutions

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353,N=2e5+10;
int a[N];
int qpow(int b,int p=mod-2){
    int res=1;
    while(p){
        if(p&1) res=res*b%mod;
        p>>=1;
        b=b*b%mod;
    }
    return res;
}
void solve(){
    int n;
    cin>>n;
    int ans=0;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++){
        ans+=qpow(2,n-i)*a[i]%mod*((1+qpow(2)*((qpow(3,i-1)-1+mod)%mod))%mod)%mod;
        ans%=mod;
    }
    cout<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--) solve();
    return 0;
}

考虑一个二分图 $G = (X, Y, E)$ ，其中 $X$ 是左侧节点集合（学生）， $Y$ 是右侧节点集合（问题）。每个右侧节点只能被匹配一次，但每个左侧节点 $x_i \in X$ 需要匹配至少 $k_i$ 个右侧节点。那么，存在这样的多重匹配当且仅当对于 $X$ 的任意子集 $S \subseteq X$ ，其邻居集合 $N(S) \subseteq Y$ 满足：
$|N(S)| \geq \sum_{x_i \in S} k_i$
在您的问题中，所有学生需要解决至少 $\text{mid}$ 个问题，即 $k_i = \text{mid}$ 对于所有 $i$ ，因此条件简化为：
$|N(S)| \geq \text{mid} \times |S|$
其中 $|N(S)|$ 是子集 $S$ 能解决的问题总数（即问题类型的数量之和）。
证明
我们可以通过将多重匹配问题转化为标准匹配问题来证明这个扩展。具体步骤如下：

节点复制：构造一个新的二分图 $G' = (X', Y', E')$ ：
· 对于每个左侧节点 $x_i \in X$ ，创建 $\text{mid}$ 个副本，即 $x_i^1, x_i^2, \ldots, x_i^{\text{mid}}$ 。因此， $X'$ 包含所有副本，且 $|X'| = \text{mid} \times |X|$ 。
· 右侧节点集 $Y' = Y$ （即问题集合，每个问题视为一个独立节点）。
· 边集 $E'$ ：如果原图中 $(x_i, y_j) \in E$ ，则在 $G'$ 中为每个副本 $x_i^k$ 添加边 $(x_i^k, y_j)$ 。
应用经典Hall定理：在 $G'$ 中，我们寻求一个匹配覆盖所有左侧副本（即每个副本匹配一个右侧节点）。经典Hall定理指出，这样的匹配存在当且仅当对于任意子集 $S' \subseteq X'$ ，有 $|N_{G'}(S')| \geq |S'|$ 。
关联原图：考虑原图 $G$ 中任意子集 $S \subseteq X$ 。在 $G'$ 中，让 $S'$ 是 $S$ 中所有节点的所有副本的集合，则 $|S'| = \text{mid} \times |S|$ 。由于每个副本都连接到与原节点相同的邻居，因此 $N_{G'}(S') = N_G(S)$ （即 $S$ 能解决的问题集合）。于是，条件变为： $|N_G(S)| \geq \text{mid} \times |S|$ 这正是扩展Hall定理的条件。
结论：如果对于所有 $S \subseteq X$ ，有 $|N_G(S)| \geq \text{mid} \times |S|$ ，则 $G'$ 满足经典Hall条件，从而存在匹配覆盖所有副本。这个匹配对应原图中的一个多重匹配，其中每个左侧节点 $x_i$ 匹配了 $\text{mid}$ 个右侧节点。反之，如果存在这样的多重匹配，则条件必须成立。

在您代码中的应用

在您的代码中，检查函数 $\text{check}(\text{mid})$ 正是验证扩展Hall定理的条件：

· 对于每个学生子集 $S$ （用位掩码 $s$ 表示），计算 $|S| = \text{popcount}(s)$ 。
· 计算 $|N(S)| = \sum \{ F[t] \mid \text{问题类型 } t \text{ 可以被 } S \text{ 中至少一个学生解决} \}$ 。
· 检查 $|N(S)| \geq \text{mid} \times |S|$ 是否成立。

如果所有子集都满足条件，则存在分配方式使得每个学生解决至少 $\text{mid}$ 个问题。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int f[8];
bool check(int mid){
    for(int s=1;s<8;s++){
        int sum=0;
        for(int t=1;t<8;t++){
            if(s&t) sum+=f[t];
        }
        if(mid*__builtin_popcount(s)>sum) return 0;
    }
    return 1;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        int s;
        cin>>s;
        for(int i=1;i<8;i++) cin>>f[i];
        int l=0,r=min({f[1]+f[3]+f[5]+f[7],f[2]+f[3]+f[6]+f[7],f[4]+f[5]+f[6]+f[7]});
        int ans;
        while(l<=r){
            int mid=(l+r)>>1;
            if(check(mid)){
                l=mid+1;
                ans=mid;
            }
            else r=mid-1;
        }
        cout<<ans<<'\n';
    }
    return 0;
}

Zero

题目大意

求长度为n的序列a[1],a[2]...a[n]，且满足以下条件的个数(模998244353)

满足 $0 \le a[1],a[2]...a[n]\le 2^m-1$
$a[i]\ne a[i+1],i=1,2,...n-1$

solution

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
int qpow(int b,int p=mod-2){
    int res=1;
    while(p){
        if(p&1) res=res*b%mod;
        p>>=1;
        b=b*b%mod;
    }
    return res;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        int ans;
        if(n&1) ans=qpow((qpow(2,m)-1+mod)%mod,n-1);
        else{
            ans=qpow((qpow(2,m)-1+mod)%mod,n-1);
            ans+=qpow((1-qpow(2,m)+mod)%mod,n/2);
            ans%=mod;
        }   
        cout<<ans<<'\n';
    }
    return 0;
}

2025 ICPC网络赛 II