11 18

定义一个序列 $\{a_n\}$ 合法，当且仅当对于任意一个质数 $p$ ， $\{\gcd(a_n,p^{+\infty}\}\}$ （非严格）单峰。

一个序列的权值 $f(a)$ 为，将这个序列的 $1$ 改成任意值（包括 $1$ ）使得序列合法，并且 $\operatorname{lcm}$ 不增的方案数。

每次询问给定 $[L,R]$ ，求 $\sum \limits_{[l,r] \in [L,R]} f(a[l:r])$ 。

$n \le 2 \times 10^5$ 。

显然每个质因数独立。

结论：对于两个相邻的 $i,j$ 使得 $a_i \neq 1,a_j \neq 1$ 而言，对于任何一个 $p$ ，记录 $v_i$ 为 $a_i$ 在 $p$ 上的指数，如果 $v_i \ge v_j$ ，则对于任意 $i<k<j$ ， $v_k \in [v_j,v_i]$ ，且序列递减。

证明：显然 $v_k \ge v_j$ ，否则 $i,k,j$ 为一个谷。 $v_k \le v_i$ ，否则 $v_k>v_i,v_k>v_j$ ，要么存在一个 $t$ 使得 $t<i$ 且 $v_t>v_i$ ，此时 $t,i,k$ 构成一个谷；要么存在一个 $t$ 使得 $t>j$ 且 $v_t>v_j$ ，此时 $k,j,t$ 构成一个谷；否则没有一个原有的 $t$ 使得 $v_t \le v_j < v_k$ ， $k$ 为全局最大值，此时违反 $\operatorname{lcm}$ 规则。

于是每一段的选择就独立了，就可以比较方便地进行统计了。具体地，对于一个

p

而言，假如一个长度为

l

的

1

连续段左右两侧的

v

值分别为

a,b

，那么相当于是

l+1

个变量，和值为

|a-b|

的方案数。方案数为

\binom{|a-b|+l}{l}

。特别地，如果左右两边没有值的话

v

视为

0

。

具体地，我们考虑进行扫描线，然后维护

[i,r]

序列的权值，之后进行历史和。当

r

扫描到一个

1

的时候，设

i

为最大的数使得

(i,r]

全是

1

，则只对

[1,i]

进行前缀积即可。否则，我们暴力更新所有

j \in (i,r)

的

[j,r]

权值，然后对

[1,i]

进行前缀积。最后，设

v

为最大的数使得

(v,r]

本身权值不为

0

（即只保留非

1

位置后合法），对

[1,v)

区间乘以

0

。

最后再说一下怎么求最大的

v

使得

(v,r]

合法。

BC 性质：我们在往右扫描

r

的时候额外维护一个

p

，满足

[p,r]

不降。当

v_{r+1}>v_r

时，

ans \leftarrow p

，否则

p \leftarrow r+1

。

B 性质：对于每一个质因子都跑一遍显然是不现实的。不过观察到对于 BC 版本而言，如果序列的末尾的

v

值为

0

，那么再插一个

0

不会改变任何东西。所以在扫描

r

时只需要对

r

与

r-1

的质因子的并更新即可。

无特殊性质：我们改为维护最大的

v

使得

a_v \neq 1

且

[v,r]

合法。令

lst_i

为

i

左边最大的

p

使得

a_p \neq 1

，则真正的答案为

lst_{v-1}

。特判前缀

1

。

设矩阵大小

K=2

，则时间复杂度

O(K^3n \log n)

。（使用矩阵维护历史和）

CPP

#include<bits/stdc++.h>

using namespace std;

#define int long long

constexpr int mod=1e9+7;
constexpr int maxn=5e5;

void veradd(int& x,int y){
	x+=y;
	if(x>=mod){
		x-=mod;
	}
}

int add(int x,int y){
	return x+y-(x+y>=mod)*mod;
}

namespace number{

constexpr int maxn=5e5;
int notprime[maxn+5];
int minprime[maxn+5];
vector<int> primes;

void init(){
	notprime[1]=1;
	minprime[1]=1;
	for(int i=2;i<=maxn;i++){
		if(!notprime[i]){
			primes.push_back(i);
			minprime[i]=i;
		}
		for(auto j:primes){
			if(i*j>maxn){
				break;
			}
			notprime[i*j]=1;
			minprime[i*j]=j;
			if(i%j==0){
				break;
			}
		}
	}
}

unordered_map<int,int> split(int x){
	unordered_map<int,int> ans;
	while(x!=1){
		int p=minprime[x];
		int cnt=0;
		while(p==minprime[x]){
			x/=p;
			cnt++;
		}
		ans[p]=cnt;
	}
	return ans;
}
	
}

