HDU 多校 Round #6 题解

\(\text{By DaiRuiChen007}\)

A. Count

Problem Link

题目大意

求有多少个长度为 \(n\)，字符集大小为 \(m\) 的字符串有长度为 \(n-k\) 的周期。

数据范围：\(n,m,k\le 10^{18}\)。

思路分析

\(k=n\) 时答案为 \(m^n\)，否则转为有长度为 \(k\) 的 Border，答案为 \(m^{n-k}\)。

时间复杂度 \(\mathcal O(\log n)\)。

代码呈现

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD=998244353;
inline int ksm(int a,int b,int p=MOD) {
	a%=MOD,b%=MOD-1;
	int ret=1;
	while(b) ret=(b&1?ret*a%p:ret),a=a*a%p,b=b>>1;
	return ret;
}
inline void solve() {
	int n,m,k;
	scanf("%lld%lld%lld",&n,&m,&k);
	printf("%lld\n",ksm(m,k==n?n:n-k));
}
signed main() {
	int T; scanf("%lld",&T);
	while(T--) solve();
	return 0;
}

B. Pair Sum and Perfect Square

Problem Link

题目大意

给一个 \(1\sim n\) 的排列 \(a\)，\(q\) 次询问 \(a_l\sim a_r\) 之间有多少对 \(a_i,a_j\) 的和为平方数。

数据范围：\(n,q\le 10^5\)。

思路分析

考虑暴力处理出所有的 \((i,j)\)，答案变成二维数点，注意到修改次数 \(\mathcal O(n\sqrt n)\)，查询次数 \(\mathcal O(q)\)，因此把树状数组换成 \(\mathcal O(1)\) 修改 \(\mathcal O(\sqrt n)\) 查询的分块来平衡复杂度即可。

时间复杂度 \(\mathcal O((n+q)\sqrt n)\)。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int a[MAXN],pos[MAXN],ans[MAXN];
struct Query { int l,r,id; };
vector <Query> Qry[MAXN];
int m,B,lp[MAXN],rp[MAXN],bel[MAXN],sum[MAXN],val[MAXN];
inline int qsum(int l,int r) {
    int ans=0;
    if(bel[l]==bel[r]) {
        for(int i=l;i<=r;++i) ans+=val[i];
        return ans;
    }
    for(int i=l;i<=rp[bel[l]];++i) ans+=val[i];
    for(int i=bel[l]+1;i<=bel[r]-1;++i) ans+=sum[i];
    for(int i=lp[bel[r]];i<=r;++i) ans+=val[i];
    return ans;
}
inline void solve() {
    int n,q;
    scanf("%d",&n);
    memset(sum,0,sizeof(sum)),memset(val,0,sizeof(val));
    B=sqrt(n),m=(n+B-1)/B;
    for(int i=1;i<=m;++i) lp[i]=(i-1)*B+1,rp[i]=min(i*B,n),fill(bel+lp[i],bel+rp[i]+1,i);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]),pos[a[i]]=i,Qry[i].clear();
    scanf("%d",&q);
    for(int i=1,l,r;i<=q;++i) scanf("%d%d",&l,&r),Qry[r].push_back({l,r,i});
    for(int i=1;i<=n;++i) {
        for(int k=1;k*k<=2*n;++k) if(1<=k*k-a[i]&&k*k-a[i]<=n) {
            int j=pos[k*k-a[i]];
            if(j<i) ++sum[bel[j]],++val[j];
        }
        for(auto o:Qry[i]) ans[o.id]=qsum(o.l,o.r);
    }
    for(int i=1;i<=q;++i) printf("%d\n",ans[i]);
}
signed main() {
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}

C. Vector

Problem Link

题目大意

给四个三维向量 \(a_1,a_2,a_3,a_4\)，判断有没有一组正实数解 \((x,y,z)\) 满足 \(a_1x+a_2y+a_3z=a_4\)。

数据范围：给定坐标均为非负整数。

思路分析

显然考虑高斯消元，然后根据 \(\mathrm{span}(a_1,a_2,a_3)\) 分别讨论一些 Corner Case：

\(\mathrm{span}(a_1,a_2,a_3)\) 为整个空间：直接高斯消元。
\(\mathrm{span}(a_1,a_2,a_3)\) 为一个平面：判断 \(a_4\) 是否在平面上，然后判断 \(a_4\) 是否在平面上的某一对向量的夹角之间。
\(\mathrm{span}(a_1,a_2,a_3)\) 为一条直线 / 一个点：判断 \(a_4\) 是否与直线同向 / 为零向量。

时间复杂度 \(\mathcal O(1)\)。

