ABC240 G - Teleporting Takahashi

题目传送门

分析

三个维度一起求不行，考虑两个维度先求出来，

设 \(f[i]\) 表示横坐标和纵坐标共走 \(i\) 个来回的方案数。

那么就是枚举横坐标走了 \(j\) 个来回，那么纵坐标走了 \(i-j\) 个来回。

四种方向需要走的步数分别为 \(x+j,j,y+i-j,i-j\)

考虑尽量留较少的 \(j\) 以方便消去。

不妨先在当中选择 \(i\) 步来走 \(j\) 和 \(i-j\) 两个方向。

那也就是 \(\binom{x+y+i*2}{i}\binom{i}{j}\)

再在当中选 \(y+i-j\) 步，合起来就是

\(f[i]=\binom{x+y+i*2}{i}\sum_{j=0}^i\binom{x+y+i}{y+i-j}\binom{i}{j}\)

可以发现后式是一个范德蒙德卷积，直接合并即可

\(f[i]=\binom{x+y+i*2}{i}\binom{x+y+i*2}{y+i}\)

然后再将这 \(i\) 步插入第三维中即可。

代码

#include 
using namespace std;
const int N=10000011,mod=998244353;
int n,m,x,y,z,fac[N],inv[N],ans,f[N];
int c(int n,int m){return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;}
int main(){
	cin>>n>>x>>y>>z;
	if (x<0) x=-x;
	if (y<0) y=-y;
	if (z<0) z=-z;
	m=n,n-=x+y+z;
	if (n<0||(n&1)){
		cout<<0;
		return 0;
	}
	n>>=1,fac[0]=fac[1]=inv[0]=inv[1]=1;
	for (int i=2;i<=m;++i) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
	for (int i=2;i<=m;++i) inv[i]=1ll*inv[i-1]*inv[i]%mod,fac[i]=1ll*fac[i-1]*i%mod;
	for (int i=0;i<=n;++i) f[i]=1ll*c(x+y+i*2,x+y+i)*c(x+y+i*2,y+i)%mod;
	for (int i=0;i<=n;++i) ans=(ans+1ll*f[n-i]*c(m,i)%mod*c(m-i,z+i)%mod)%mod;
	return !printf("%d",ans);
}

ABC240 Ex - Sequence of Substrings

题目传送门

分析

第一步模型转换才是最重要的。

如果将这个字符串的所有子串抽取出来，那么字典序严格递增要满足 \(r_i

这与求最长上升子序列很类似，或者换句话说，最长上升子序列的决策区间长度一定为 1。

可不可以将这道题转化成最长上升子序列，答案是肯定的。

在lower_bound之后不直接加入答案数组，而在到达子串末尾时再尝试添加到答案数组。

由于固定左端点的子串字典序一定单调递增，所以可以直接用一个双指针扫描，判断大小可以用哈希比较 \(LCP\) 做到一个 \(\log\)

那么就是 \(O(n^2\log n)\) 吗，显然不是，考虑到加入答案数组的子串长度一定可以不超过 \(\sqrt{2n}\)，所以子串长度只需要枚举到 \(\sqrt{2n}\) 级别。

所以最后时间复杂度为 \(O(n\sqrt{2n}\log{n})\)，考虑到空间复杂度也可以优化，

垃圾回收就可以做到 \(O(2n)\)（只有 \(\sqrt{2n}\) 个时刻需要保留，每个时刻最多保留 \(\sqrt{2n}\) 个决策）

代码

#include 
#include 
using namespace std;
const int N=25011,mod=998244353; struct node{int y,w,next;}e[N<<1];
int h[N],p[N],n,mx,l[N],r[N],et,ans,as[N],st[N<<1],Top; char s[N];
int min(int a,int b){return as[ly];
	int l=1,r=min(rx-lx+1,ry-ly+1),mn=r;
	while (l>1;
		if (query(lx,lx+mid-1)==query(ly,ly+mid-1)) l=mid;
		    else r=mid-1;
	}
	if (r==mn) return rx-lx+1>ry-ly+1;
	    else return s[lx+r]>s[ly+r];
}
int main(){
	scanf("%d%s",&n,s+1),mx=sqrt(2*n);
	s[n+1]=50,l[ans=1]=r[1]=n+1,p[0]=1;
	for (int i=1;i<=n+1;++i) p[i]=331ll*p[i-1]%mod;
	for (int i=1;i<=n+1;++i) h[i]=(331ll*h[i-1]+s[i]-48)%mod;
	for (int i=1;i<=n;++i){
		for (int j=i,k=1;jans) {++ans,l[ans]=r[ans]=n+1; break;}
		}
		for (int j=as[i];j;j=e[j].next){
			int I=e[j].y,J=i,t=e[j].w; st[++Top]=j;
			if (geq(l[t],r[t],I,J)) l[t]=I,r[t]=J;
		}
		as[i]=0;
	}
	return !printf("%d",ans);
}