Xiaobai yuesai 51 supplement e g f

E topic

After thinking, I found that a The condition is only useful if it is incremented , So when we create an array, we only need to increment the a Just add it in , Then think about what you started with n The value is 【n*b,（n+1）*b-1】 In this range , Then we can take the intersection of intervals , Match these n The intervals of add up .

using Pll=pair<ll,ll>;
int x;
ll n;
vector<Pll> v;
ll a[MAXN];
ll b[MAXN];

ll query(ll l,ll r,ll x){
	ll tmp1=x*n,tmp2=(n+1)*x-1;
	l=max(l,tmp1);
	r=min(r,tmp2);
	return max(0ll,r-l+1);
}


void solve(){
	scanf("%d",&x);
	int mx=0;
	for(int i=1;i<=x;i++){
		scanf("%lld %lld",a+i,b+i);
		if(a[i]>mx){
			mx=a[i];
			v.push_back(Pll(a[i],b[i]));
		}
	}
	scanf("%lld",&n);
	if(n>=mx) return void(printf("1"));
	ll ans=0;
	for(int i=0;i<v.size();i++){
		if(i) ans+=query(v[i-1].first,v[i].first-1,v[i].second);
		else ans+=query(1,v[i].first-1,v[i].second);
	}
	printf("%lld",ans);
}

F topic

The average sum of all subintervals is required , You can think of a rule

  The same is true for other situations , So you can write code directly , Note that an inverse element is required

const int mod=1e9+7;
int n;
ll a[MAXN];
ll pre[MAXN];
ll sum[MAXN];

ll q_pow(ll a,ll b){
	ll rec=1;
	while(b){
		if(b&1){
			rec=rec*a%mod;
		}
		b>>=1;
		a=a*a%mod;
	}
	return rec;
}

void solve(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",a+i);
		pre[i]=(a[i]+pre[i-1])%mod;
	}
	for(int i=1;i<=n;i++){
		if(i<=n/2+n%2){
			sum[i]=(sum[i-1]+pre[n-i+1]-pre[i-1])%mod;
		}else{
			sum[i]=sum[n-i+1];
		}
	}
	ll ans=0;
	for(int i=1;i<=n;i++){
		ans+=sum[i]*q_pow(i,mod-2);
		ans%=mod;
	}
	printf("%lld\n",ans);
}

G topic

Just recently I was learning string hashing, so it came , Direct positive and reverse hash , Then start enumerating the length of the deleted suffix , The prefix paragraph only has 1, It was originally a palindrome string 2. The last one is the palindrome string 3. A lot less yes Just judge these three kinds separately , Among them, even and odd strings should be distinguished , Special judgment on OK, To judge whether it is a palindrome string, you can use bisection to find the maximum palindrome substring , Then, when the character that is not is reached, it can be judged whether the remaining strings on both sides are palindromes, which indicates whether it is a palindrome string .

int n;
char s[MAXN];
ull h1[MAXN];
ull h2[MAXN];
ull g[MAXN];
const int p=131;
ull query1(int l,int r){
	return h1[r]-h1[l-1]*g[r-l+1];
}
ull query2(int l,int r){
	return h2[l]-h2[r+1]*g[r-l+1];
}

void solve(){
	scanf("%d",&n);
	scanf("%s",s+1);
	g[0]=1;
	for(int i=1;i<=n;i++){
		g[i]=g[i-1]*p;
		h1[i]=h1[i-1]*p+(ull)s[i];
	}
	int ans=0;
	for(int i=n;i>=1;i--) h2[i]=h2[i+1]*p+(ull)s[i];
	for(int i=0;i<n;i++){
		int tmp=(n-i)/2+(n-i)%2;
		if((n-i)%2){
			if(query1(1,n-i)==query2(1,n-i)) ans+=26;
			else{
				int l=0,r=tmp-1;
				while(l<=r){
					int mid=l+r>>1;
					if(query1(tmp-mid,tmp-1)==query2(tmp+1,tmp+mid)) l=mid+1;
					else r=mid-1;
				}
				if(query1(1,tmp-l-1)==query2(tmp+l+1,n-i)) ans+=2;
			}
		}else{
			if(query1(1,n-i)==query2(1,n-i)) ans+=1;
			else{
				int l=0,r=tmp;
				while(l<=r){
					int mid=l+r>>1;
					if(query1(tmp-mid+1,tmp)==query2(tmp+1,tmp+mid)) l=mid+1;
					else r=mid-1;
				}
				if(query1(1,tmp-l)==query2(tmp+l+1,n-i)) ans+=2;
			}
		}
	}
	printf("%d",ans);
}

Personally, I think this set of questions is very good