代码呈现

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct Vector{
    int x,y,z;
    Vector(int xx=0,int yy=0,int zz=0):x(xx),y(yy),z(zz){};
    inline void read() {
        scanf("%lld%lld%lld",&x,&y,&z);
    }
    inline friend Vector operator+(Vector ls,Vector rs) {
        return Vector(ls.x+rs.x,ls.y+rs.y,ls.z+rs.z);
    }
    inline friend Vector operator-(Vector ls,Vector rs) {
        return Vector(ls.x-rs.x,ls.y-rs.y,ls.z-rs.z);
    }
    inline friend Vector operator*(Vector ls,int k) { return Vector(ls.x*k,ls.y*k,ls.z*k); }
    inline friend int dot(Vector ls,Vector rs) { return ls.x*rs.x+ls.y*rs.y+ls.z*rs.z; }
    inline friend bool operator==(Vector ls,Vector rs) {
        return ls.x==rs.x&&ls.y==rs.y&&ls.z==rs.z;
    }
    inline friend bool operator!=(Vector ls,Vector rs) {
        return ls.x!=rs.x||ls.y!=rs.y||ls.z!=rs.z;
    }
    inline friend Vector cross(Vector ls,Vector rs) {
        return Vector(ls.y*rs.z-ls.z*rs.y,ls.z*rs.x-ls.x*rs.z,ls.x*rs.y-ls.y*rs.x);
    }
};
bool eqdir(Vector u,Vector v){
    Vector c=cross(u,v);
    if(c.x||c.y||c.z) return false;
    if(u.x*v.x<0||u.y*v.y<0||u.z*v.z<0) return false;
    return true;
}
const long double eps=1e-8;
const Vector v0={0,0,0};
void solve(){
    Vector a,b,c,d;
    a.read(),b.read(),c.read(),d.read();
    // three zero vectors.
    if(a==v0&&b==v0&&c==v0) return puts(d==v0?"YES":"NO"),void();
    // two zero vectors / colinear
    if(eqdir(a,b)&&eqdir(b,c)&&eqdir(c,a)) {
        return puts(eqdir(d,a)&&eqdir(d,b)&&eqdir(d,c)?"YES":"NO"),void();
    }
    // one zero vector, not colinear
    if(a==v0||b==v0||c==v0){
        if(a==v0) swap(a,c);
        if(b==v0) swap(b,c);
        if(dot(cross(a,b),d)) return puts("NO"),void();
        if(eqdir(d,a)||eqdir(d,b)) return puts("YES"),void();
        return puts(!eqdir(cross(d,a),cross(d,b))?"YES":"NO"),void();
    }
    // no zero vectors, a colinear pair and an other vector
    if(eqdir(a,b)||eqdir(b,c)||eqdir(a,c)) {
        if(eqdir(a,b)) swap(a,c);
        if(eqdir(a,c)) swap(a,b);
        if(dot(cross(a,b),d)) return puts("NO"),void();
        if(eqdir(d,a)||eqdir(d,b)) return puts("YES"),void();
        return puts(!eqdir(cross(d,a),cross(d,b))?"YES":"NO"),void();
    }
    // a,b,c in same plane
    if(!dot(cross(a,b),c)) {
        auto check=[&](Vector a,Vector b,Vector d) {
            if(dot(cross(a,b),d)) return false;
            if(eqdir(d,a)||eqdir(d,b)) return true;
            return !eqdir(cross(d,a),cross(d,b));
        };
        if(check(a,b,d)||check(b,c,d)||check(c,a,d)) return puts("YES"),void();
        return puts("NO"),void();
    }
    // no zero vectors, no colinear pairs.
    long double e[3][4];
    e[0][0]=a.x,e[0][1]=b.x,e[0][2]=c.x,e[0][3]=d.x;
    e[1][0]=a.y,e[1][1]=b.y,e[1][2]=c.y,e[1][3]=d.y;
    e[2][0]=a.z,e[2][1]=b.z,e[2][2]=c.z,e[2][3]=d.z;
    for(int i=0;i<3;++i) {
        for(int j=i;j<3;++j) {
            if(fabs(e[j][i])>eps) { swap(e[i],e[j]); break; }
        }
        assert(fabs(e[i][i])>eps);
        for(int j=3;j>=i;--j) e[i][j]/=e[i][i];
        for(int k=i+1;k<3;++k) {
            for(int j=3;j>=i;--j) e[k][j]-=e[k][i]*e[i][j];
        }
    }
    long double x[3];
    x[0]=e[0][3],x[1]=e[1][3],x[2]=e[2][3];
    for(int i=2;~i;--i) {
        for(int j=i-1;~j;--j) x[j]-=x[i]*e[j][i];
    }
    if(x[0]<-eps||x[1]<-eps||x[2]<-eps) puts("NO");
    else puts("YES");
}
signed main(){
    int T; scanf("%lld",&T);
    while(T--) solve();
    return 0;
}

D. Tree

Problem Link

题目大意

给一棵 \(n\) 个点的树，路径上每个点有一个 \(\{1,2,3\}\) 之中的颜色，求有多少路径上三种颜色节点数量均相同。

数据范围：\(n\le 10^5\)。

思路分析

直接点分治，记录路径上 \(1/2\) 颜色数之差，以及 \(2/3\) 颜色数之差即可。

时间复杂度 \(\mathcal O(n\log n)\)。

代码呈现

