20231014 B 组模拟赛 题解
前言
这场没啥可说的，感觉策略没问题，纯粹实力问题。
但是有一说一这套题难度梯度有点大啊。
T1
场上唯一做出来的题。
容易发现他就是要求你 $T_1$ 中没有横叉边，$T_2$ 中没有前向边/返祖边。
其实很简单，容易发现 $T_1$ 是 dfs 树，因为无向图的 dfs 树上显然没有横叉边。$T_2$ 是 bfs 树，因为 bfs 树上显然没有前向边，由于是无向图那么他显然同时也没有返祖边。
复杂度 $O(n)$。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=2e5+5,inf=0x3f3f3f3f;
int n,m,vis[N];
vector<int> e[N];
void dfs(int x){
vis[x]=1;
for(auto i:e[x]){
if(vis[i]) continue;
printf("%d %d\n",x,i);
dfs(i);
}
}
void bfs(){
queue<int> q;
mem(vis,0);
q.push(1);vis[1]=1;
while(q.size()){
int u=q.front();q.pop();
for(auto i:e[u]){
if(vis[i]) continue;
vis[i]=1;
printf("%d %d\n",u,i);
q.push(i);
}
}
}
signed main(){
n=read();m=read();
forup(i,1,m){
int u=read(),v=read();
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1);
bfs();
}
T2
首先，我们令一个数 $p_i$ 的“权值”为 $\sum_{j=1}^{i-1}[p_j>p_i]$。
由于交换的次数最小，那么对于每次交换 $p_i,p_{i+1}$，显然有 $p_i>p_{i+1}$。那么容易发现这对于 $p_i$ 的权值是没有影响的，我们可以视作这样一个交换为对 $p_{i+1}$ 进行了一次操作，使 $p_{i+1}$ 的权值减去 $1$。
那么容易发现，只有在最终序列中权值恰好为 $k$ 的数是有可能被操作过的，因为如果加入进行了一系列操作后把一个大于 $k$ 的权值变成了等于 $k$ 的，那么你显然不会考虑把它变得更小，因为把它变小并不会影响其他位置的权值。
那么只需要考虑这些权值为 $k$ 的位置初始权值有多少种可能就可以了…
吗？
其实并不是，容易发现假如其他数相对位置不动，一个数 $x$ 在多个位置可能具有相同的权值，而排列更关注的其实是数的位置。
比如在排列 5,2,4,1,3、5,2,1,4,3、5,2,1,3,4 中 $4$ 都具有相同的权值。
那么我们需要考虑的就是每个数的初始位置有多少种可能。
容易发现，若最终排列中 $p_i$ 后面存在一个 $p_j<p_i$ 就不太好构造。
但是跳出思维的误区，由于 $p_i$ 的权值恰好是 $k$，若后面有一个 $p_j<p_i$，那么 $p_j$ 的权值必然大于 $k$，说明 $p_i$ 后面必定全都严格大于 $p_i$，也就是说 $p_i$ 在后面的所有位置都必然有不同的权值！
那么我们又只需要求初始权值的可能性了。
而显然，由于我们每个操作只影响一个权值，假如我们要倒回去构造，那么我们可以一个一个放到想要的权值的位置，也就是说如果只求方案数可以直接乘起来。
然后最终序列上的权值可以树状数组维护，复杂度 $O(n\log n)$。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=5005,mod=998244353;
int n,k,ans=1;
struct BIT{
int c[N];
void upd(int x,int k){for(;x<=n;x+=x&-x)c[x]+=k;}
int sum(int x){int res=0;for(;x>0;x-=x&-x)res+=c[x];return res;}
}mt;
signed main(){
n=read();k=read();
forup(i,1,n){
int a=read();
if(i-1-mt.sum(a)==k) ans=1ll*ans*(n-i+1)%mod;
mt.upd(a,1);
}
printf("%d",ans);
}
T3
很有意思的一道题。
首先考虑如果给你一些点，问包含这些所有点的连通块最小是多少应该怎么求。
这个可以直接虚树秒掉，考虑把这些点拎出来建虚树，容易发现虚树上所有点和边都是必要的，那么虚树的点数就是最小连通块大小。
而我们刚刚说的那个东西其实有更快速的求法，由于一棵树的点数等于边数 $+1$，那么考虑求边数，容易发现按 dfs 序排序后虚树上边数刚好是相邻两项的距离（加上首尾两个）之和的二分之一，证明类似建虚树的方法。
那么容易想到用莫队维护区间内点按 dfs 序排序的序列（这个可以用 set），复杂度是 $O(n\sqrt{n}\log n)$，不太能过（听说写压位 Trie 能过）。
容易发现在序列上删点是可以 $O(1)$ 的，但是加点不行。那么可以用只删的回滚莫队维护双向链表，复杂度 $O(n\sqrt{n})$。
另外由于是只删的回滚莫队，左右端点在同一块的情况其实不需要特判。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1e5+5,inf=0x3f3f3f3f;
int n,m,q,c[N],TT,ans[N];
vector<int> e[N];
struct query{
int blg,l,r,pos;
}s[N];
int dfn[N],mp[N],Tm,dpt[N];
int ST[20][N],lg[N],ff[N];
void dfs(int x,int fa){
dfn[x]=++Tm;
mp[Tm]=x;
dpt[x]=dpt[fa]+1;ff[x]=fa;
ST[0][Tm]=x;
for(auto i:e[x]){
if(i==fa) continue;
dfs(i,x);
}
}
void initst(){
forup(i,1,19){
forup(j,1,(n-(1<<i)+1)){
if(dpt[ST[i-1][j]]<=dpt[ST[i-1][j+(1<<(i-1))]]){
ST[i][j]=ST[i-1][j];
}else{
ST[i][j]=ST[i-1][j+(1<<(i-1))];
}
}
}
lg[1]=0;
forup(i,2,n){
lg[i]=lg[i>>1]+1;
}
}
int lca(int l,int r){
if(l==r) return l;
l=dfn[l];r=dfn[r];
if(l>r) swap(l,r);
++l;
int len=lg[r-l+1],r1=ST[len][l],r2=ST[len][r-(1<<len)+1];
if(dpt[r1]<dpt[r2]){
return ff[r1];
}else{
return ff[r2];
}
}
int dist(int u,int v){
return dpt[u]+dpt[v]-2*dpt[lca(u,v)];
}
int cnt[N],lst;
int res,pre[N],nxt[N];
int L,R;
void del(int x){
cnt[x]--;
if(!cnt[x]){
res-=(dist(x,pre[x])+dist(x,nxt[x]));
pre[nxt[x]]=pre[x];
nxt[pre[x]]=nxt[x];
res+=dist(pre[x],nxt[x]);
}
}
struct Node{
int x,pre,nxt;
};
signed main(){
n=read();m=read();q=read();
TT=sqrt(m);
forup(i,1,n-1){
int u=read(),v=read();
e[u].push_back(v);
e[v].push_back(u);
}
forup(i,1,m){
c[i]=read();
}
forup(i,1,q){
s[i].l=read();s[i].r=read();s[i].pos=i;
s[i].blg=s[i].l/TT;
}
dfs(1,0);
initst();
sort(s+1,s+q+1,[&](query a,query b){
if(a.blg==b.blg){
return a.r>b.r;
}else{
return a.blg<b.blg;
}
});
forup(i,1,q){
if(i==1||s[i].blg!=s[i-1].blg){
lst=0;res=0;
mem(pre,0);mem(nxt,0);
mem(cnt,0);
L=s[i].blg*TT;R=s[i].r;
forup(j,L,R) cnt[c[j]]++;
fordown(j,n,1){
if(cnt[mp[j]]){
lst=mp[j];
break;
}
}
forup(j,1,n){
if(cnt[mp[j]]){
pre[mp[j]]=lst;
res+=dist(mp[j],lst);
nxt[lst]=mp[j];
lst=mp[j];
}
}
}
stack<Node> stk;
int LL=L;
while(R>s[i].r){
del(c[R--]);
}
while(L<s[i].l){
stk.push(Node{c[L],pre[c[L]],nxt[c[L]]});
del(c[L++]);
}
ans[s[i].pos]=res/2+1;
L=LL;
while(stk.size()){
int u=stk.top().x,pr=stk.top().pre,nx=stk.top().nxt;
stk.pop();
++cnt[u];
if(cnt[u]==1){
pre[u]=pr;nxt[pr]=u;
nxt[u]=nx;pre[nx]=u;
res+=dist(u,pr)+dist(u,nx);
res-=dist(pr,nx);
}
}
}
forup(i,1,q){
printf("%d\n",ans[i]);
}
}
T4
现在迎面向我们走来的是蒸批出的 T4（指题目背景）。
由于题目非常贴心的让你把答案乘以 $M^K$，那么其实就是要求有多少个整数序列 $a$，满足 $\forall i\in[1,K],a_i\in[0,M-1],\prod_{i+1}^Ka_i\equiv N\pmod M$。
- 首先考虑若 $M$ 是质数应该怎么做。
根据简化剩余系的知识，我们可以知道，当 $M$ 是质数时，若 $a\ne 0$，那么必然存在一个 $r$ 使得 $a\times r\equiv b\pmod M$，且对于不同的 $b$，$r$ 的取值必定不相同。
也就是说，特判掉 $n=0$ 的情况后，只要前 $k-1$ 项的乘积不同余 $0$，那么必然存在一个唯一确定的第 $k$ 项能把 $n$ 构造出来，也就是说乘积为 $n$ 的序列数就是 $(M-1)^{k-1}$。
关于 $n=0$ 的情况，简单容斥即可，大概就是总序列数减去不为 $0$ 的序列数。
- 然后考虑 $M=p^e$ 的情况，其中 $p$ 是一个质数。
此时，容易发现 $n$ 必然能拆成 $d\times p^r$，其中 $\gcd(d,p)=1$，另外由于 $n<m$，必然有 $r<e$，证明考虑分解质因数。
那么显然 $d$ 在 $M$ 的简化剩余系内，可以套用之前的算法，然后考虑这 $r$ 个 $p$ 分给 $k$ 个位置的方案数，由于 $r<e$，那么就是 $r$ 个小球放进 $k$ 个盒子，可以有空盒的方案数，这个很典，答案是 $\binom{r+k-1}{k-1}$。
对于 $n=0$ 的情况，容斥变得稍微复杂了一点，但还是挺简单的，就是总序列数减去恰好有零个 $p$ 的序列数再减去恰好有一个 $p$ 的序列数再减恰好去有两个 $p$ 的序列数……减去恰好有 $e-1$ 个 $p$ 的序列数。
- 最后考虑一般情况
根据唯一分解定理，$M=\prod p_i^{e_i}$，容易想到对于每个 $p_i^{e_i}$ 求出答案后通过某种方法得出最终答案。为方便叙述，设 $f(n,m,k)$ 表示 $N=n,M=m,K=k$ 时的答案。那么其实，$f(N,M,K)=\prod f(N\bmod p_i^{e_i},p_i^{e_i},K)$，证明如下：
容易发现若每个 $f(N,M,K)$ 的答案与 $f(N\bmod p_i^{e_i},p_i^{e_i},K)$ 的答案组一一对应，那么上式正立。
先证明一个 $f(N,M,K)$ 能对应一组 $f(N\bmod p_i^{e_i},p_i^{e_i},K)$ 的答案，考虑一个答案的形式，即 $\prod_{j=1}^K A_j\equiv N\pmod M$，那么对于每个小情况 $i$，就是 $\prod_{j=1}^K a_{i,j}\equiv n_i\pmod{m_i}$，容易发现可以取 $a_{i,j}=A_{j}\bmod m_i,n_{i}=N\bmod m_i$，显然能对应。
然后考虑证明一组 $f(N\bmod p_i^{e_i},p_i^{e_i},K)$ 的答案能对应 $f(N,M,K)$ 的答案。其实也很简单，考虑他是数个 $a_{i,j}\equiv n_i\pmod{m_i}$ 的形式，这其实就是 CRT 的形式，由于 $p_i^{e_i}$ 显然两两互质（证明考虑唯一分解定理），那么对于一组 $a_j$，显然 $A_j$ 是唯一的。
故 $f(N,M,K)$ 的答案与 $f(N\bmod p_i^{e_i},p_i^{e_i},K)$ 的答案形成了双射，可以用乘法原理直接乘起来。
然后就做完了……
吗？
如果你真的认真想过，会发现情况 $2$ 中 $\binom{r+k-1}{k-1}$ 这个组合数算不了，因为 $k$ 是 $10^9$ 级别的，但是 $r$ 是 $\log M$ 级别的，那么上面的组合数其实等于 $\binom{r+k-1}{r}$，可以预处理一些逆元后暴力下降幂。
复杂度 $O(\log K+\log M)$（快速幂和暴力下降幂）。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(i64 i=(s);i<=(e);i++)
#define fordown(i,s,e) for(i64 i=(s);i>=(e);i--)
using namespace std;
using i64=long long;
#define gc getchar()
inline i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 mod=998244353;
i64 k,n,m,ans=1;
i64 ksm(i64 a,i64 b){
i64 c=1;a%=mod;
while(b!=0){
if((b&1ll)!=0) c=a*c%mod;
a=a*a%mod;
b>>=1;
}
return c;
}
i64 inv[105];
i64 C(i64 m,i64 n){
if(n>m) return 0;
i64 res=1;
forup(i,1,n){
res=res*(m+1-i)%mod*inv[i]%mod;
}
return res;
}
i64 f(i64 k,i64 n,i64 m,i64 p,i64 e){
if(n!=0){
i64 nn=n,x=0;
while(nn%p==0){
nn/=p;++x;
}
return C(x+k-1,x)*ksm(m-m/p,k-1)%mod;
}else{
i64 res=ksm(m,k);
forup(i,0,e-1){
res=(res+mod-(ksm(p,e-i)+mod-ksm(p,e-i-1))%mod*C(i+k-1,i)%mod*ksm(m-m/p,k-1)%mod)%mod;
}
return res;
}
}
signed main(){
k=read();n=read();m=read();
inv[1]=1;
forup(i,2,100) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
for(i64 i=2;i*i<=m;++i){
if(m%i!=0) continue;
i64 e=0,p=1;
while(m%i==0){
++e;m/=i;
p=p*i;
}
ans=ans*f(k,n%p,p,i,e)%mod;
}
if(m>1){
ans=ans*f(k,n%m,m,m,1)%mod;
}
printf("%lld\n",ans);
}