namespace historysum{
	struct info{
		int a[2];
		
		info(){
			a[0]=a[1]=0;
		}
		
		int& operator [](int x){
			return a[x];
		}
	};
	
	struct Matrix{
		int a[2][2];
		
		Matrix(){
			a[0][0]=a[1][1]=1;
			a[1][0]=a[0][1]=0;	
		}
			
		int* operator [](int x){
			return a[x];
		}
	};

	Matrix Time(int x){
		Matrix ret;
		ret.a[0][0]=x;
		return ret;
	}
	
	Matrix Sum(){	
		Matrix ret;
		ret.a[0][1]=1;
		return ret;
	}
	
	void operator *= (info& a,Matrix t){
		info ret;
		ret[0]=add(a[0]*t[0][0]%mod,a[1]*t[1][0]%mod);
		ret[1]=add(a[0]*t[0][1]%mod,a[1]*t[1][1]%mod);
		a=ret;
	}
	
	void operator += (info& a,info b){
		veradd(a[0],b[0]);
		veradd(a[1],b[1]);
	}
	
	info operator + (info a,info b){
		info ret;
		ret[0]=add(a[0],b[0]);
		ret[1]=add(a[1],b[1]);
		return ret;
	}
	
	Matrix operator * (Matrix a,Matrix b){
		Matrix ret;
		ret[0][0]=(a[0][0]*b[0][0]+a[0][1]*b[1][0])%mod;
		ret[0][1]=(a[0][0]*b[0][1]+a[0][1]*b[1][1])%mod;
		ret[1][0]=(a[1][0]*b[0][0]+a[1][1]*b[1][0])%mod;
		ret[1][1]=(a[1][0]*b[0][1]+a[1][1]*b[1][1])%mod;
		return ret;
	}
	
	info sum[(maxn<<2)+5];
	Matrix tag[(maxn<<2)+5];
	bool havetag[(maxn<<2)+5];
	
	void build(int now,int from,int to){
		sum[now][0]=to-from+1;
		if(from==to)
			return;
		int mid=(from+to)>>1;
		build(now<<1,from,mid);
		build(now<<1|1,mid+1,to);
	}
	
	void on(int now,Matrix tg){
//		cerr<<"Onbeg!: "<<now<<"\n";
		sum[now]*=tg;
	//	cerr<<"Onmid!\n";
		if(havetag[now]==0){
			tag[now]=tg;
	//	cerr<<"Oned!:\n";
			havetag[now]=1;
		}
		else{
			tag[now]=tag[now]*tg;
		}
	}
	
	void pushup(int now){
		sum[now]=sum[now<<1]+sum[now<<1|1];
	}
	
	void pushdown(int now){
		if(havetag[now]){
			on(now<<1,tag[now]);
			on(now<<1|1,tag[now]);
			tag[now]=Matrix();
			havetag[now]=0;
		}
	}

	void update(int now,int from,int to,int ql,int qr,Matrix v){
//		if(now==1){
//			if(v[0][1]==0){
//				cout<<"Update "<<ql<<" "<<qr<<" "<<v[0][0]<<"\n";
//			}
//		}
//		cerr<<from<<" "<<to<<" "<<ql<<" "<<qr<<"\n";
		if(from==ql&&to==qr){
			on(now,v);
			return;
		}
		pushdown(now);
//		cerr<<"Pushdown!\n";
	//	exit(0);
		int mid=(from+to)>>1;
		if(ql<=mid){
			update(now<<1,from,mid,ql,min(qr,mid),v);
		}
		if(mid<qr){
			update(now<<1|1,mid+1,to,max(mid+1,ql),qr,v);
		}
		pushup(now);
	}	
	
	info quary(int now,int from,int to,int ql,int qr){
		if(from==ql&&to==qr){
			return sum[now];
		}
		pushdown(now);
		int mid=(from+to)>>1;
		info ans;
		if(ql<=mid){
			//veradd(ans,quary(now<<1,from,mid,ql,min(mid,qr)));
			ans+=quary(now<<1,from,mid,ql,min(mid,qr));
		}
		if(mid<qr){
			ans+=quary(now<<1|1,mid+1,to,max(mid+1,ql),qr);
		}
		return ans;
	}
}

namespace Binom{
	constexpr int Bmax=maxn+50;
	
	int frac[Bmax+5];
	int ifrac[Bmax+5];
	
	int ksm(int a,int b){
		int ans=1;
		while(b){
			if(b&1){
				ans=ans*a%mod;
			}
			a=a*a%mod;
			b>>=1;
		}
		return ans;
	}
	