#include<bits/stdc++.h>
#define ll int long long
using namespace std;
const int MAXN=1e5+5;
int n,cur[MAXN],siz[MAXN],col[MAXN]; ll ans=0;
bool vis[MAXN];
vector <int> G[MAXN];
inline void solve(int u) {
	auto Hash=[&](array<int,2> arr) -> ll { return arr[0]*100000ll+arr[1]; };
	unordered_map <array<int,2>,int,decltype(Hash)> cnt(0,Hash);
//	cnt.push_back({rt[0]-rt[1],rt[1]-rt[2]});
	if(col[u]==0) ++cnt[{1,0}];
	if(col[u]==1) ++cnt[{-1,1}];
	if(col[u]==2) ++cnt[{0,-1}];
	for(int v:G[u]) if(!vis[v]) {
		vector <array<int,3>> Info;
		auto dfs=[&](auto self,int u,int fa,array<int,3> pa) -> void {
			++pa[col[u]],Info.push_back(pa);
			for(int v:G[u]) if(v!=fa&&!vis[v]) self(self,v,u,pa);
		};
		dfs(dfs,v,u,{0,0,0});
		for(auto I:Info) ans+=cnt[{I[1]-I[0],I[2]-I[1]}];
		for(auto I:Info) ++I[col[u]],++cnt[{I[0]-I[1],I[1]-I[2]}];
	}
}
inline void dfs(int u) {
	vis[u]=true,solve(u);
	for(int v:G[u]) if(!vis[v]) {
		int rt=0,tot=siz[v];
		auto find=[&](auto self,int u,int fa) -> void {
			siz[u]=1,cur[u]=0;
			for(int v:G[u]) if(!vis[v]&&v!=fa) {
				self(self,v,u);
				cur[u]=max(cur[u],siz[v]);
				siz[u]+=siz[v];
			}
			cur[u]=max(cur[u],tot-siz[u]);
			if(!rt||cur[u]<cur[rt]) rt=u;
		};
		find(find,v,u);
		dfs(rt);
	}
}
char str[MAXN];
signed main() {
	scanf("%d%s",&n,str+1);
	for(int i=1;i<=n;++i) col[i]=str[i]-'a';
	for(int i=1,u,v;i<n;++i) {
		scanf("%d%d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1);
	printf("%lld\n",ans);
	return 0;
}

E. Meadow

Problem Link

题目大意

给定一个 \(n\times m\) 的网格，每个格子有颜色 \(c_{i,j}\) 和一个权值 \(v_{i,j}\)，对于一个全黑的正方形子矩阵 \([i,i+k-1]\times[j,j+k-1]\)，其权值定义为子矩阵内的权值和的 \(k\) 倍。

求原网格所有正方形子矩阵的权值和。

数据范围：\(n,m\le 1000\)。

思路分析

考虑固定左上角 \((i,j)\)，二分得到最大的 \(k\) 使得 \([i\sim i+k]\times [j\sim j+k]\) 是全黑矩阵。

设 \(v_{i,j}\) 的二维前缀和为 \(S_{i,j}\)，那么左上角在 \(i,j\) 的子矩阵答案就是：

\[\sum_{t=0}^k (t+1)\times (S_{i+t,j+t}-S_{i+t,j-1}-S_{i-1,j+t}+S_{i-1,j-1}) \]

拆开分别维护处理，发现我们只要维护 \(S_{i,j}\) 的行和，列和，对角线和，以及 \(i\times S_{i,j}\) 的列和和对角线和，以及 \(j\times S_{i,j}\) 的行和，分别前缀和处理即可。

时间复杂度 \(\mathcal O(nm\log n)\)。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1005,MOD=1e9+7,i2=(MOD+1)/2;
int blo[MAXN][MAXN];
struct mint {
    int v;
    mint(int w=0) { v=(0<=w&&w<MOD)?w:(MOD+w%MOD)%MOD; }
    inline friend mint operator +(mint a,mint b) { return a.v+b.v>=MOD?a.v+b.v-MOD:a.v+b.v; }
    inline void operator +=(mint o) { v=v+o.v>=MOD?v+o.v-MOD:v+o.v; }
    inline void operator +=(int o) { v=v+o>=MOD?v+o-MOD:v+o; }
    inline friend mint operator -(mint a,mint b) { return a.v>=b.v?a.v-b.v:a.v+MOD-b.v; }
    inline void operator -=(mint o) { v=v>=o.v?v-o.v:v+MOD-o.v; }
    inline friend mint operator *(mint a,mint b) { return 1ll*a.v*b.v%MOD; }
    inline void operator *=(mint o) { v=1ll*v*o.v%MOD; }
};
mint val[MAXN][MAXN],col[MAXN][MAXN][2],row[MAXN][MAXN][2],arr[MAXN][MAXN][2];
inline void solve() {
	int n,m; cin>>n>>m;
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=m;++j) {
			cin>>blo[i][j],blo[i][j]^=1;
			blo[i][j]+=blo[i][j-1]+blo[i-1][j]-blo[i-1][j-1];
		}
	}
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=m;++j) {
			int x; cin>>x;
			val[i][j]=x+val[i][j-1]+val[i-1][j]-val[i-1][j-1];
		}
	}
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=m;++j) {
			row[i][j][0]=row[i][j-1][0]+val[i][j];
			row[i][j][1]=row[i][j-1][1]+val[i][j]*j;
			col[i][j][0]=col[i-1][j][0]+val[i][j];
			col[i][j][1]=col[i-1][j][1]+val[i][j]*i;
			arr[i][j][0]=arr[i-1][j-1][0]+val[i][j];
			arr[i][j][1]=arr[i-1][j-1][1]+val[i][j]*i;
		}
	}
	mint ans=0;
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=m;++j) {
			int L=0,R=min(n-i,m-j),T=-1;
			while(L<=R) {
				int mid=(L+R)>>1;
				if(blo[i+mid][j+mid]+blo[i-1][j-1]==blo[i+mid][j-1]+blo[i-1][j+mid]) {
					T=mid,L=mid+1;
				} else R=mid-1;
			}
			if(T==-1) continue;
			ans+=arr[i+T][j+T][1]-arr[i-1][j-1][1];
			ans-=(i-1)*(arr[i+T][j+T][0]-arr[i-1][j-1][0]);
			ans-=row[i-1][j+T][1]-row[i-1][j-1][1];
			ans+=(j-1)*(row[i-1][j+T][0]-row[i-1][j-1][0]);
			ans-=col[i+T][j-1][1]-col[i-1][j-1][1];
			ans+=(i-1)*(col[i+T][j-1][0]-col[i-1][j-1][0]);
			ans+=val[i-1][j-1]*(T+1)*(T+2)*i2;
		}
	}
	cout<<ans.v<<"\n";
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	int T; cin>>T;
	while(T--) solve();
	return 0;
}

