本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-26 20:15:18

T1

枚举左端点，考虑怎么确定右端点。

首先要满足两个数字的位数一致，所以考虑先通过位数筛掉一些右端点。

注意到随着选择区间的增加，第一个数字的长度单调不增。

另外，选择的区间的总和的位数每增加一位，都需要增加很多选择的数字才可以。

对于同一个 $l$，最多连续大约 $6$ 个 $r$ 对应的最终位数是一致的。

也就是说，可能的右端点最多只有 $6$ 个，先二分找出可能的右端点区间（二分的根据是结果的位数），然后暴力枚举右端点判定。

T2

一开始，所有艺术家的可能作品集合都是 $1,2,\cdots,n$。

第一次操作后，划分为两个集合，集合内部每个艺术家的可能作品集合都一致，即所有集合内艺术家的作品都有可能是自己的作品。

第二次操作后，对于每个集合，再次根据本次的分组情况进行划分成两个集合。

一个集合划分之后如果大小变为 $1$，那么其就确定了。

T3

考虑二分答案，令答案为 $t$，首先保证二分上界不能超过最小区间的长度。

那么假设左端点为 $l$，右端点为 $r$，即 $r-l+1=t$。

答案将会是 $\sum\limits_{i=1}^n\max(0,L_i-l)+\max(0,r-R_i)$

上述式子改一下变为：
$$ \sum\limits_{i=1}^n(\max(0,L_i-l)+\max(0,l+t-1-R_i)) $$ 令 $U_i = R_i-t+1$，上式变为：
$$ \sum\limits_{i=1}^n(\max(0,L_i-l)+\max(0,l-U_i)) $$

$$ \sum\limits_{L_i \ge l}L_i-l + \sum\limits_{U_i \le l}l-U_i $$

从一开始，$l$ 不断增加，答案会先减少再上升。

考虑三分 $l$。

T4

实际上已知最终的顺序。

考虑按照最终的顺序逐个扫描。

合法的前提是相邻后一项的最大成绩小于等于（能否等于得看 id）前一项的最大成绩。

$f_{i,j}$ 表示已经确定了前 $i$ 个选手的方案，总共隐藏 $j$ 题，此时最后一个人的最大的公开成绩。

可以粗略的估计，所有选手隐藏题目个数的总和不超过 $M$。

假设隐藏了 $M+1$ 个题目。

首先，初始情况下最高分减去最低分最多为 $M \cdot K$。

若隐藏了 $M+1$ 个问题，那么意味着中间的差值减少了 $(M+1)\cdot K$，无论如何都不能保证原来的顺序。

现在需要知道每个选手有哪些方案。

$g_{i,j,k}$：当前选手考虑了前 $i$ 道题，公开了 $j$ 个，此时公开总和为 $k$ 是否可行。

转移：逐个扫描题目：

• $g_{i+1,j+1,k+v_{i+1}} \leftarrow g_{i,j,k}$
• $g_{i+1,j,k}\leftarrow g_{i,j,k}$。

其中 $v_i$ 表示当前选手对于第 $i$ 题的分数。

暴力转移复杂度将会是 $O(m^3k)$ 的。

加上 bitset 优化后变为 $O(\frac{m^3k}{\omega})$ 。

对于 $f$ 本身的转移，需要枚举下一个人的公开成绩，以及公开题目个数。

那么 $f$ 的求解总复杂度将会是 $O(nm^3k)$。

总复杂度 $O(nm^3k+\frac{m^3k}{\omega})$，期望 72pts，irris 说开 O3 优化能过。

考虑哪些状态有效。

重定义状态 $g_{i,j,s}$ 表示当前选手考虑了前 $i$ 道题，公开了 $j$ 个，真实总和减去隐藏总和的值为 $s$ 是否可行。

令 $id$ 表示当前选手编号，注意到 $s \ge score_{id+1}$。

也就是说，$s \in [score_{id+1},score_{id}]$。

仅保留有效的 $s$，那么注意到所有选手的 $g$ 的有效状态数加起来仅有 $O(m^2\sum\limits_{i=1}^n(score_i-score_{i+1})) = O(m^3k)$，其中 $score_{n+1}$ 视为 $0$。

再分析一下 $f$ 此时的转移复杂度。

每一层分别加和，得到 $\sum\limits_{i=1}^n (score_i-score_{i+1})m^2 = O(m^3k)$。

再算上一开始的排序，总复杂度将是 $O(n\log n + m^3k)$。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-04 11:44:43

• 结论一：

  能成为冠军的人，在任意一张地图的排行榜上构成一个前缀。

• 证明：

  假设某一张地图上存在 $i \lt j$，且排名为 $i$ 的人无法成为冠军，但排名为 $j$ 的人可以成为冠军，那么由排名为 $j$ 的人击败除了排名为 $i$ 的人以外的所有的人，然后再由排名为 $i$ 的人击败排名为 $j$ 的人，那么排名为 $i$ 的人就可以成为冠军，与假设矛盾。

• 结论二：

  三张地图的冠军前缀长度相等。

• 证明：

  假设三张地图的冠军构成的前缀长度从小到大依次为 $len_1,len_2,len_3$，且 $len_1 \neq len_3$。

  那么，对于长度为 $len_3$ 的冠军前缀，其在另外两个排行榜上同样占据 $len_3$ 个人，所有排名小于等于这些人的，同样构成冠军，那么也就是说 $len_1$ 肯定大于等于 $len_3$，与假设矛盾。

考虑如何确定前缀的长度，假定其为 $len$。

那么任意一个冠军的最差排名不会高于 $len$。

另外，必然存在至少一个冠军的最差排名为 $len$，否则排名为 $len$ 的人无论如何也无法击败任意一个冠军，也就没有排名为 $len$ 的人能成为冠军。

那么现在已经确定了条件：

• 令选手 $i$ 的最优排名为 $l_i$，最差排名为 $r_i$，那么 $len$ 就是最小的位置，使得不存在任意一个区间左端点小于 $len$，右端点大于等于 $len$。

对于每个位置，记录左端点小于等于其的区间个数减去右端点小于等于其的区间个数。

这个数字肯定是一个非负整数，现在要找的就是第一个 $0$ 的位置。

那么，考虑使用线段树，其支持以下操作：

• 区间加法。

  修改操作需要用到。

• 维护区间最小值。

  用于确定区间是否存在 $0$。

• 二分查找第一个 $0$ 的位置。

  这个需要依赖区间最小值。

