差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:other:错题集_3 [2020/08/27 19:50]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:other:错题集_3 [2020/08/31 18:12] (当前版本)
jxm2001
@@ 行 407: / 行 407: @@
 </hidden>
-===== 5、四月樱花 =====
+===== 6、四月樱花 =====
 [[https://www.luogu.com.cn/problem/P6788|链接]]
@@ 行 422: / 行 422: @@
 $$\prod_{x=1}^n\prod_{y\mid x}\cfrac {y^{\tau(x)}}{\prod_{z\mid y}(z+1)^2}$$
+$$
+\begin{equation}\begin{split}
+s&=\prod_{x=1}^n\prod_{y\mid x}\cfrac {y^{\tau(x)}}{\prod_{z\mid y}(z+1)^2}\\
+&=\prod_{x=1}^n\prod_{y\mid x}\cfrac {\prod_{z\mid y}z^2}{\prod_{z\mid y}(z+1)^2}\\
+&=\prod_{x=1}^n\prod_{y\mid x}\prod_{z\mid y}\cfrac {z^2}{(z+1)^2}\\
+&=\prod_{y=1}^n\left(\prod_{z\mid y}\cfrac {z^2}{(z+1)^2}\right)^{\lfloor\frac ny\rfloor}\\
+&=\prod_{z=1}^n\left(\cfrac z{z+1}\right)^{2\sum_{k=1}^{\lfloor\frac nz\rfloor}\lfloor\frac n{kz}\rfloor}
+\end{split}\end{equation}
+$$
+令 $f(n)=\sum_{i=1}^n \lfloor\frac ni\rfloor$，于是上式变为
+$$s=\prod_{z=1}^n\left(\cfrac z{z+1}\right)^{2f(\lfloor\frac nz\rfloor)}$$
+考虑分块，有
+$$\prod_{z=l}^r\left(\cfrac z{z+1}\right)^{2f(\lfloor\frac nz\rfloor)}=\left(\prod_{z=l}^r\cfrac z{z+1}\right)^{2f(\lfloor\frac nl\rfloor)}=\left(\frac l{r+1}\right)^{2f(\lfloor\frac nl\rfloor)}$$
+$f(\frac nl)$ 也可以通过分块计算。总时间复杂 $O\left(\sum_{i=1}^{\sqrt n}\sqrt i+\sqrt {\frac ni}\right)=O\left(n^{\frac 34}\right)$。
+<hidden 查看代码>
+<code cpp>
+int Mod;
+int quick_pow(unsigned int a,int b){
+	int ans=1;
+	while(b){
+		if(b&1)ans=1LL*ans*a%Mod;
+		a=1LL*a*a%Mod;
+		b>>=1;
+	}
+	return ans;
+}
+int cal(unsigned int n){
+	unsigned int l=1,r;
+	int ans=0;
+	while(l<=n){
+		r=n/(n/l);
+		ans=(ans+1LL*(r-l+1)*(n/l))%(Mod-1);
+		l=r+1;
+	}
+	return ans;
+}
+int main()
+{
+	unsigned int n=read_LL(),l=1,r;
+	Mod=read_int();
+	int ans=1;
+	while(l<=n){
+		r=n/(n/l);
+		ans=1LL*ans*quick_pow(1LL*l*quick_pow(r+1,Mod-2)%Mod,cal(n/l))%Mod;
+		l=r+1;
+	}
+	enter(1LL*ans*ans%Mod);
+	return 0;
+}
+</code>
+</hidden>
+==== 优化 ====
+$$\sum_{i=1}^n \lfloor\frac ni\rfloor=\sum_{i=1}^n \tau (i)$$
+考虑线性筛处理 $O\left(n^{\frac 23}\right)$ 的 $\tau (n)$ 的前缀和，大于 $n^{\frac 23}$ 的 $f(n)$ 暴力分块计算。
+时间复杂度变为 $O\left(n^{\frac 23}+\sum_{i=1}^{n^{\frac 13}}\sqrt {\frac ni}\right)=O\left(n^{\frac 23}\right)$。
+<hidden 查看代码>
+<code cpp>
+int Mod,Block;
+const int MAXS=2e6+5;
+int prime[MAXS],tau[MAXS],mpow[MAXS],cnt;
+void pre(){
+	tau[1]=1;
+	_for(i,2,Block){
+		if(!tau[i])prime[cnt++]=i,tau[i]=2,mpow[i]=1;
+		for(int j=0;j<cnt&&i*prime[j]<Block;j++){
+			if(i%prime[j])
+			tau[i*prime[j]]=tau[i]<<1,mpow[i*prime[j]]=1;
+			else{
+				tau[i*prime[j]]=tau[i]/(mpow[i]+1)*(mpow[i]+2),mpow[i*prime[j]]=mpow[i]+1;
+				break;
+			}
+		}
+	}
+	_for(i,2,Block)tau[i]=(0LL+tau[i]+tau[i-1])%(Mod-1);
+}
+int quick_pow(unsigned int a,int b){
+	int ans=1;
+	while(b){
+		if(b&1)ans=1LL*ans*a%Mod;
+		a=1LL*a*a%Mod;
+		b>>=1;
+	}
+	return ans;
+}
+int cal(unsigned int n){
+	if(n<Block)return tau[n];
+	unsigned int l=1,r;
+	int ans=0;
+	while(l<=n){
+		r=n/(n/l);
+		ans=(ans+1LL*(r-l+1)*(n/l))%(Mod-1);
+		l=r+1;
+	}
+	return ans;
+}
+int main()
+{
+	unsigned int n=read_LL(),l=1,r;
+	Mod=read_int();Block=pow(Mod,2.0/3)+1;
+	pre();
+	int ans=1;
+	while(l<=n){
+		r=n/(n/l);
+		ans=1LL*ans*quick_pow(1LL*l*quick_pow(r+1,Mod-2)%Mod,cal(n/l))%Mod;
+		l=r+1;
+	}
+	enter(1LL*ans*ans%Mod);
+	return 0;
+}
+</code>
+</hidden>
+===== 7、B-Suffix Array =====
+[[https://ac.nowcoder.com/acm/contest/5666/A|链接]]
+==== 题意 ====
+给出一个字符串，定义一个字符串 $S$ 对应序列 $B$，其中 $b_i=\min_{j\lt i,s_j=s_i} (i-j)$，如果不存在 $j$，$b_i=0$。
+求序列 $B$ 后缀排序后的结果。
+==== 题解 ====
+构造 $c_i=\min_{j\gt i,s_j=s_i}(j-i)$，如果不存在 $j$，$b_i=n$。特别的，$c_{n+1}$ 为 $c$ 的结束符且 $c_{n+1}=n+1$。
+有结论将 $B$ 序列后缀排序结果翻转后与 $C[1,n+1]$ 后缀排序前 $n$ 项相同。
+<hidden 查看代码>
+<code cpp>
+#include <cstdio>
+#include <algorithm>
+#define _for(i,a,b) for(int i=(a);i<(b);++i)
+#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
+#define mem(a,b) memset(a,b,sizeof(a))
+using namespace std;
+typedef long long LL;
+const int MAXN=1e5+5;
+namespace SA{
+	int sa[MAXN],x[MAXN],y[MAXN],c[MAXN];
+	void get_sa(int *s,int n,int m){
+		_rep(i,0,m)c[i]=0;
+		_rep(i,1,n)c[x[i]=s[i]]++;
+		_rep(i,1,m)c[i]+=c[i-1];
+		for(int i=n;i;i--)sa[c[x[i]]--]=i;
+		for(int k=1;k<n;k<<=1){
+			int pos=0;
+			_rep(i,n-k+1,n)y[++pos]=i;
+			_rep(i,1,n)if(sa[i]>k)y[++pos]=sa[i]-k;
+			_rep(i,0,m)c[i]=0;
+			_rep(i,1,n)c[x[i]]++;
+			_rep(i,1,m)c[i]+=c[i-1];
+			for(int i=n;i;i--)sa[c[x[y[i]]]--]=y[i],y[i]=0;
+			_rep(i,1,n)swap(x[i],y[i]);
+			pos=0,y[n+1]=0;
+			_rep(i,1,n)x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?pos:++pos;
+			if(pos==n)break;
+			m=pos;
+		}
+	}
+}
+char buf[MAXN];
+int a[MAXN],last[2];
+int main()
+{
+	int n;
+	while(~scanf("%d%s",&n,buf+1)){
+		last[0]=last[1]=0;
+		for(int i=n;i;i--){
+			int c=buf[i]-'a';
+			if(last[c])a[i]=last[c]-i;
+			else a[i]=n;
+			last[c]=i;
+		}
+		a[n+1]=n+1;
+		SA::get_sa(a,n+1,n+1);
+		for(int i=n;i;i--)
+		printf("%d ",SA::sa[i]);
+		puts("");
+	}
+	return 0;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具