	void init(){
		frac[0]=1;
		for(int i=1;i<=Bmax;i++){
			frac[i]=frac[i-1]*i%mod;
		}
		ifrac[Bmax]=ksm(frac[Bmax],mod-2);
		for(int i=Bmax-1;i>=0;i--){
			ifrac[i]=ifrac[i+1]*(i+1)%mod;
		}
	}
	
	int binom(int n,int m){
		return frac[n]*ifrac[n-m]%mod*ifrac[m]%mod;
	}
}

using Binom::binom;
using historysum::update;
using historysum::Time;
using historysum::Sum;
using historysum::update;
using number::split;
using historysum::quary;
using Binom::ksm;

int n,q;
int a[maxn+5];
int lft[maxn+5];
int answer[maxn+5];
unordered_map<int,int> splited[maxn+5];
vector<pair<int,int>> quarys[maxn+5];

int lownotdown[maxn+5];
int llim[maxn+5];
int Mx=1;

void calc(int v,int pos,int lastpos){
	int lastv=splited[lastpos].count(v)?splited[lastpos][v]:0;
	int nowv=splited[pos].count(v)?splited[pos][v]:0;
	if(nowv>lastv){
		//	cout<<pos<<":"<<v<<" Update! "<<nowv<<" "<<lastv<<"\n";
		Mx=max(Mx,lownotdown[v]);
	}
	else if(nowv<lastv){
		lownotdown[v]=pos;
	}
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	Binom::init();
	number::init();
	cin>>n>>q;
	historysum::build(1,1,n);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]==1){
			lft[i]=lft[i-1];
		}
		else{
			lft[i]=i;
		}
	}
	for(int i=1;i<=n;i++){
		splited[i]=split(a[i]);
	}
	for(int i=1;i<=q;i++){
		int l,r;
		cin>>l>>r;
		quarys[r].push_back(make_pair(l,i));
	}
	llim[0]=1;
	for(int i=1;i<=n;i++){
		if(a[i]==1){
			llim[i]=llim[i-1];
		}
		else{
			int lpos=lft[i-1];
			if(lpos==0){
				for(int j=1;j<=maxn;j++){
					lownotdown[j]=i;
				}
				Mx=i;
			}
			else{
				for(auto j:splited[lpos]){
					calc(j.first,i,lpos);
				}
				for(auto j:splited[i]){
					if(!splited[lpos].count(j.first)){
						calc(j.first,i,lpos);
					}
				}
			}
			llim[i]=lft[Mx-1]+1;
		}
	}
	for(int i=1;i<=n;i++){
	//	cerr<<i<<":\n";
		if(a[i]==1){
			if(lft[i]){
				int old=1,New=1;
				for(auto j:splited[lft[i]]){
					if(lft[i]!=i-1)
						old=old*binom(j.second+i-lft[i]-1,i-lft[i]-1)%mod;
					New=New*binom(j.second+i-lft[i],i-lft[i])%mod;
				}
				update(1,1,n,1,lft[i],Time(New*ksm(old,mod-2)%mod));
			}
		}
		else{
			int tail=i-1;
			while(a[tail]==1){
				int bl=1;
				for(auto j:splited[i]){
					bl=bl*binom(j.second+i-tail,i-tail)%mod;
				}
				update(1,1,n,tail,tail,Time(bl));
				tail--;
			}
			if(lft[i-1]){
				if(a[i-1]==1){
					int bl=1;
					for(auto j:splited[lft[i-1]]){
						bl=bl*binom(j.second+i-lft[i-1]-1,i-lft[i-1]-1)%mod;
					}
					bl=ksm(bl,mod-2);
					for(auto j:splited[lft[i-1]]){
						int ben=j.second,other=(splited[i].count(j.first)?splited[i][j.first]:0);
						bl=bl*binom(abs(ben-other)+i-lft[i-1]-1,i-lft[i-1]-1)%mod;
					}
					for(auto j:splited[i]){
						if(!splited[lft[i-1]].count(j.first)){
							bl=bl*binom(j.second+i-lft[i-1]-1,i-lft[i-1]-1)%mod;
						}
					}
					update(1,1,n,1,lft[i-1],Time(bl));
				}
			}
		}
		if(llim[i]!=1){
			update(1,1,n,1,llim[i]-1,Time(0));
		}
		update(1,1,n,1,i,Sum());
		for(auto j:quarys[i]){
			answer[j.second]=quary(1,1,n,j.first,i)[1];
		}
	}
	for(int i=1;i<=q;i++){
		cout<<answer[i]<<"\n";
	}
}

文章操作

相关推荐

评论

11 18