2023.9.5 Online test
A
有一个长 \(n+1\) 的数组 \(a\),长 \(n\) 的数组 \(b\)，
每次询问删除 \(a\) 中某个位置，求剩下的数跟 \(b\) 组成一种匹配 \(p\)，使得 \(\max(a[i]-b[p[i]])\) 最小。
显然有一个贪心，就是排序后位置相同的匹配。
把 \(a,b\) 排序，求出 \(a\) 的前后缀匹配 \(b\) 的值，这样就可以处理删除某个数的贡献了。
code
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+10;
int n;
int b[N],c[N],ans1[N],ans2[N],ret[N];
struct node {
int x,id;
} a[N];
bool cmp(node u,node v) {
return u.x<v.x;
}
int main() {
freopen("tie.in","r",stdin);
freopen("tie.out","w",stdout);
ios::sync_with_stdio(0);
cin>>n;
for(int i=1; i<=n+1; i++) cin>>a[i].x,a[i].id=i;
sort(a+1,a+1+n+1,cmp);
for(int i=1; i<=n; i++) cin>>b[i];
sort(b+1,b+1+n);
for(int i=1; i<=n+1; i++) {
ans1[i]=max(ans1[i-1],a[i].x-b[i]);
}
for(int i=n+1; i>=1; i--) {
ans2[i]=max(ans2[i+1],a[i].x-b[i-1]);
}
for(int i=1; i<=n+1; i++) {
ret[a[i].id]=max(ans1[i-1],ans2[i+1]);
}
for(int i=1; i<=n+1; i++) printf("%d ",ret[i]);
return 0;
}
B
给定 \(n\) 根木棍，要从中选出 \(6\) 根木棍，满足这 \(6\) 根木棍拼出一个正方形，注意木棍不能弯折。
问方案数（选出木棍相同但正方形不同算一种）。
只有两种方式凑成长方形，一种是 \(a=b=c+d=e+f\)，另一种是 \(a=b=c=d+e+f\)。
先处理第一种：\(a=b=c+d=e+f\)，
防止算重，考虑钦定 \(c\le e\le f\le d\).
我们从小到大先枚举一个 \(d\)，再枚举一个 \(c\)，那么 \(a=b=c+d\) 已知。
在枚举 \(d\) 的时候，再处理出一个 \(cnt2_i\) 数组，表示两个数和为 \(i\) 的方案数。每次把 \(d\) 的贡献加进去即可。
考虑若 \(c>d\)，贡献是 \(C(cnt_{c+d},2)\cdot (cnt_c\cdot cnt_d\cdot cnt2_{c+d}+C(cnt_c,2)\cdot C(cnt_d,2))\)，
由于 \(cnt_2\) 中已有的贡献都是 \(e\le d\) 的 \(e\) 贡献的，所以一定不会算重。
若 \(c=d\) 呢？贡献是 \(C(cnt_{c+d},2)\cdot (C(cnt_c,2)\cdot cnt2_{c+d}+C(cnt_c,4))\)。
第二种：\(a=b=c=d+e+f\)，钦定 \(d\le e\le f\).
从大到小枚举 \(d\)，再次处理出 \(cnt2_i\) 数组。
再枚举一个 \(a\)，贡献是 \(C(cnt_a,3)\cdot cnt_d\cdot cnt2_{a-d}\).
考虑 \(d=e\)，那么如果 \(a-2d>d\) 的话，那么贡献是 \(C(cnt_a,3)\cdot C(cnt_a,2)\cdot cnt_{a-2d}\).
我们其实还没有结束，我们漏了 \(d=e=f\) 的情况，最后贡献加上 \(C(cnt_{a/3},3)\) 即可。
code
#include<bits/stdc++.h>
using namespace std;
const int N=5010,M=1e7+10;
typedef long long LL;
int n,a[N];
LL cnt[M],cnt2[M],C[N][5],Ans,ret;
vector<int> vec;
int main() {
freopen("yist.in","r",stdin);
freopen("yist.out","w",stdout);
scanf("%d",&n);
for(int i=1; i<=n; i++) {
scanf("%d",&a[i]);
if(!cnt[a[i]]) vec.push_back(a[i]);
cnt[a[i]]++;
}
C[0][0]=1;
for(int i=1; i<=n; i++) {
C[i][0]=1;
for(int j=1; j<=4; j++) C[i][j]=C[i-1][j]+C[i-1][j-1];
}
sort(vec.begin(),vec.end());
for(int v:vec) {
for(int w:vec) {
if(v+w>=M) continue;
LL tmp=C[cnt[v+w]][2];
if(w>v) {
Ans=Ans+tmp*cnt[v]*cnt[w]*cnt2[v+w];
Ans=Ans+tmp*C[cnt[v]][2]*C[cnt[w]][2];
cnt2[v+w]+=cnt[v]*cnt[w];
}
if(w==v) {
Ans=Ans+tmp*C[cnt[w]][2]*cnt2[2*w];
Ans=Ans+tmp*C[cnt[w]][4];
cnt2[2*w]+=C[cnt[w]][2];
}
}
}
memset(cnt2,0,sizeof cnt2);
reverse(vec.begin(),vec.end());
for(int w:vec) {
for(int v:vec) {
LL tmp=C[cnt[v]][3];
if(v>w) {
Ans=Ans+tmp*cnt[w]*cnt2[v-w];
if(v-w-w>w) Ans=Ans+tmp*C[cnt[w]][2]*cnt[v-w-w];
}
}
for(int y:vec) {
if(w+y>=M) continue;
if(w<y)
cnt2[w+y]+=cnt[w]*cnt[y];
if(w==y)
cnt2[2*w]+=C[cnt[w]][2];
}
}
for(int v:vec) {
LL tmp=C[cnt[v]][3];
if(v%3==0) Ans=Ans+tmp*C[cnt[v/3]][3];
}
printf("%lld\n",Ans);
return 0;
}
C
定义 \(k\) 子树为节点子树内距离不超过 \(k\) 的部分。如果一个子树不存在距离为 \(k\) 的部分，那么其不存在 \(k\) 子树。
你需要找到最大的 \(k\)，满足存在两个节点的 \(k\) 子树是同构的。注意儿子顺序也是要考虑的。
树哈希处理同构。
显然答案可二分。我们如果用倍增代替二分呢？
我们处理 \(h[i][u]\)，表示 \(u\) 的 \(2^i\) 子树的哈希值。
我们现在想合并 \(h[i],h[j]\)，使其成为 \(h[i+j]\)。
设 \(p(u,k)\) 表示 \(u\) 的 \(k\) 级儿子集合。那么 \(h[i+j][u]\) 分为两部分，\(h[i][u]\) 以及 \(h[j][v]\space (v\in p(u,i))\).
我们递归一次树，对于 \(v\)，就向其 \(i\) 级祖先做贡献。合并是 \(O(n)\) 的。
我们可以先处理出所有的 \(h[2^i]\)，然后倍增判断即可。
code
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=1e5+10;
int n,mx,ans,len,now;
const ull bas=7988993;
ull hs[20][N],f[N],nf[N],pv[N];
vector<int> e[N];
int dep[N],p[N],st[N],mxd[N],vis[N];
void dfs(int x,ull *a,ull *b,ull *c) {
if(x==1) p[0]=st[0]=0,dep[1]=1;
st[dep[x]]=x;
mxd[x]=dep[x];
a[x]=b[x];
if(dep[x]>len)
a[st[dep[x]-len]]=a[st[dep[x]-len]]*bas+c[x];
for(int y:e[x]) {
dep[y]=dep[x]+1;
dfs(y,a,b,c);
mxd[x]=max(mxd[x],mxd[y]);
}
st[0]--;
}
bool cmp(int a,int b) {
return pv[a]<pv[b];
}
void merge(ull *a,ull *b,ull *c,int k) {
len=k;
dfs(1,a,b,c);
for(int i=1; i<=n; i++) p[i]=i,pv[i]=a[i];
sort(p+1,p+n+1,cmp);
for(int i=1,j=0; i<=n; i++) {
if(pv[p[i]]>pv[p[i-1]]) j++;
a[p[i]]=j;
}
}
int check(ull *a,ull *b,ull *c,int k) {
merge(a,b,c,ans);
now++;
for(int i=1; i<=n; i++) {
if(mxd[i]-dep[i]>=k) {
if(vis[a[i]]==now) return 1;
vis[a[i]]=now;
}
}
return 0;
}
int main() {
freopen("ernd.in","r",stdin);
freopen("ernd.out","w",stdout);
scanf("%d",&n);
for(int i=1; i<=n; i++) {
int s,x;
scanf("%d",&s),hs[0][i]=s;
for(int j=1; j<=s; j++) {
scanf("%d",&x); e[i].push_back(x);
}
}
for(int i=1; i<=16; i++)
merge(hs[i],hs[i-1],hs[i-1],1<<(i-1));
for(int i=16; i>=0; i--) {
if(check(nf,f,hs[i],ans+(1<<i))) {
ans+=(1<<i);
memcpy(f,nf,sizeof(nf));
}
}
printf("%d\n",ans);
return 0;
}
D
定义一个数列的权值为它本质不同的子序列个数，
给出一个长度为 \(n(n\le 30000)\) 的数列 \(A\) 和一个整数 \(K(K\le 5)\)，保证 \(Ai ∈ [0, K)\)。\(m(m\le 30000)\) 次操作：
- 给出 \(l, r, x\)，对所有的 \(i ∈ [l, r]\)，将 \(A_i\) 变成 \((A_i + x) \bmod K\)。
- 给出 \(l, r, x\)，对所有的 \(i ∈ [l, r]\)，将 \(A_i\) 变成 \(A_i \times x \bmod K\)。
- 给出 \(l, r\)，询问区间 \([l, r]\) 的权值对 \(998244353\) 取模后的值。
本质不同的子序列个数，我们考虑用最小表示法，即我们把一个子序列第一次出现的位置做贡献。
设 \(f_{i,j}\) 表示 \(i\) 结尾的，结尾是 \(j\) 的子序列个数。
那么 \(f_{i,j}\) 可以被 \(f_{pre[x],x}\) 做贡献，其中 \(pre[x]\) 是 \(x\) 上一次出现的位置。
这种子序列的题一般是动态 dp，状态是一行所有的 \(f_{pre[x],x}\)，我们直接把转移写成矩阵，显然是单位矩阵再把第 \(a_i\) 行设为 \(1\)。
直接把矩阵上线段树即可。
在给区间加上一个数时，区间中任意两个数的相等关系并不会变，因此只需要给矩阵的行列置换一下就好了，内容本质上并没有变化。
在给区间乘上一个数 \(x\) 时，如果 \(\gcd(x,K)=1\)，相等关系同样不会变化，处理方法和区间加一样。对于其他情况，区间中的数以模 \(K/\gcd(K,x)\) 的余数划分成了 \(K/\gcd(K,x)\) 个等价类，这样就不能直接用原有的值更新了。处理方法是我们对 \(K\) 的所有约数 \(d\)，都用一棵线段树维护模 \(d\) 时的答案，在区间乘法时相当于用模 \(K/\gcd(K,x)\) 的信息去更新模 \(d\) 的信息。
code
#include<bits/stdc++.h>
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
typedef long long LL;
inline int read(){
char ch=getchar();
while(!isdigit(ch) && ch!='-') ch=getchar();
int x=0,ff=1; if(ch=='-') ff=-1,ch=getchar();
while(isdigit(ch)) x=(x<<3) + (x<<1) + (ch^48),ch=getchar();
return x*ff;
}
const int N=3e4+5,P=998244353;
int n,K,Q,a[N],l[4],m;
inline int gcd(int x,int y){
if(!y) return x;
else return gcd(y,x%y);
}
struct matrix{
int mx[6][6],c;
void set(int nc,int op){
c=nc;
for(int i=0;i<=c;i++)
for(int j=0;j<=c;j++)
mx[i][j]=0;
if(op){
for(int i=0;i<=c;i++)
mx[i][i]=1;
}
}
matrix operator * (const matrix A) const {
matrix B; B.set(A.c,0);
for(int i=0;i<=c;i++)
for(int j=0;j<=c;j++)
for(int k=0;k<=c;k++)
(B.mx[i][k]+=1ll*mx[i][j]*A.mx[j][k]%P)%=P;
return B;
}
} bf;
struct node{
int adt,mlt;
matrix b[3];
void addt(int x,int op){
if(!op){
(adt+=x)%=K;
for(int k=1;k<=m;k++){
bf.c=l[k];
for(int i=0;i<=l[k];i++)
for(int j=0;j<=l[k];j++){
int vi=(i==l[k])?l[k]:(i+x)%l[k],vj=(j==l[k])?l[k]:(j+x)%l[k];
bf.mx[vi][vj]=b[k].mx[i][j];
}
b[k]=bf;
}
}
else {
(adt*=x)%=K; (mlt*=x)%=K;
for(int k=m;k>=1;k--){
int tx=gcd(l[k],x);
if(tx==1) {
bf.c=l[k];
for(int i=0;i<=l[k];i++){
int vi=(i==l[k])?l[k]:(i*x)%l[k];
for(int j=0;j<=l[k];j++){
int vj=(j==l[k])?l[k]:(j*x)%l[k];
bf.mx[vi][vj]=b[k].mx[i][j];
}
}
b[k]=bf;
}
else {
int ty=0; if(k==2 && l[k]/tx==l[1]) ty=1;
bf.set(l[k],1);
for(int i=0;i<=l[ty];i++){
int vi=i*tx;
bf.mx[vi][vi]=0;
for(int j=0;j<=l[k];j++)
if(j%tx>0 &&i<l[ty]) bf.mx[vi][j]=b[ty].mx[i][l[ty]];
else bf.mx[vi][j]=b[ty].mx[i][j/tx];
}
b[k]=bf;
}
}
}
}
} tr[N<<2];
void pushdown(int p){
if(tr[p].mlt!=1){
tr[p<<1].addt(tr[p].mlt,1);
tr[p<<1|1].addt(tr[p].mlt,1);
tr[p].mlt=1;
}
if(tr[p].adt){
tr[p<<1].addt(tr[p].adt,0);
tr[p<<1|1].addt(tr[p].adt,0);
tr[p].adt=0;
}
}
void pushup(int p){
for(int i=0;i<=m;i++)
tr[p].b[i]=tr[p<<1].b[i]*tr[p<<1|1].b[i];
}
void build(int p,int L,int R){
tr[p].adt=0; tr[p].mlt=1;
if(L==R){
for(int k=0;k<=m;k++){
tr[p].b[k].set(l[k],1);
for(int j=0;j<=l[k];j++) tr[p].b[k].mx[a[L]%l[k]][j]=1;
}
return ;
}
int mid=(L+R)/2;
build(p<<1,L,mid); build(p<<1|1,mid+1,R);
pushup(p);
}
void Mdf(int p,int L,int R,int lt,int rt,int x,int op){
if(L>=lt && R<=rt) { tr[p].addt(x,op); return ;}
int mid=(L+R)/2; pushdown(p);
if(lt<=mid) Mdf(p<<1,L,mid,lt,rt,x,op);
if(rt>mid) Mdf(p<<1|1,mid+1,R,lt,rt,x,op);
pushup(p);
}
matrix Qry(int p,int L,int R,int lt,int rt){
if(L>=lt && R<=rt) return tr[p].b[m];
int mid=(L+R)/2; pushdown(p);
if(lt<=mid && rt>mid) return Qry(p<<1,L,mid,lt,rt)*Qry(p<<1|1,mid+1,R,lt,rt);
else if(lt<=mid) return Qry(p<<1,L,mid,lt,rt);
else return Qry(p<<1|1,mid+1,R,lt,rt);
}
void vmain(){
n=read(); K=read(); Q=read();
l[m=0]=1; if(K==4) l[++m]=2;
l[++m]=K;
for(int i=1;i<=n;i++) a[i]=read();
build(1,1,n);
while(Q--){
int op=read(),l=read(),r=read(),x;
if(op==3){
matrix res=Qry(1,1,n,l,r); int ans=0;
for(int i=0;i<K;i++) (ans+=res.mx[i][K])%=P;
printf("%d\n",ans);
}
else {
x=read(); --op;
Mdf(1,1,n,l,r,x,op);
}
}
}
int main(){
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
int T=read(); while(T--) vmain();
return 0;
}