一种可以通过的代码实现：

#include <bits\/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
#define FORK(i,a,b,k) for(auto i=(a);i<=(b);i+=(k))
#define REPK(i,a,b,k) for(auto i=(a);i>=(b);i-=(k))
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a\/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
#define islower(ch) (ch>='a'&&ch<='z')
#define isupper(ch) (ch>='A'&&ch<='Z')
#define isalpha(ch) (islower(ch)||isupper(ch))
template<class T>
void wrint(T x){
    if(x<0){
        x=-x;
        pc('-');
    }
    if(x>=10){
        wrint(x\/10);
    }
    pc(x%10^48);
}
template<class T>
void wrintln(T x){
    wrint(x);
    pln
}
template<class T>
void read(T& x){
    x=0;
    int f=1;
    char ch=gc;
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=gc;
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=gc;
    }
    x*=f;
}
void ioopti(){
    ios::sync_with_stdio(0);
    cin.tie(0);
}
void io(){
    freopen("champion.in","r",stdin);
    freopen("champion.out","w",stdout);
}
const int maxn=1e5+5;
struct SGT{
    int mn[maxn<<2],lazy[maxn<<2];
    int lef[maxn<<2],rig[maxn<<2];
    void pushup(int pos){
        mn[pos]=min(mn[pos<<1],mn[pos<<1|1]);
    }
    void upd(int pos,int _add){
        mn[pos]+=_add;
        lazy[pos]+=_add;
    }
    void pushdown(int pos){
        if(!lazy[pos])return;
        upd(pos<<1,lazy[pos]);
        upd(pos<<1|1,lazy[pos]);
        lazy[pos]=0;
    }
    void bd(int pos,int l,int r){
        lef[pos]=l,rig[pos]=r;
        if(l==r)return;
        int mid=(l+r>>1);
        bd(pos<<1,l,mid);
        bd(pos<<1|1,mid+1,r);
        pushup(pos);
    }
    void add(int pos,int l,int r,int _add){
        if(lef[pos]>=l&&rig[pos]<=r){
            upd(pos,_add);
            return;
        }
        pushdown(pos);
        int mid=(lef[pos]+rig[pos]>>1);
        if(mid>=l)add(pos<<1,l,r,_add);
        if(mid<r)add(pos<<1|1,l,r,_add);
        pushup(pos);
    }
    int find(int pos){
        if(lef[pos]==rig[pos]){
            return lef[pos];
        }
        pushdown(pos);
        if(mn[pos<<1]==0)return find(pos<<1);
        return find(pos<<1|1);
    }
}sgt;
int n,q;
int rklist[4][maxn];
int pos[4][maxn];
int l[maxn],r[maxn];
void solve(int id_of_test){
	read(n);
    read(q);
    memset(l,0x3f,sizeof l);
    sgt.bd(1,1,n);
    FOR(i,1,3){
        FOR(j,1,n){
            read(rklist[i][j]);
            pos[i][rklist[i][j]]=j;
            ckmn(l[rklist[i][j]],j);
            ckmx(r[rklist[i][j]],j);
        }
    }
    FOR(i,1,n){
        sgt.add(1,l[i],n,1);
        sgt.add(1,r[i],n,-1);
    }
    while(q--){
        int op;
        read(op);
        if(op==1){
            int x;
            read(x);
          \/\/  printf("sgt.find1 = %d\n",sgt.find(1));
            if(min({pos[1][x],pos[2][x],pos[3][x]})<=sgt.find(1)){
                puts("DA");
                continue;
            }
            puts("NE");
        }else{
            int p,a,b;
            read(p);
            read(a);
            read(b);
            sgt.add(1,l[a],n,-1);
            sgt.add(1,r[a],n,1);
            sgt.add(1,l[b],n,-1);
            sgt.add(1,r[b],n,1);
            int &id1=pos[p][a],&id2=pos[p][b];
            swap(rklist[p][id1],rklist[p][id2]);
            swap(id1,id2);
            l[a]=min({pos[1][a],pos[2][a],pos[3][a]});
            r[a]=max({pos[1][a],pos[2][a],pos[3][a]});
            l[b]=min({pos[1][b],pos[2][b],pos[3][b]});
            r[b]=max({pos[1][b],pos[2][b],pos[3][b]});
            sgt.add(1,l[a],n,1);
            sgt.add(1,r[a],n,-1);
            sgt.add(1,l[b],n,1);
            sgt.add(1,r[b],n,-1);
        }
    }
}
int main()
{
    \/\/ io();
	int T;
	T=1;
	FOR(_,1,T){
		solve(_);
	}
	return 0;
}
\/*
1. 对题意的理解能否和样例对的上？  
2. 每一步操作，能否和自己的想法对应上？  
3. 每一步操作的正确性是否有保证？  
4. 是否考虑到了所有的 case？特别是极限数据。
5. 变量的数据类型是否与其值域匹配？
6. 时间复杂度有保证吗？
7. 空间多少 MB？  
*\/

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-04-25 10:29:25

做法介绍

本题解与题解区所有题解做法都不相同，不需要 FWT 或 bitset。

令 $m$ 的质因数数量为 $c$，那么本做法复杂度为 $O(\sqrt m + (2^{c}+n)c)$。

一些前置思考

考虑 lcm 的性质。

一些数的 lcm，本质上是这些数的每个质因数的次数取最大值，然后乘起来。

首先，如果一个数不是 $m$ 的因数，那么这个数一定不会出现在最终的答案集合，先将这个数从输入的数组删除，接下来的分析均只考虑剩下的数。

现在，一种选择方案是合法的，当且仅当，对于 $m$ 的每个质因数 $p$，本选择方案里面存在一个数，使得这个数里面 $p$ 的次数等于 $m$ 里面 $p$ 的次数。

容易发现，$m$ 的质因数个数小于等于 $14$，这就提示我们使用状态压缩。

现在，根据上述方案，可以计算出输入数组中的每个数可以搞定 $m$ 的哪些质因数。

现在，问题转化为：

给定一个整数数组 $a$，$\forall 1 \le i \le n,0 \le a_i \lt 2^{14}$。
给定一个正整数 $m \lt 2^{14}$，求 $a$ 的子序列个数，使得子序列内部所有数的或值等于 $m$，子序列不同当且仅当选择的位置集合不同。

转化后的处理

考虑容斥。

可以限制一下哪些位可以是 $1$，枚举这些位。

令 $g(msk)$ 代表只有 $msk$ 集合的位可以是 $1$，此时选择位置集合的方案数。

显然，令 $x$ 代表只有 $msk$ 集合的位可能是 $1$ 的数的个数，那么 $g(msk) = 2^{x}-1$。

问题是，如何快速对于每个 $msk$，求出对应的 $x$。

这个很经典，是 SOSDP 的板子。

令 $popcount(msk)$ 为 $msk$ 集合的大小，$all$ 代表全集。

那么如果 $popcount(all)-popcount(msk)$ 是偶数，那么答案加上 $g(msk)$，否则减去 $g(msk)$。

对 $m$ 质因数分解的复杂度为 $O(\sqrt m)$，预处理每个输入的数对应的状态的复杂度为 $O(nc)$，SOSDP 的复杂度为 $O(2^cc)$，容斥的复杂度为 $O(2^c)$。

故复杂度 $O(\sqrt m + (n+2^c)c)$。

#include <bits\/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
#define FORK(i,a,b,k) for(auto i=(a);i<=(b);i+=(k))
#define REPK(i,a,b,k) for(auto i=(a);i>=(b);i-=(k))
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a\/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
#define islower(ch) (ch>='a'&&ch<='z')
#define isupper(ch) (ch>='A'&&ch<='Z')
#define isalpha(ch) (islower(ch)||isupper(ch))
template<class T>
void wrint(T x){
    if(x<0){
        x=-x;
        pc('-');
    }
    if(x>=10){
        wrint(x\/10);
    }
    pc(x%10^48);
}
template<class T>
void wrintln(T x){
    wrint(x);
    pln
}
template<class T>
void read(T& x){
    x=0;
    int f=1;
    char ch=gc;
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=gc;
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=gc;
    }
    x*=f;
}
const ll mod=998244353;
const int maxn=2e5+5;
ll qpow(ll a,ll b){
    ll ret=1;
    for(;b;a=a*a%mod,b>>=1){
        if(b&1){
            ret=ret*a%mod;
        }
    }
    return ret;
}
ll inv(ll a){
    return qpow(a,mod-2);
}
ll fact[maxn],factinv[maxn];
ll C(int n,int m){
    return n<m?0:fact[n]*factinv[m]%mod*factinv[n-m]%mod;
}
int n;
ll m,a[maxn];
int psgdivs[maxn];
ll pdivs[maxn];
int pdcnt;
void split(){
    ll _=m;
    for(ll i=2;i*i<=_;i++){
        if(_%i==0){
            pdivs[++pdcnt]=1;
            psgdivs[pdcnt]=i;
            while(_%i==0)_\/=i,pdivs[pdcnt]*=i;
        }
    }
    if(_>=2)pdivs[++pdcnt]=_,psgdivs[pdcnt]=_;
}
int pre[1<<14];
ll pw2[maxn];
void solve(int id_of_test){
	read(n);
    read(m);
    FOR(i,1,n){
        read(a[i]);
    }
    split();
    FOR(i,1,n){
        int msk=0;
        FOR(j,1,pdcnt){
            if(a[i]%pdivs[j]==0&&(a[i]\/pdivs[j])%psgdivs[j]!=0){
                msk|=(1<<j-1);
            }
        }
        if(m%a[i]==0)pre[msk]++;
    }
    int all=(1<<pdcnt)-1;
    FOR(bit,0,pdcnt-1){
        FOR(msk,0,all){
            if(msk&(1<<bit)){
                pre[msk]+=pre[msk^(1<<bit)];
            }
        }
    }
    ll ans=0;
    FOR(msk,0,all){
        ll mul=1;
        if(__builtin_parity(all^msk)){
            mul*=-1;
        }
        (ans+=(pw2[pre[msk]]-1)*mul)%=mod;
    }
    printf("%lld\n",(ans+mod)%mod);
}
int main()
{
    pw2[0]=1;
    FOR(i,1,maxn-1)pw2[i]=pw2[i-1]*2%mod;
    fact[0]=1;
    FOR(i,1,maxn-1)fact[i]=fact[i-1]*i%mod;
    factinv[maxn-1]=inv(fact[maxn-1]);
    REP(i,maxn-1,1){
        factinv[i-1]=factinv[i]*i%mod;
    }
	int T;
	T=1;
	FOR(_,1,T){
		solve(_);
	}
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-04-28 09:45:46

本题解做法比较暴力，容斥过程需要一步步拆解成子问题，每次都通过容斥转化。而能单次完成容斥的方法，别的题解已经写了。

一些分析

车的攻击范围包括一行和一列。

每个车均会覆盖某行和某列，要求找到摆放方案数，使得黑方和白方的覆盖范围互不重叠。

可以考虑枚举黑方，白方分别占据了多少行，多少列。

实际做法

假设 $f(i,j)$ 代表黑方占据已经选定的 $i$ 行 $j$ 列的摆放方案数，$g(i,j)$ 代表白方占据已经选定的 $i$ 行 $j$ 列的方案数。

那么答案是：
$$ \sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{k=1}^{n-i}\sum\limits_{l=1}^{m-j}\binom{n}{i}\binom{m}{j}\binom{n-i}{k}\binom{m-j}{l} f(i,j)g(k,l) $$

考虑怎么求出 $f$，然后 $g$ 的求解方法同理。

令 $f'(i,j)$ 代表最多选择 $i$ 行，强制选择 $j$ 列的方案数。

根据二项式反演，得 $f(i,j) = \sum\limits_{i'=1}^{i}\binom{i}{i'}(-1)^{i-i'}f'(i',j)$。

令 $f''(i,j)$ 代表限制最多选择 $i$ 行，最多选择 $j$ 列的方案数。

显然 $f''(i,j) = \binom{ij}{b}$。

根据二项式反演，得 $f'(i,j) = \sum\limits_{j'=1}^j\binom{j}{j'}(-1)^{j-j'}f''(i,j')$。

先求出 $f''$，然后求出 $f'$，最后求出 $f'$ 就完成了。

#include <bits\/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
#define FORK(i,a,b,k) for(auto i=(a);i<=(b);i+=(k))
#define REPK(i,a,b,k) for(auto i=(a);i>=(b);i-=(k))
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a\/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
#define islower(ch) (ch>='a'&&ch<='z')
#define isupper(ch) (ch>='A'&&ch<='Z')
#define isalpha(ch) (islower(ch)||isupper(ch))
template<class T>
void wrint(T x){
    if(x<0){
        x=-x;
        pc('-');
    }
    if(x>=10){
        wrint(x\/10);
    }
    pc(x%10^48);
}
template<class T>
void wrintln(T x){
    wrint(x);
    pln
}
template<class T>
void read(T& x){
    x=0;
    int f=1;
    char ch=gc;
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=gc;
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=gc;
    }
    x*=f;
}
const ll mod=998244353;
ll qpow(ll a,ll b){
    ll ret=1;
    for(;b;a=a*a%mod,b>>=1){
        if(b&1)ret=ret*a%mod;
    }
    return ret;
}
ll inv(ll a){
    return qpow(a,mod-2);
}
const int maxn=55;
ll fact[maxn*maxn],factinv[maxn*maxn];
ll C(int n,int m){
    return n<m?0:fact[n]*factinv[m]%mod*factinv[n-m]%mod;
}
int n,m,b,w;
ll f1[maxn][maxn],f2[maxn][maxn],f3[maxn][maxn],g1[maxn][maxn],g2[maxn][maxn],g3[maxn][maxn];
void solve(int id_of_test){
	read(n);
    read(m);
    read(b);
    read(w);
    FOR(i,1,n){
        FOR(j,1,m){
            \/\/ 限制选 i 行，j 列。
            f3[i][j]=C(i*j,b);
        }
    }
    FOR(i,1,n){
        FOR(j,1,m){
            ll ml=1;
            REP(lsti,i,1){
                (f2[i][j]+=f3[lsti][j]*C(i,lsti)%mod*ml%mod)%=mod;
                ml*=-1;
            }
        }
    }
    FOR(i,1,n){
        FOR(j,1,m){
            ll ml=1;
            REP(lstj,j,1){
                (f1[i][j]+=f2[i][lstj]*C(j,lstj)%mod*ml%mod)%=mod;
                ml*=-1;
            }
        }
    }
    \/\/ calc g
    FOR(i,1,n){
        FOR(j,1,m){
            \/\/ 限制选 i 行，j 列。
            g3[i][j]=C(i*j,w);
        }
    }
    FOR(i,1,n){
        FOR(j,1,m){
            ll ml=1;
            REP(lsti,i,1){
                (g2[i][j]+=g3[lsti][j]*C(i,lsti)%mod*ml%mod)%=mod;
                ml*=-1;
            }
        }
    }
    FOR(i,1,n){
        FOR(j,1,m){
            ll ml=1;
            REP(lstj,j,1){
                (g1[i][j]+=g2[i][lstj]*C(j,lstj)%mod*ml%mod)%=mod;
                ml*=-1;
            }
        }
    }
    ll ans=0;
    FOR(r1,1,n){
        FOR(c1,1,m){
            FOR(r2,1,n){
                FOR(c2,1,m){
                    (ans+=f1[r1][c1]*g1[r2][c2]%mod*C(n,r1)%mod*C(m,c1)%mod*C(n-r1,r2)%mod*C(m-c1,c2)%mod)%=mod;
                }
            }
        }
    }
    printf("%lld\n",(ans+mod)%mod);
}
int main()
{
    fact[0]=1;
    FOR(i,1,maxn*maxn-1)fact[i]=fact[i-1]*i%mod;
    factinv[maxn*maxn-1]=inv(fact[maxn*maxn-1]);
    REP(i,maxn*maxn-1,1)factinv[i-1]=factinv[i]*i%mod;
	int T;
	T=1;
	FOR(_,1,T){
		solve(_);
	}
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-04-29 21:12:12

本文章不是什么正经的讲解，纯娱乐，另外引用了别人的代码，如果侵权可以联系删除。

我大约 4 年前在 CSDN 写的这个，看到不少人写这个类型的专栏，我也放在洛谷试试。

软件准备

首先，安装 VMware，版本没有什么要求。

再安装 nasm 并配好环境变量，用来将汇编源码编译为可执行文件。

之所以不用 masm 是因为 masm 不能在 64 位系统用。

实际操作

先创建一个文件，命名为 boot.s，内容如下：

BOOTSEG equ 0x07c0              ; BIOS 加载 bootsect 代码的原始段地址；

start:
        jmp BOOTSEG:go          ; 段间跳转。 INITSEG 指出跳转段地址， 标号 go 是偏移地址。
go:
        mov ax,cs               ; 段寄存器 cs 值-->ax，用于初始化数据段寄存器 ds 和 es。
        mov ds,ax
        mov es,ax
;画图
        mov ah,00
        mov al,06h
        int 10h ;设置640*480、16色彩色分辨率
        mov dx,50
back_1:
        mov cx,100
back_2:
        mov ah,0ch
        mov al,71h ;白底蓝色图 
        mov bh,0
        int 10h
        inc cx
        cmp cx,100
        jnz back_2
        inc dx
        cmp dx,150
        jnz back_1
loop1:  jmp loop1               ; 死循环。

        times 510-($-$$) db 0   ; 表示以后语句从地址 510(0x1FE)开始存放。
        dw 0xAA55               ; 有效引导扇区标志， 供 BIOS 加载引导扇区使用。

再在其同一文件夹下新建一个名为 makeos.bat 的文件。
内容如下：

nasm -f bin boot.s -o boot
dd if=boot of=boot.img
pause

注：dd 命令用于制作 img 映像。

然后，运行 makeos.bat，下面是结果，理论上会生成一个 boot.img。

然后使用 VMware 创建虚拟机。

操作系统选择“其他”。

接下俩的操作，均按照默认就可以。

完成创建之后，添加硬件，此时应选择软盘驱动器，软盘则选择源码文件夹下的 boot.img。

选择界面：

最后，启动虚拟机。

注：需要将 VMware 最大化，否则显示不正常。

下面是正常的效果：

引用

程序 boot.s 的源代码来自于一本书，我忘了什么名字。不过当时讲的仅仅是一个界面绘制，我把它搬运到了系统启动。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-05-03 23:41:14

凭什么这题分值比差分约束板子的 G 低！我这种过 F 不过 G 的亏死了。

难点

拆答案的贡献。

做法

每次游戏都随机排列，意思其实就是每次游戏结束前，都得不到任何关于正确按钮的位置信息。

那么，值得用于决策的信息就只剩下了当前的正确选择次数，当前剩下的游戏次数。

首先，可以自然的想到定义 $f_{i,j}$ 代表还剩下 $i$ 次游戏可以玩，还需要选中 $j$ 次正确按钮才可以获得最终胜利。

转移的话，考虑当前这次游戏怎么玩。

似乎不是很好设计策略，那么来分析一下答案的贡献组成。

本次游戏假设有 $x$ 个按钮的选中次数不为 $0$，其中第 $l$ 个按钮被选中了 $c_l$ 次。

那么，每个按钮都有 $\frac{1}{n}$ 的概率是正确的按钮，此时状态推进到 $f_{i-1,j-c_l}$，贡献是 $\frac{1}{n}f_{i-1,j-c_l}$。

有 $\frac{n-x}{n}$ 的概率所有 $x$ 个按钮都不是正确的按钮，贡献是 $\frac{n-x}{n}f_{i-1,j}$。

所以，一种方案的答案就是 $\frac{1}{n}\sum\limits_{l=1}^n f_{i-1,j-c_l}+\frac{n-x}{n}f_{i-1,j}$。

可以看出来，答案跟选择的按钮数量，每个被选择的按钮的操作次数有关，而且每个按钮的贡献都是独立的，可以累加。

由此，可以对答案的第一项进行 dp，按钮数量也需要加入状态。

令 $g_{i,j}$ 表示选择了 $i$ 个按钮，总共用了 $j$ 次操作，且每个按钮至少操作 $1$ 次，答案式子的第一项的最大总和是多少。

$f_{i,j} = \max\limits_{x=0}^{\min(n,m)}{(g_{x,m}+\frac{n-x}{n}f_{i-1,j})}$。

时间复杂度是 $O(TKM^3)$ 的，听说有人用爆搜也过了。

Accepted Submission

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-05-06 11:14:13

首先，可以使用 BFS 计算不瞬移的答案。

假设最后一次瞬移到达了 $x$ 点，当然 $x \neq s$。

这意味着编号 $\in [0,x-1]$ 的所有点都必须经过一遍。此时到达 $x$ 点的总代价将至少是 $x+1-[s \lt x]$。

而如果从 $s$ 出发就一直瞬移，直到到达 $x$，那么就能达到这个最小的代价。

令 $dis(x,y)$ 代表不瞬移，仅从给定边走，从 $x$ 到 $y$ 的最短路径长度，令 $f(x)$ 代表最后一次瞬移到达 $x$ 的情况下，从 $s$ 到 $x$ 的最小代价。

枚举 $x \in [0,n-1]$，答案就是 $f(x)+dis(x,t)$ 的最小值。

快速计算 dis，则只需要一次 bfs 预处理。

时间复杂度 $O(n)$。

std

#include <bits\/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
#define gc getchar()
#define pc putchar
#define pln pc(10);
#define eb emplace_back
template<class T>
void ckmx(T& a,T b){
	a=max(a,b);
} 
template<class T>
void ckmn(T& a,T b){
	a=min(a,b);
}
template<class T>
T gcd(T a,T b){
	return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
	return a\/gcd(a,b)*b;
}
template<class T>
void read(T& x){
	x=0;
	int f=1;
	char ch=gc;
	while(!isdigit(ch)){
		if(ch=='-')f=-1;
		ch=gc;
	} 
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=gc;
	}
	x*=f;
}
template<class T>
void wrint(T x){
	if(x>=10)wrint(x\/10);
	pc(x%10^48);
}
const int maxn=2e5+5;
int n,m,s,t;
vi g[maxn];
int dis[maxn];
void solve(int id_of_testcase){
	read(n);
	read(m);
	read(s);
	read(t);
	FOR(i,1,m){
		int u,v;
		read(u);
		read(v);
		g[u].eb(v);
		g[v].eb(u);
	}
	FOR(i,0,n-1)dis[i]=1e9;
	queue<int> q;
	dis[t]=0;
	q.push(t);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int& v:g[u]){
			if(dis[v]>dis[u]+1){
				dis[v]=dis[u]+1;
				q.push(v); 
			}
		}
	}
	int ans=dis[s];
	FOR(i,0,n-1){
		int ds=dis[i]+i+1;
		if(i>=s)ds--;
		ckmn(ans,ds);
	}
	wrint(ans);
	pln
	FOR(i,0,n-1){
		g[i].clear(); 
	}
}
int main(){
	int T;
	read(T);
	FOR(_,1,T){
		solve(_);
	}
	return 0;
}

验题人 @Tiffake 的代码：

#include<bits\/stdc++.h>
#define int long long
#define pair pair<int,int>
#define fst first
#define snd second
using namespace std;
const int N=3e5+1;
int T,n,m,s,t,x,y,ans,d[N];
priority_queue<pair,vector<pair>,greater<pair>>q;
vector<int>v[N];
bitset<N>vis;
inline void dijkstra(){
	for(int i=0;i<n;i++)d[i]=INT_MAX>>2;
	d[t]=0,q.push({0,t});
	while(!q.empty()){
		int u=q.top().snd;q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(int i:v[u]){
			if(d[i]>d[u]+1){
				d[i]=d[u]+1;
				q.push({d[i],i});
			}
		}
	}
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>m>>s>>t,ans=INT_MAX,vis.reset();
		for(int i=0;i<n;i++)v[i].clear();
		while(m--)cin>>x>>y,v[x].push_back(y),v[y].push_back(x);
		dijkstra();
		for(int i=0;i<s;i++)ans=min(ans,d[i]+i+1);
		for(int i=s+1;i<n;i++)ans=min(ans,d[i]+i);
		cout<<min(ans,d[s])<<'\n';
	}
	return 0;
}

验题人 @Lastkismet 的代码：

#include<bits\/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
template<typename T> using vec=vector<T>;
template<typename T> using grheap=priority_queue<T>;
template<typename T> using lrheap=priority_queue<T,vector<T>,greater<T>>;
#define fir first
#define sec second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define rep(i,x,y) for(int i=(x);i<=(y);i++)
#define per(i,x,y) for(int i=(x);i>=(y);i--)
#define repl(i,x,y) for(int i=(x);i<(y);i++)
#define file(f) freopen(#f".in","r",stdin);freopen(#f".out","w",stdout);

struct mint {
	int x,mod;
	inline mint(int o=0,int p=998244353) {x=o;mod=p;}
	inline mint & operator=(ll o){return x=o%mod,(x+=mod)>=mod&&(x-=mod),*this;}
	inline mint & operator+=(mint o){return (x+=o.x)>=mod&&(x-=mod),*this;}
	inline mint & operator-=(mint o){return (x-=o.x)<0&&(x+=mod),*this;}
	inline mint & operator*=(mint o){return x=(ll)x*o.x%mod,*this;}
	inline mint & operator^=(ll b){mint res(1);for(;b;b>>=1,*this*=*this)if(b&1)res*=*this;return x=res.x,*this;}
	inline mint & operator^=(mint o){return *this^=o.x;}
	inline mint & operator\/=(mint o){return *this*=(o^=(mod-2));}
	inline mint & operator++(){return *this+=1;}
	inline mint & operator--(){return *this-=1;}
	inline mint operator++(int o){mint res=*this;return *this+=1,res;}
	inline mint operator--(int o){mint res=*this;return *this-=1,res;}
	friend inline mint operator+(mint a,mint b){return a+=b;}
	friend inline mint operator-(mint a,mint b){return a-=b;}
	friend inline mint operator*(mint a,mint b){return a*=b;}
	friend inline mint operator\/(mint a,mint b){return a\/=b;}
	friend inline mint operator^(mint a,ll b){return a^=b;}
	friend inline mint operator^(mint a,mint b){return a^=b;}
	friend inline bool operator<(mint a,mint b){return a.x<b.x;}
	friend inline bool operator>(mint a,mint b){return a.x>b.x;}
	friend inline bool operator<=(mint a,mint b){return a.x<=b.x;}
	friend inline bool operator>=(mint a,mint b){return a.x>=b.x;}
	friend inline bool operator==(mint a,mint b){return a.x==b.x;}
	friend inline istream & operator>>(istream &in,mint &o){ll x;return in>>x,o=x,in;}
	friend inline ostream & operator<<(ostream &ot,mint o){return ot<<o.x,ot;}
};

const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;

const int N=2e5+5;

int n,m,s,t;
int dis[2][N];
vec<int> g[N];

void bfs(int be,int kd){
	queue<int> q;
	q.push(be);
	while(!q.empty()){
		int now=q.front();q.pop();
		for(auto nxt:g[now])if(dis[kd][nxt]>dis[kd][now]+1){
			dis[kd][nxt]=dis[kd][now]+1;
			q.push(nxt);
		}
	}
}

void solve(){
	cin>>n>>m>>s>>t;
	repl(i,0,n)g[i].clear(),dis[0][i]=dis[1][i]=inf;
	rep(i,1,m){
		int u,v;cin>>u>>v;
		g[u].pub(v);
		g[v].pub(u);
	}
	dis[0][s]=dis[1][t]=0;
	bfs(s,0);bfs(t,1);
	int ans=inf;
	repl(i,0,n)chmin(ans,dis[1][i]+min(dis[0][i],i+(i<=s)));
	if(ans==inf)ans=-1;
	cout<<ans<<"\n";
}

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

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-05-06 20:29:35

出题人题解。

出题人做法

假设 $b(x,i)$ 表示非负整数 $x$ 的二进制表示中，从 $0$ 位算起，从低到高的第 $i$ 位的值。

假设 $lim=0$，即不存在对树的修改操作，也不存在附加代价的情况下，树的价值是多少。

显然，$s$ 必然等于 $all(i)$。

那么，先不考虑后面减去的那一项，答案会是什么样子。

此时，每操作一个节点 $u$，就相当于加上

$$ \sum\limits_{0 \le i \le 63} \sum\limits_{v \in all(i) }[b(u,i) \gt b(v,i)]2^i
$$

另外，每个节点最多被操作 $1$ 次，因为第二次操作不可能有贡献。

令 $dis(u,v)$ 表示 $u$ 点到 $v$ 点所需要经过的最少边数。

那么，所有的节点操作的贡献总和，似乎很像某个值？

一个我认为最容易想到的猜想： $\sum\limits_{dis(u,v)=1}(a_u \oplus a_v)$

然后，实际上上述操作（假设仍然忽略掉减少项）的总贡献并不是这个值。

原因是，一个数 $u$ 清零之后，原本如果一个位，使 $u$ 和它相邻的节点 $v$ 这一位都是 $1$，那么这一位原本不应该在任何时候产生贡献。

但是，操作了 $u$ 之后再操作 $v$，就导致这些位的贡献被错误地计算，因为 $u$ 的这一位的值被作为 $0$ 参与计算了。

这时候，再考虑题目式子中减去的那个值，发现刚好将这一项贡献减掉了。

所以猜想成立。

那么现在，如何考虑那两种对于树本身的修改呢？

对于第一种操作，考虑两个相邻点 $u,v$ ，如果不断开边，那么 $u,v$ 之间的贡献就是 $a_u \oplus a_v$，而断开边，需要多出 $a_u + a_v$ 的贡献，$a_u + a_v \ge a_u \oplus a_v$，这显然是不优的。

所以，第一种操作永远不会被执行。

对于第二种操作，考虑 dp。

树形 dp，令 $f_{u,i,0/1}$ 表示 $u$ 为根的子树执行了 $i$ 次删除操作，$u$ 自己被删或没被删，此时的最小总价值是多少。

审核管理做法

不观察到异或性质也可以通过本题，方法是设置边权，但是这种方法相对复杂。

加强版做法

我也不会，一个 7 级钩出题人显然是不会做黑题的。
但是既然做法存在，我就设置了 5 元的最优解奖金来征求 std。

std

#include <bits\/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
#define FORK(i,a,b,k) for(auto i=(a);i<=(b);i+=(k))
#define REPK(i,a,b,k) for(auto i=(a);i>=(b);i-=(k))
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a\/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
#define islower(ch) (ch>='a'&&ch<='z')
#define isupper(ch) (ch>='A'&&ch<='Z')
#define isalpha(ch) (islower(ch)||isupper(ch))
template<class T>
void wrint(T x){
    if(x<0){
        x=-x;
        pc('-');
    }
    if(x>=10){
        wrint(x\/10);
    }
    pc(x%10^48);
}
template<class T>
void wrintln(T x){
    wrint(x);
    pln
}
template<class T>
void read(T& x){
    x=0;
    int f=1;
    char ch=gc;
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=gc;
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=gc;
    }
    x*=f;
}
typedef __int128 sll;
const int maxn=2005;
int n,lim;
sll a[maxn];
vi gp[maxn];
sll f[maxn][maxn][2];
\/\/ u\/u exist\/u.optimes : minimul xor sum
int siz[maxn];
void dfs(int u,int _fa){
    siz[u]=1;
    for(int& v:gp[u]){
        if(v==_fa)continue;
        dfs(v,u);
        siz[u]+=siz[v];
    }
    sll g[2][maxn];
    {
        FOR(b,0,1){
            FOR(i,0,n)g[b][i]=1e30;
        }
        \/\/ u 存在
        g[0][0]=0;
        bool cur=0;
        int sz=0;
        for(int& v:gp[u]){
            if(v==_fa)continue;
            FOR(i,0,sz){
                FOR(j,0,siz[v]){
                    \/\/ v 存在
                    ckmn(g[cur^1][i+j],g[cur][i]+f[v][j][1]+(a[u]^a[v]));
                    \/\/ v 不存在
                    ckmn(g[cur^1][i+j],g[cur][i]+f[v][j][0]);
                }
            }
            FOR(i,0,sz)g[cur][i]=1e30;
            sz+=siz[v];
            cur^=1;
        }
        FOR(i,0,siz[u]){
            f[u][i][1]=g[cur][i];
        }
    }
    {
        FOR(b,0,1){
            FOR(i,0,n)g[b][i]=1e30;
        }
        \/\/ u 不存在
        g[0][1]=0;
        bool cur=0;
        int sz=1;
        for(int& v:gp[u]){
            if(v==_fa)continue;
            FOR(i,0,sz){
                FOR(j,0,siz[v]){
                    \/\/ v 存在
                    ckmn(g[cur^1][i+j],g[cur][i]+f[v][j][1]);
                    \/\/ v 不存在
                    ckmn(g[cur^1][i+j],g[cur][i]+f[v][j][0]);
                }
            }
            FOR(i,0,sz)g[cur][i]=1e30;
            sz+=siz[v];
            cur^=1;
        }
        FOR(i,1,siz[u]){
            f[u][i][0]=g[cur][i];
        }
    }
}
void solve(int id_of_test){
	read(n);
    read(lim);
    FOR(i,1,n){
        read(a[i]);
    }
    FOR(i,1,n-1){
        int u,v;
        read(u);
        read(v);
        gp[u].eb(v);
        gp[v].eb(u);
    }
    FOR(i,0,n){
        FOR(j,0,n){
            f[i][j][0]=f[i][j][1]=1e30;
        }
    }
    dfs(1,0);
    FOR(k,0,lim){
        sll ans=min(f[1][k][0],f[1][k][1]);
        wrint(ans);
        pc(' ');
    }
    pln
}
int main()
{
	int T;
	T=1;
	FOR(_,1,T){
		solve(_);
	}
	return 0;
}

验题人 @LastKismet 的代码：

#include<bits\/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
template<typename T> using vec=vector<T>;
template<typename T> using grheap=priority_queue<T>;
template<typename T> using lrheap=priority_queue<T,vector<T>,greater<T>>;
#define fir first
#define sec second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define rep(i,x,y) for(int i=(x);i<=(y);i++)
#define per(i,x,y) for(int i=(x);i>=(y);i--)
#define repl(i,x,y) for(int i=(x);i<(y);i++)
#define file(f) freopen(#f".in","r",stdin);freopen(#f".out","w",stdout);

struct mint {
	int x,mod;
	inline mint(int o=0,int p=998244353) {x=o;mod=p;}
	inline mint & operator=(ll o){return x=o%mod,(x+=mod)>=mod&&(x-=mod),*this;}
	inline mint & operator+=(mint o){return (x+=o.x)>=mod&&(x-=mod),*this;}
	inline mint & operator-=(mint o){return (x-=o.x)<0&&(x+=mod),*this;}
	inline mint & operator*=(mint o){return x=(ll)x*o.x%mod,*this;}
	inline mint & operator^=(ll b){mint res(1);for(;b;b>>=1,*this*=*this)if(b&1)res*=*this;return x=res.x,*this;}
	inline mint & operator^=(mint o){return *this^=o.x;}
	inline mint & operator\/=(mint o){return *this*=(o^=(mod-2));}
	inline mint & operator++(){return *this+=1;}
	inline mint & operator--(){return *this-=1;}
	inline mint operator++(int o){mint res=*this;return *this+=1,res;}
	inline mint operator--(int o){mint res=*this;return *this-=1,res;}
	friend inline mint operator+(mint a,mint b){return a+=b;}
	friend inline mint operator-(mint a,mint b){return a-=b;}
	friend inline mint operator*(mint a,mint b){return a*=b;}
	friend inline mint operator\/(mint a,mint b){return a\/=b;}
	friend inline mint operator^(mint a,ll b){return a^=b;}
	friend inline mint operator^(mint a,mint b){return a^=b;}
	friend inline bool operator<(mint a,mint b){return a.x<b.x;}
	friend inline bool operator>(mint a,mint b){return a.x>b.x;}
	friend inline bool operator<=(mint a,mint b){return a.x<=b.x;}
	friend inline bool operator>=(mint a,mint b){return a.x>=b.x;}
	friend inline bool operator==(mint a,mint b){return a.x==b.x;}
	friend inline istream & operator>>(istream &in,mint &o){ll x;return in>>x,o=x,in;}
	friend inline ostream & operator<<(ostream &ot,mint o){return ot<<o.x,ot;}
};

const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;

const int N=2005;

int n,lim;
i128 a[N];
vec<int> g[N];

int siz[N];
i128 f[N][N][2];

void dfs(int now,int fid){
	siz[now]=1;
	f[now][0][0]=f[now][1][1]=0;
	for(auto nxt:g[now]){
		if(nxt==fid)continue;
		dfs(nxt,now);
		per(i,siz[now],0)per(j,siz[nxt],0){
			if(j)chmin(f[now][i+j][0],f[now][i][0]+min(f[nxt][j][1],f[nxt][j][0]+(a[now]^a[nxt])));
else f[now][i+j][0]=f[now][i][0]+min(f[nxt][j][1],f[nxt][j][0]+(a[now]^a[nxt]));
			if(i)if(j)chmin(f[now][i+j][1],f[now][i][1]+min(f[nxt][j][0],f[nxt][j][1]));
            else f[now][i+j][1]=f[now][i][1]+min(f[nxt][j][0],f[nxt][j][1]);
		}
		siz[now]+=siz[nxt];
	}
}

void print(i128 x){
	if(x\/10)print(x\/10);
	cout<<char(x%10+'0');
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>lim;
	memset(f,0x3f,sizeof(f));
	rep(i,1,n){
		ll x;cin>>x;
		a[i]=x;
	}
	repl(i,1,n){
		int u,v;cin>>u>>v;
		g[u].pub(v);g[v].pub(u);
	}
	dfs(1,0);
	rep(i,0,lim)print(min(f[1][i][0],f[1][i][1])),cout<<' ';
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-06-05 15:08:26

我不理解为什么题解区所有做法都需要枚举 $[-1000,1000]$。

我实际测试，$[0,1000]$ 就足够了。

这篇题解将主要说明为什么 $[0,1000]$ 足够。

做法

首先，令 $b_i = a_i -n$，那么题目显然可以转化为，选择 $k \gt 0$ 个下标 $p_1,p_2,\cdots,p_k$，使得 $\sum\limits_{i=1}^k b_{p_i} = 0$。

令 $dis_i$ 表示总和为 $i$ 需要选择的最少下标数量，那么，可以通过 bfs 来进行转移。

但是，可能的总和范围在 $[-10^6,10^6]$ 之间，也就是说有 $2\times 10^6$ 个编号在 $[-10^6,10^6]$ 的点。

而每个点最多有 $10^3$ 个连接的点，肯定爆炸了。

但是，事实上，只有编号 $[0,10^3]$ 的点才是有效的，接下来证明为什么。

首先，枚举的总和范围在 $[0,10^6]$。

证明：已知最后总和为 $0$，所以，负数的绝对值总和是等于正数的绝对值总和的，重新排列累加顺序，先累加所有正数，再累加所有负数，就可以保证过程的总和非负。

接着，上界可以降低到 $10^3$。

证明：如果有某一步，总和超过了 $10^3$，但是已知的是最终总值小于等于 $10^3$，所以，必然存在一种方案，将当前的数和后面步骤某个数交换，使得当前这一步的绝对值小于等于 $10^3$。

#include <bits\/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
#define FORK(i,a,b,k) for(auto i=(a);i<=(b);i+=(k))
#define REPK(i,a,b,k) for(auto i=(a);i>=(b);i-=(k))
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a\/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
#define islower(ch) (ch>='a'&&ch<='z')
#define isupper(ch) (ch>='A'&&ch<='Z')
#define isalpha(ch) (islower(ch)||isupper(ch))
template<class T>
void wrint(T x){
    if(x<0){
        x=-x;
        pc('-');
    }
    if(x>=10){
        wrint(x\/10);
    }
    pc(x%10^48);
}
template<class T>
void wrintln(T x){
    wrint(x);
    pln
}
template<class T>
void read(T& x){
    x=0;
    int f=1;
    char ch=gc;
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=gc;
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=gc;
    }
    x*=f;
}
const int maxn=1005;
int n,k;
bitset<maxn> ok;
int dis[maxn];
void bfs(){
    memset(dis,0x3f,sizeof dis);
    int inf=dis[0];
    queue<int> q;
    FOR(i,n,1000){
        if(ok[i])dis[i-n]=1,q.push(i-n);
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        FOR(i,0,1000){
            if(ok[i]){
                int to=u+i-n;
                if(to>=0&&to<=1000){
                    if(dis[to]>dis[u]+1){
                        dis[to]=dis[u]+1;
                        q.push(to);
                    }
                }
            }
        }
    }
    if(dis[0]==inf)puts("-1");
    else printf("%d\n",dis[0]);
}
void solve(int id_of_test){
	read(n);
    read(k);
    FOR(i,1,k){
        int a;
        read(a);
        ok[a]=1;
    }
    bfs();
}
int main()
{
	int T;
	T=1;
	FOR(_,1,T){
		solve(_);
	}
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-06-16 14:07:01

前置

两个月前参加了特招考试。

难度还行，共 6 题 + 80 分钟，红黄黄绿蓝紫，切了前 5 个。

然后获得了 A+ 评级，不再需要担心中考。

Day -1

上午写出了一道 hba 布置的大模拟。

晚上 6:00 开始简单复习了一下语文，物理。

Day 1

考点在 WFYZ。

居然连透明垫板都不能带进考场，看起来很严。

进门的地方成堆的被门卫扔掉的东西，都是不能带的。

进校门之后，还没到进考场时间，得等大约 0.5h。

值得一提的是，我听见一群女生在议论屈原，我不知道 @wflhx2011（通常在机房内称之为屈原）对此的感想是什么。

操场上很热闹的。

到处乱逛，然后就到了进考场时间。

语文卷子发下来，先翻到后面，发现是一大一小两篇作文，150 + 600。

感觉中规中矩的，就按顺序答题。

根据感觉答题，没啥好说的。

写到大小作文的时候，只剩下 40min 了，不过，如果只关心能写够字数 + 语句通顺的话，还是很容易的，最后 10min 检查了一下准考证号没涂错就交了。

没有条形码，差评！

中午回去简单的准备了物理，但是我还是更想睡觉。

下午第一节，考物理，喜提没做完！

然后，出去等了 1h，考政治。

中间这段时间，只能是睡觉。

政治的话，选择题凭感觉，大题就抄材料。

晚上回去，打算复习数学。

我拿出 2024 年的数学中考题做了一遍，感觉良好，没有不会的题。

Day2

嗯，数学翻车了。

很多公式都忘了（比如说，圆锥的侧展开面积，还有更丢人的，一元二次方程的顶点式，我忘了除以 2a 还是 4a，另外就是一些几何结论），得现场推。

然后，就是遗憾的超时。

下午先考的化学。

我至少还记得元素符号对应的名称。

然后，就感觉，虽然是可以推算的，但是很吃力。

然后，也超时了，但不多。

历史，同政治，抄材料。

晚上回去打了场 ABC，F 题一开始（比赛进行到 39:00）就想到了正确做法，然后复杂度分析错了，最后意识到的时候，来不及了。

赛后看 G 题，发现一个不久前做过的 trick 刚好能秒，写完 AC，感觉有些遗憾。

Day3

考英语。

文章基本都能看懂，自认为是考得最好的科目，至于填空和作文有没有语法错误，我也不知道。

最后

九年义务教育结束了，现在还能想起来第一次报名小学的那个雨天，以及广场上的人群。

接下来，对我最重要的考试，就是 11 月的正式 NOIP 了，将会决定我是否能继续下去。