2021.08.23 膜你赛

2024-03-08 10:42:16

2021.08.23 膜你赛

count

Description

问有几个无序二元组 \((x, y)\) 满足 \(x y ≡ 1 \pmod p\), \(0 ≤ x < P, 0 ≤ y <P\)。

无序二元组是指，如果 \(P = 10\)，\((3, 7)\) 和 \((7, 3)\) 只算一次。

Solution

首先根据 \(xy \equiv 1\pmod p\) 可以得 \(x \equiv \frac{1}{y} \pmod p\) ,\(\frac{1}{y}\) 就是 \(x\) 在 \(\mod p\) 意义下的逆元。一个数有逆元当且仅当 \(x,p\)​ 互质，因此我们可以通过求出 \(\phi\) 函数来求解部分答案。

我们发现，答案中的一些数是可以两两配对的，一个数不可以两两配对当且仅当他是一个平方数，如果可以配对，就不满足无序数对的要求，我们可以先减去平方数，将剩下的数减半后再加上原来的数 (Ans-js)>>1+js ,其实通分之后和题解的答案一样，都等于 (Ans+js)>>1。

code

/*
* @Author: smyslenny
* @Date:    2021.08.
* @Title:   
* @Main idea:
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <vector>

#define int long long
#define INF 0x3f3f3f3f
#define orz cout<<"LKP AK IOI\n"
#define MAX(a,b) (a)>(b)?(a):(b)
#define MIN(a,b) (a)>(b)?(a):(b)

using namespace std;
const int mod=998244353;
const int M=5e7+5;
int P,Ans;
int read()
{
	int x=0,y=1;
	char c=getchar();
	while(c<'0' || c>'9') {if(c=='-') y=0;c=getchar();}
	while(c>='0' && c<='9') { x=x*10+(c^48);c=getchar();}
	return y?x:-x;
}
int get_phi(int n) {
    int res=n,a=n;
    for(int i=2;i*i<=a;i++) if(a%i==0) {res=res/i*(i-1);while(a%i==0) a/=i; }
    if(a>1) res=res/a*(a-1);
    return res;
}
int js;
signed main()
{
//	freopen("count.in","r",stdin);
//	freopen("count.out","w",stdout);
	P=read();
	Ans=get_phi(P);
	for(int i=0;i<P;i++)
		if(i*i%P==1)
		js++;
	printf("%lld\n",(Ans+js)>>1);
	return 0; 
}//

color

Description

给出平面上 \(n\) 个点，你要把每个点染成黑色或白色。要求染完之后，任
意一条与坐标轴平行的直线上，黑白点数量差的绝对值小于等于 \(1\)。

Solution

对于x坐标相同的点，我们把这些点两两配对,如果剩下点则不管，然后在每一对点之间连一条边。

对于y坐标相等的点，我们也把这些点两两配对，如果剩下点则不管，然后在每一对点之间连一条边。

最后对得到的图进行其实就是黑白染色就可以得到方案了。总的配对出来的图案就是一个个矩形，或者是两个点连成的线。

Code

/*
* @Author: smyslenny
* @Date:    2021.08.
* @Title:   
* @Main idea:
*/
#incldue <bits/stdc++.h> 
using namespace std;
const int N=1e6+10;
int col[N],n,lstu[N],lstv[N];
void addedge(int u,int v){edge[++num].u=u;edge[num].v=v;edge[num].net=head[u];head[u]=num;}
void dfs(int u,int color)
{
	col[u]=color;
	for(int i=head[u];i;i=edge[i].net) if(col[edge[i].v]==-1) dfs(edge[i].v,color^1);
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++) col[i]=-1;//预处理 
	for(int i=1,x,y;i<=n;i++)
	{
		x=read(),y=read();
		if(lstu[x]) addedge(lstu[x],i),addedge(i,lstu[x]),lstu[x]=0;//围城矩形 
		else lstu[x]=i;
		if(lstv[y]) addedge(lstv[y],i),addedge(i,lstv[y]),lstv[y]=0;
		else lstv[y]=i;
	}
	for(int i=1;i<=n;i++) if(col[i]==-1)dfs(i,0);//将颜色一直图上01 
	for(int i=1;i<=n;i++) printf((col[i])?"0 ":"1 ");
	return 0;
}

sequence

Description

给出一个 \(n\) 个数的序列，一个区间的价值是区间内最小值乘最大值的积。

求所有区间价值和。答案对 \(998244353\) 取模。

Solution

理解了比较长时间才明白了这个方法。

题解里 \(Substack2\) 的方法是在 \([l,r]\) 中找到最大值的位置，记为 \(a_{mid}\)​， 考虑左端点在 \([l,mid]\)​ 内，右端点在 \([mid,r]\) 内的区间的价值和。它们内部的最大值肯定就是 \(a_{mid}\)。

对 \([l,mid]\)​ 做后缀 \(\min\)​，对 \([mid,r]\)​ 做前缀 \(\min\)​，把结果记为 \(mn[i]\)​。即 \(l\leq i\leq mid\)​ 时，\(mn[i] =min \times min_{i-l}^{mid}a_i\)​ ,\(mid< i \leq r\)​ 时,\(m=min_{i=mid}^ra_i\)​ 。