F. Perfect square number

Problem Link

题目大意

给一个长度为 \(n\) 的序列 \(a_1\sim a_n\)，值域为 \([1,V]\) 其中 \(V=300\)，\(f(a)\) 定义为满足 \(\sum_{i=l}^ra_i\) 为平方数的 \((l,r)\) 个数。

修改一个 \(a_i\) 为 \([1,V]\) 中的任意值，求最大的可能的 \(f(a')\)。

数据范围：\(n\le 300\)。

思路分析

注意到我们只要维护每个 \(a_i\to x\) 的答案 \(f_{i,x}\)，考虑一个区间 \(a_l\sim a_r\)，考虑使区间和从 \(S\) 变成 \(k^2\)，那么相当于给每个 \(f_{i,k^2-S}\) 增加一，做个差分即可维护。

注意特殊处理减少掉的区间。

时间复杂度 \(\mathcal O(n^2V)\)。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=305,V=300;
int a[MAXN];
inline void solve() {
	int n,sum=0;
	scanf("%d",&n);
	unordered_map <int,vector<int>> cnt;
	for(int i=-V;i<=V;++i) cnt[i].resize(n+2,0);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	for(int l=1;l<=n;++l) {
		for(int r=l,s=0;r<=n;++r) {
			s+=a[r];
			for(int v=1;v<=V;++v) {
				int k=v*v-s;
				sum+=(k==0);
				if(-V<=k&&k<=V) ++cnt[k][l],--cnt[k][r+1];
			}
		}
	}
	int ans=sum;
	for(int k=-V;k<=V;++k) {
		for(int i=1;i<=n;++i) {
			cnt[k][i]+=cnt[k][i-1];
		}
	}
	for(int k=-V;k<=V;++k) {
		for(int i=1;i<=n;++i) {
			if(1<=a[i]+k&&a[i]+k<=V) {
				ans=max(ans,sum+cnt[k][i]-cnt[0][i]);
			}
		}
	}
	printf("%d\n",ans);
}
signed main() {
	int T; scanf("%d",&T);
	while(T--) solve();
	return 0;
}

G. Competition

Problem Link

题目大意

你在玩一个游戏，初始你有两个数 \(x=1,y=0\)，游戏有 \(n\) 轮，每轮有两种情况：

若你赢：\(y\gets y+2,x\gets x\times y\)，先加后乘。

若你输：\(y\gets y-1\)。

已知你恰好输了 \(k\) 场，求所有可能游戏过程对应的 \(x\) 的和。

数据范围：\(n\le 1.5\times10^5,k\le 10^5\)。

思路分析

考虑记 \(f_{n,k}\) 表示 \(n\) 场输 \(k\) 场的答案，容易得到转移：\(f_{n,k}=f_{n-1,k-1}+(2n-3k)f_{n-1,k}\)。

考虑生成函数，设 \(F_n(x)=\sum x^kf_{n,k}\)，得到：\(F_n(x)=xF_{n-1}(x)+2nF_{n-1}(x)-3xF_{n-1}'(x)\)。

考虑把 \(xF_{n-1}(x)-3xF'_{n-1}(x)\) 合成一项，注意到 \((e^{-x/3}f(x))'=e^{-x/3}f'(x)-\dfrac 13e^{-x/3} f(x)\).

因此记 \(G_{n}(x)=e^{-x/3}F_n(x)\)，则有 \(G_n'(x)=\dfrac 13(3e^{-x/3}F_{n-1}(x)-e^{-x/3}F_{n-1}(x))\)。

因此得到新的转移：\(G_n(x)=-3xG_{n-1}'(x)+2nG_{n-1}(x)\)，展开得到：\(g_{n,k}=2n\times g_{n-1,k}-3k\times g_{n-1,k}\)。

因此 \(g_{n,k}=g_{0,k}\prod_{i=1}^n(2i-3k)\)，其中 \(g_{0,k}=[x^k]e^{-x/3}\)，最后的答案再卷上 \(e^{x/3}\) 次方的第 \(k\) 项就是答案。

考虑如何求 \(c_k=\prod_{i=1}^n(2i-3k)\)，暴力出 \(c_0,c_1\)，然后发现 \(c_k=c_{k-2}\times\dfrac{2-3k}{2+2n-3k}\times \dfrac{4-3k}{4+2n-3k}\times \dfrac{6-3k}{6+2n-3k}\)，然后就可以递推了。

根据泰勒展开得到 \(e^{x/3}=\sum_{k=0}^\infty \dfrac{x^k}{3^k\times k!}, e^{-x/3}=\sum_{k=0}^\infty \dfrac{(-1)^k\times x^k}{3^k\times k!}\)，暴力计算即可。

时间复杂度 \(\mathcal O(n\log P)\)，精细实现可以做到 \(\mathcal O(n)\)。

代码呈现

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2e5+5,MOD=998244353,i3=(MOD+1)/3;
int fac[MAXN],ifac[MAXN],f[MAXN],g[MAXN];
inline int ksm(int a,int b=MOD-2,int p=MOD) {
	int ret=1;
	while(b) ret=(b&1?ret*a%p:ret),a=a*a%p,b=b>>1;
	return ret;
}
signed main() {
	int n,k;
	scanf("%lld%lld",&n,&k),n+=k;
	for(int i=fac[0]=ifac[0]=1;i<=n;++i) ifac[i]=ksm(fac[i]=i*fac[i-1]%MOD);
	for(int i=0;i<=k;++i) { //e^{-x/3}
		f[i]=ksm(i3,i)*ifac[i]%MOD;
		if(i&1) f[i]=(MOD-f[i])%MOD;
	}
	for(int j:{0,1}) {
		g[j]=1;
		for(int i=1;i<=n;++i) g[j]=(2*i+3*(MOD-j))%MOD*g[j]%MOD;
	}
	for(int j=2;j<=k;++j) {
		//g[j] = prod_{i=1~n}(2i-3j)
		int t=3*(MOD-j)%MOD;
		g[j]=g[j-2]*ksm((2*n+t+6)%MOD)%MOD*ksm((2*n+t+4)%MOD)%MOD*ksm((2*n+t+2)%MOD)%MOD;
		g[j]=g[j]*(2+t)%MOD*(4+t)%MOD*(6+t)%MOD;
	}
	for(int j=0;j<=k;++j) f[j]=f[j]*g[j]%MOD;
	int ans=0;
	for(int j=0;j<=k;++j) { //convolution with e^{x/3}
		ans=(ans+f[k-j]*ksm(i3,j)%MOD*ifac[j]%MOD)%MOD;
	}
	printf("%lld\n",ans);
	return 0;
}

H. Alice and Bob

Problem Link

题目大意

给一个长度为 \(n\) 的序列，AB 两人轮流操作，每人可以把序列分成两段，保留权值和较大的一段，不能操作的人输。

如果某人必胜，则最大化最后得到的数，否则最小化最后得到的数，求谁赢，以及最后的数。

数据范围：\(n\le 3000\)。

思路分析

考虑区间 dp，设 \(dp_{l,r}\) 表示区间 \(l,r\) 的答案，先手必胜则为正，否则为负，求出序列中点 \(mid\) 使得 \(S(l,mid)\ge S(mid+1,r)\)，那么得到转移方程：

\[dp_{l,r}=-\min\left\{\min_{k=l+1}^{mid}dp_{k,r}\ ,\ \min_{k=mid}^{r-1} dp_{l,k}\right\} \]

注意到转移过程中，同一个 \(dp_{l,*}\)，所询问的区间一定是向右单调的，单调队列优化即可，\(dp_{*,r}\) 同理维护即可。

时间复杂度 \(\mathcal O(n^2)\)。

代码呈现

#include<bits/stdc++.h>
#pragma GCC optimize(2,3,"Ofast")
#define ll long long
using namespace std;
mt19937 rnd(time(0));
const int MAXN=3003,inf=2e9;
struct MQ {
	int val[MAXN],q[MAXN],hd,tl,lst;
	inline int query(int l,int r) {
		if(l>r) return inf;
		assert(lst<=r);
		for(int i=lst+1;i<=r;++i) {
			while(hd<=tl&&val[q[tl]]>=val[i]) --tl;
			q[++tl]=i;
		}
		lst=r;
		while(hd<=tl&&q[hd]<l) ++hd;
		return val[q[hd]];
	}
	inline void clear() { hd=1,tl=0,lst=0; }
}	pre[MAXN],suf;
ll s[MAXN];
inline ll sum(int l,int r) { return l<=r?s[r]-s[l-1]:0; }
int n,a[MAXN],dp[MAXN][MAXN],o[MAXN][MAXN];
void solve() {
	cin>>n;
	for(int i=1;i<=n;++i) pre[i].clear();
	for(int i=1;i<=n;++i) cin>>a[i],s[i]=s[i-1]+a[i];
	for(int i=1;i<=n;++i) {
		dp[i][i]=-a[i];
		pre[i].val[n-i+1]=dp[i][i];
		pre[i].lst=n-i;
	}
	for(int l=n;l>=1;--l) {
		suf.clear(),suf.lst=l-1,suf.val[l]=dp[l][l];
		for(int r=l+1,mid=l;r<=n;++r) {
			mid=max(mid,l);
			while(mid<r&&sum(l,mid)<sum(mid+1,r)) ++mid;
			dp[l][r]=-min(pre[r].query(n-mid+1,n-l),suf.query(mid,r-1));
			suf.val[r]=dp[l][r];
			pre[r].val[n-l+1]=dp[l][r];
		}
	}
	if(dp[1][n]>0) cout<<"Alice "<<abs(dp[1][n])<<"\n";
	else cout<<"Bob "<<abs(dp[1][n])<<"\n";
}
int main() {
	ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
	int T; cin>>T;
	while(T--) solve();
	return 0;
}

I. Coloration

Problem Link

题目大意

给一张 \(n\) 点 \(m\) 边的无向连通图，点边都有权值且边权互不相同。

对于某条边 \(e\)，当且仅当存在一条路径 \(u\to v\) 使得 \(e\) 是路径上最大权值且 \(val(u)\ge val(e)\)，则 \(u\in S(e)\)。

对于每个点有染黑或染白的代价，对于每条边要求 \(S(e)\) 中的黑点不超过 \(x(e)\) 个，白点不超过 \(y(e)\) 个，求最小染色代价。保证有解。

数据范围：\(n\le 1000\)。

思路分析

注意到 \(S(e)\) 就是 Kruskal 重构树上 \(e\) 子树内 \(val(u)\ge val(e)\) 的点，考虑建立网络流模型，先给每个点染白，然后用流量到 \(e\) 的表示 \(S(e)\) 中的黑边数量，在 Kruskal 重构树上传递即可，而 \(val(u)\ge val(e)\) 则把每个 \(u\) 在第一个 \(val(e)>val(u)\) 的点上连回流边起删除作用。

为了限制 \(x(e),y(e)\)，把每个点拆点，中间连带上下界的边来限制 \(S(e)\) 中的黑点个数即可，原问题转化成了一个无源汇上下界最小费用可行流问题，转成一般的最小费用最大流后，由于可能有负环，因此要再加一对源汇跑消圈费用流。

时间复杂度 \(\mathcal O(n^3)\)。

代码呈现

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct Edge0 { int v,lst,f,c; }; //edge in spfa
struct Edge1 { int u,v,f,c; }; //edge in origin net graph
struct Edge2 { int u,v,w,l0,l1; }; //edge in origin tree
namespace MCMF {
const int MAXV=1e4+5,MAXE=2e5+5,inf=1e18;
Edge0 G[MAXE];
int ecnt=1,hd[MAXV];
inline void adde(int u,int v,int f,int c) {
	G[++ecnt]={v,hd[u],f,c},hd[u]=ecnt;
}
inline void link(int u,int v,int f,int c) {adde(u,v,f,c),adde(v,u,0,-c); }
int dis[MAXV],lst[MAXV],pre[MAXV]; //lst: last edge, pre: last ver
bool inq[MAXV];
inline bool SPFA(int S,int T) {
	memset(dis,0x3f,sizeof(dis));
	memset(lst,-1,sizeof(lst));
	memset(pre,-1,sizeof(pre));
	memset(inq,false,sizeof(inq));
	queue <int> Q;
	Q.push(S),dis[S]=0,inq[S]=true;
	while(!Q.empty()) {
		int u=Q.front(); Q.pop();
		inq[u]=false;
		for(int i=hd[u];i;i=G[i].lst) if(G[i].f&&dis[u]+G[i].c<dis[G[i].v]) {
			int v=G[i].v;
			dis[v]=dis[u]+G[i].c;
			pre[v]=u,lst[v]=i;
			if(!inq[v]) inq[v]=true,Q.push(v);
		}
	}
	return ~pre[T];
}
int cost,flow;
inline void aug(int S,int T) {
	int g=inf;
	for(int u=T;u!=S;u=pre[u]) g=min(g,G[lst[u]].f);
	flow+=g,cost+=g*dis[T];
	for(int u=T;u!=S;u=pre[u]) G[lst[u]].f-=g,G[lst[u]^1].f+=g;
}
int deg[MAXV];
inline array<int,2> SSP(const vector<Edge1>&N,int s,int t,int tot) {
	int S=++tot,T=++tot,tmp=0;
	for(auto e:N) {
		if(e.c>=0) {
			link(e.u,e.v,e.f,e.c);
		} else {
			deg[e.u]-=e.f,deg[e.v]+=e.f;
			tmp+=e.f*e.c;
			link(e.v,e.u,e.f,-e.c);
		}
	}
	for(int i=1;i<=tot-2;++i) {
		if(deg[i]>0) link(S,i,deg[i],0);
		else link(i,T,-deg[i],0);
	}
	link(t,s,inf,0);
	while(SPFA(S,T)) aug(S,T);
	flow=0;
	while(SPFA(s,t)) aug(s,t);
	return {flow,cost+tmp};
}
inline void init() {
	cost=0,flow=0,ecnt=1;
	memset(hd,0,sizeof(hd));
	memset(deg,0,sizeof(deg));
}
}
const int MAXN=2005,inf=1e18;
int val[MAXN],c0[MAXN],c1[MAXN];
int dsu[MAXN],l0[MAXN],l1[MAXN],fa[MAXN];
inline int find(int x) { while(x^dsu[x]) x=dsu[x]=dsu[dsu[x]]; return x; }
int s[MAXN],t[MAXN],siz[MAXN],deg[MAXN];
inline void solve() {
	int n,m,ans=0;
	cin>>n>>m;
	MCMF::init();
	vector <Edge1> N;
	vector <Edge2> E(m);
	for(int i=1;i<=n;++i) cin>>c0[i]>>c1[i]>>val[i];
	for(auto &e:E) cin>>e.u>>e.v>>e.w;
	for(auto &e:E) cin>>e.l0;
	for(auto &e:E) cin>>e.l1;
	sort(E.begin(),E.end(),[&](auto e1,auto e2){ return e1.w<e2.w; });
	iota(dsu+1,dsu+n+1,1);
	int p=n,tot=n;
	for(auto &e:E) {
		int x=find(e.u),y=find(e.v);
		if(x==y) continue;
		++p,dsu[p]=dsu[x]=dsu[y]=p,fa[x]=fa[y]=p;
		l0[p]=e.l0,l1[p]=e.l1,val[p]=e.w;
		s[p]=++tot,t[p]=++tot,siz[p]=0;
	}
	auto link=[&](int u,int v,int l,int r,int c) {
		deg[u]-=l,deg[v]+=l;
		N.push_back({u,v,r-l,c});
	};
	for(int i=1;i<=n;++i) {
		link(i,s[fa[i]],0,1,c1[i]-c0[i]);
		ans+=c0[i];
		int u;
		for(u=fa[i];u&&val[i]>=val[u];u=fa[u]) ++siz[u];
		if(u) link(s[u],i,0,1,0);
		else link(t[p],i,0,1,0);
	}
	for(int i=n+1;i<=p;++i) {
		link(s[i],t[i],max(0ll,siz[i]-l0[i]),l1[i],0);
		if(i<p) link(t[i],s[fa[i]],0,inf,0);
	}
	int s=++tot,t=++tot;
	for(int i=1;i<=tot-2;++i) {
		if(deg[i]>0) link(s,i,0,deg[i],0);
		else link(i,t,0,-deg[i],0);
		deg[i]=0;
	}
	cout<<ans+MCMF::SSP(N,s,t,tot)[1]<<"\n";
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	int T; cin>>T;
	while(T--) solve();
	return 0;
}

J. Calculate

Problem Link

题目大意

给一棵基环内向树，你有一个数 \(x\)，经过某个 \(i\) 会使得 \(x\gets k_ix+b_i\)。

\(q\) 次询问：从 \(u\) 出发以 \(x_0\) 的初值走 \(d\) 步后的 \(x\) 是多少。

数据范围：\(n,q\le 10^5,V=\max d\le 10^9\)。

思路分析

由于一次函数变换可以合并，因此直接维护倍增即可。

时间复杂度 \(\mathcal O((n+q)\log V)\)。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5,MOD=1e9+7;
int fa[MAXN][31];
struct Info {
	int k,b;
	inline friend Info operator *(Info u,Info v) { return {1ll*u.k*v.k%MOD,(1ll*u.b*v.k+v.b)%MOD}; }
}	w[MAXN][31],I[MAXN];
inline void solve() {
	int n,q; cin>>n>>q;
	for(int i=1;i<=n;++i) cin>>I[i].k;
	for(int i=1;i<=n;++i) cin>>I[i].b;
	for(int i=1;i<=n;++i) cin>>fa[i][0],w[i][0]=I[fa[i][0]];
	for(int k=1;k<31;++k) for(int i=1;i<=n;++i) {
		fa[i][k]=fa[fa[i][k-1]][k-1];
		w[i][k]=w[i][k-1]*w[fa[i][k-1]][k-1];
	}
	for(int x,d,u;q--;) {
		cin>>u>>d>>x;
		Info I={1,0};
		for(int k=0;k<31;++k) if(d&(1<<k)) I=I*w[u][k],u=fa[u][k];
		cout<<(1ll*I.k*x+I.b)%MOD<<"\n";
	}
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	int T; cin>>T;
	while(T--) solve();
	return 0;
}

K. String

Problem Link

题目大意

给定一个字符串 \(S\)，\(q\) 次询问给定字符串 \(T\)，随机选择一个 \(T\) 的子串 \(T'\)，求 \(S\) 中包含 \(T'\) 的子串数量的期望。

数据范围：\(n=|S|\le 10^6,m=\sum |T|\le 10^6\)。

思路分析

考虑 \(T=S\)，建出 SAM，观察 \(S\) 的每个等价类 \(\{r_1,r_2,\dots,r_k\}\)，对应的子串数就是 \(\sum_{i=1}^k (r_{i+1}-r_i)\times l_i\)，其中 \(r_{k+1}=n+1\)。

容易发现方案数是关于串长 \(len\) 的一次函数 \(f\)，线段树合并维护 \(f\)，每个节点的答案都是 \(f\) 的一段区间和。

然后考虑一般情况，考虑 \(T\) 的一个前缀，容易在 \(S\) 的后缀自动机上匹配到最长的一段后缀和对应的 SAM 节点，答案就是这个节点 Parent Tree 上祖先的贡献加上这个点的贡献，注意这个点的贡献可能不是满的（区间不一定是上界）要单独算。

时间复杂度 \(\mathcal O(n\log n+m)\)。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5,MOD=998244353;
int n,q;
char s[MAXN],t[MAXN];
struct Info {
    int lp,rp,b;
    inline friend Info operator +(Info L,Info R) {
        if(!L.lp) return R;
        if(!R.lp) return L;
        int g=R.lp-L.rp,b=(L.b+R.b)%MOD;
        return {L.lp,R.rp,(b+1ll*(L.rp+1)*g%MOD)%MOD};
    }
};
class SegmentTree {
    private:
        struct Node {
            int ls,rs;
            Info I; //f(x) = ax+b
        }    tr[MAXN*20];
        inline void pushup(int p) { tr[p].I=tr[tr[p].ls].I+tr[tr[p].rs].I; }
        int siz;
    public:
        inline void init() {
            for(int i=1;i<=siz;++i) tr[i]={0,0,{0,0,0}};
            siz=0;
        }
        inline void Insert(int u,int l,int r,int &p) {
            p=++siz;
            if(l==r) return tr[p].I={l,r,0},void();
            int mid=(l+r)>>1;
            if(u<=mid) Insert(u,l,mid,tr[p].ls);
            else Insert(u,mid+1,r,tr[p].rs);
            pushup(p);
        }
        inline void Merge(int l,int r,int q,int &p) {
            if(!q||!p) return p|=q,void();
            if(l==r) return tr[p].I={l,r,0},void();
            int mid=(l+r)>>1;
            Merge(l,mid,tr[q].ls,tr[p].ls),Merge(mid+1,r,tr[q].rs,tr[p].rs);
            pushup(p);
        }
        inline int print(int u,int l,int r,int p) {
            if(!p) return 0;
            if(l==r) return 1;
            int mid=(l+r)>>1;
            return u<=mid?print(u,l,mid,tr[p].ls):print(u,mid+1,r,tr[p].rs);
        }
        inline Info Query(int p) { return tr[p].I; }
}    TR;
int rt[MAXN<<1];
struct Node {
    map <char,int> ch;
    int link,len;
}    tr[MAXN<<1];
int tot,lst;
inline int insert(char c) {
    int cur=++tot,p=lst;
    tr[cur].len=tr[lst].len+1;
    while(p&&!tr[p].ch.count(c)) tr[p].ch[c]=cur,p=tr[p].link;
    if(!p) tr[cur].link=1;
    else {
        int q=tr[p].ch[c];
        if(tr[q].len==tr[p].len+1) tr[cur].link=q;
        else {
            int r=++tot;
            tr[r]=tr[q],tr[r].len=tr[p].len+1;
            tr[q].link=tr[cur].link=r;
            while(p&&tr[p].ch[c]==q) tr[p].ch[c]=r,p=tr[p].link;
        }    
    }
    return lst=cur;
}
vector <int> G[MAXN<<1];
int val[MAXN<<1],a[MAXN<<1],b[MAXN<<1];
inline int calc(int a,int b,int lo,int hi) { //ax+b when lo<x<=hi
    auto c1=[&](int x) { return 1ll*x*(x+1)/2%MOD; };
    auto c0=[&](int x) { return x; };
    int ans=0;
    ans=(ans+1ll*a*(c1(hi)+MOD-c1(lo))%MOD)%MOD;
    ans=(ans+1ll*b*(c0(hi)+MOD-c0(lo))%MOD)%MOD;
    return ans;
}
inline int ksm(int a,int b=MOD-2,int p=MOD) {
    int ret=1;
    while(b) ret=(b&1?1ll*ret*a%p:ret),a=1ll*a*a%p,b=b>>1;
    return ret;
}
inline void dfs0(int u) {
    for(int v:G[u]) dfs0(v),TR.Merge(1,n,rt[v],rt[u]);
    Info I=TR.Query(rt[u]);
    int g=(n+1-I.rp);
    a[u]=MOD-(n+1-I.lp),b[u]=(I.b+1ll*g*(I.rp+1)%MOD)%MOD;
    val[u]=calc(a[u],b[u],tr[tr[u].link].len,tr[u].len);
}
inline void dfs1(int u) {
    for(int v:G[u]) val[v]=(val[v]+val[u])%MOD,dfs1(v);
}
inline void solve() {
    TR.init();
    memset(rt,0,sizeof(rt));
    for(int i=1;i<=tot;++i) tr[i].link=tr[i].len=0,tr[i].ch.clear(),G[i].clear();
    tot=lst=1;
    scanf("%d%d%s",&n,&q,s+1);
    for(int i=1;i<=n;++i) TR.Insert(i,1,n,rt[insert(s[i])]);
    for(int i=2;i<=tot;++i) G[tr[i].link].push_back(i);
    dfs0(1),dfs1(1);
    while(q--) {
        scanf("%s",t+1);
        int m=strlen(t+1),p=1,ans=0;
        for(int i=1,len=0;i<=m;++i) {
            if(tr[p].ch.count(t[i])) p=tr[p].ch[t[i]],++len;
            else {
                while(p&&!tr[p].ch.count(t[i])) p=tr[p].link;
                if(!p) p=1,len=0;
                else len=tr[p].len+1,p=tr[p].ch[t[i]];
            }
            if(p!=1) {
                ans=(ans+val[tr[p].link])%MOD;
                ans=(ans+calc(a[p],b[p],tr[tr[p].link].len,len))%MOD;
            }
        }
        printf("%lld\n",1ll*ans*ksm((1ll*m*(m+1)/2)%MOD)%MOD);
    }
}
signed main() {
    int T; scanf("%d",&T);
    while(T--) solve();
    return 0;
}