枚举左端点 \(i\)​​​，由于右半部分的 \(mn\)​​​ 是单调的，因为只有遇见更小的数才会变化，所以一定存在一个分界点 \(p\)​​​，使得 \(j ≤ p\)​​ 时 \(mn[j] ≥ mn[i]\)​，\(j>p\) 时 \(mn[j] <mn[i]\)。又由于左半部分的 \(mn\) 也是单调的，所以左端点 \(i\) 移动时，分界点 \(p\) 的移动方向是不变的。这样就容易对每个左端点 \(i\) 都求出分界点 \(p\) 了。另外再求出 \(mn\) 的前缀和，就能求出左端点的区间的价值和了。

然后再递归计算。

正解也应用到了这样的思想。

每次取 \(mid=\lfloor\frac{l+r}{2}\rfloor\)，对最大值进行和最小值类似的操作（把前缀/后缀 \(max\)

的结果记为 \(mx[i]\)​​​​​），求出最大值的分界点 \(q\)​​​​ 。再求出 \(mx\)​​ 的前缀和以及 \(mn\times mx\)​​ 的前缀和。\(p\)​ 和 \(q\)​​ 把右半部分划分成三个区间，对三个区间分别计算。利用求出来的前缀和。

Code

/*
* @Author: smyslenny
* @Date:    2021.08.
* @Title:   
* @Main idea:
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <vector>

#define int long long
#define INF 0x3f3f3f3f
#define orz cout<<"LKP AK IOI\n"
#define MAX(a,b) (a)>(b)?(a):(b)
#define MIN(a,b) (a)>(b)?(a):(b)

using namespace std;
const int MOD=998244353;
const int M=5e5+5;
int n,Ans; 
int mp[M],ans,maxl[M],maxr[M],minl[M],minr[M],sum[M],sum_minl[M],sum_maxl[M];
int read()
{
	int x=0,y=1;
	char c=getchar();
	while(c<'0' || c>'9') {if(c=='-') y=0;c=getchar();}
	while(c>='0' && c<='9') { x=x*10+(c^48);c=getchar();}
	return y?x:-x;
}
void solve(int l,int r)
{
	if(l>r)return;
	if(l==r) { ans=(ans+mp[l]*mp[r])%MOD;return;}
	int mid=l+r>>1;
	solve(l,mid-1);solve(mid+1,r);
	int s=0;
	maxl[0]=maxr[0]=minl[0]=minr[0]=mp[mid]; 
	for(int i=mid+1;i<=r;i++) maxr[i-mid]=max(maxr[i-mid-1],mp[i]),minr[i-mid]=min(minr[i-mid-1],mp[i]);//向后求出前缀最大值最小值 
	for(int i=mid-1;i>=l;i--) maxl[mid-i]=max(maxl[mid-i-1],mp[i]),minl[mid-i]=min(minl[mid-i-1],mp[i]);//先前求出后缀最大值最小值 
	sum[mid-l+1]=0;//清空，原来的答案都计入ans,已经没有用了 
	for(int i=l;i<=mid;i++) sum[mid-i]=(sum[mid-i+1]+minl[mid-i]*maxl[mid-i])%MOD,sum_minl[mid-i]=(sum_minl[mid-i+1]+minl[mid-i])%MOD,sum_maxl[mid-i]=(sum_maxl[mid-i+1]+maxl[mid-i])%MOD;
	//对于在左区间的每一个 i,求 min*max前缀和，min前缀和，max前缀和。以方便找到 p 点 
	int now_minl=0,now_maxl=0;
	for(int i=0;i<=r-mid;i++)//枚举右端点，在左区间寻找答案 
	{
		while(now_minl<=mid-l&&minl[now_minl]>=minr[i])now_minl++;//小于左边区间的长度 （第一个限制） 固定右端点，找到该最大值最小值能够延伸的区间 
		while(now_maxl<=mid-l&&maxl[now_maxl]<=maxr[i])now_maxl++;//以 i 为右端点的最小值，左端点不能比他大，要不然最大值就要变化了 （第二个限制） 
		ans=(ans+minr[i]*maxr[i]%MOD*min(now_minl,now_maxl))%MOD;//加上 x 个 min*max 的答案  所有区间重复的地方 
		ans=ans+sum[max(now_minl,now_maxl)]; 
		if(now_minl<now_maxl)ans=(ans+(sum_minl[now_minl]-sum_minl[now_maxl]+MOD)*maxr[i])%MOD;//超出来的部分 
		else ans=(ans+(sum_maxl[now_maxl]-sum_maxl[now_minl]+MOD)*minr[i])%MOD;
	}
}	
signed main()
{
	n=read();
	for(int i=1;i<=n;i++) mp[i]=read();
	solve(1,n);
	printf("%lld\n",ans%MOD);
	return 0;
}
上一篇：洛谷 P4183 - [USACO18JAN]Cow at Large P（点分治）


下一篇：LeetCode 题解4 寻找两个正序数组中的中位数 解法1