洛谷月赛【LGR-073】题解

Hello, 欢迎登录 or 注册!

/ 21评 / 0赞

本文作者：  本文分类：编程学习笔记  浏览：3136
阅读时间：8286字, 约9-14分钟

题解是我“氪金”弄来的，勿外传。。否则会被官方封号的

customize football jersey
nfl shop coupon code
nfl steelers
custom nfl jersey
nike air jordan blue
wig store
adidas ultraboost
nfl jersey sales
adidas yeezy boost 350 v2 bone
customized jerseys
nfl steelers
human hair wig
nike air jordan
custom football jerseys
sex toys

注意：Div1的同学是CDEF四道题目，Div2的同学是ABCD四道题目。

官网Div1传送门 官网Div2传送门

A题：可持久化动态仙人掌的直径问题（雾）

题解思路：

本题代码（简单到爆，，，所以叫签到题）

#include<bits/stdc++.h>
int n,m;
int main(){
	scanf("%d%d",&n,&m);
	printf("%d",(int)(pow(n,1.0/m)+1e-12));
	return 0;
}

Continue to next page....

B题：混凝土数学

题解思路：

本题代码：

#include<bits/stdc++.h>
using namespace std;
#define FL(a) {freopen(a".in","r",stdin);freopen(a".out","w",stdout);}
#define Mod 998244353
#define int long long
const int mx=200000;
int n,a,tax[200005],sum[200005];
const int inv2=(Mod+1)/2,inv3=(Mod+1)/3,inv6=inv2*inv3%Mod;

signed main(){
//	FL("data1-1");
	scanf("%lld",&n);
	for(int i=1;i<=n;++i){
		scanf("%lld",&a);
		tax[a]++;
	}
	int ans=0;
	for(int i=1;i<=mx;++i)sum[i]=(sum[i-1]+tax[i])%Mod;
	for(int i=1;i<=mx;++i){
		int N=tax[i];
		if(N<2)continue;
//		cerr<<"N: "<<N<<endl;
		ans=(ans+N*(N-1)/2%Mod*(sum[min(i*2-1,mx)]-N)%Mod+N*(N-1)%Mod*(N-2)%Mod*inv6%Mod)%Mod;
	}
	printf("%lld\n",ans);
	cerr<<"ans: "<<ans<<endl;
	return 0;
}

C题：论如何玩转 Excel 表格

思路：

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
using namespace std;
const int maxn = 2e6+10;

int read(){
	int x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+c-48;c=getchar();}
	return x*f;
}

int k,m,n;
int a[maxn],b[maxn],c[maxn],d[maxn],fa[maxn],p[maxn];
pair<int,int> P[maxn];
int sum[maxn];
void add(int x){for(int i=x;i<=n;i+=i&-i)sum[i]++;}
int query(int x){int SUM=0;for(int i=x;i;i-=i&-i)SUM+=sum[i];return SUM;}
int main(){
	n=read();
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<=n;i++)b[i]=read();
	for(int i=1;i<=n;i++){c[i]=read();P[c[i]]=make_pair(i,1);}
	for(int i=1;i<=n;i++){d[i]=read();P[d[i]]=make_pair(i,2);}
	for(int i=1;i<=n;i++){fa[a[i]]=b[i];fa[b[i]]=a[i];}
	for(int i=1;i<=n;i++){
		if(fa[c[i]]!=d[i] || fa[d[i]]!=c[i]){puts("dldsgay!!1");return 0;}
		if((P[a[i]].first+P[a[i]].second)%2!=(i+1)%2){puts("dldsgay!!1");return 0;}
		if((P[b[i]].first+P[b[i]].second)%2!=(i+2)%2){puts("dldsgay!!1");return 0;}
	}
	for(int i=1;i<=n;i++)p[a[i]]=i;
	for(int i=1;i<=n;i++)c[i]=p[c[i]]+p[d[i]];
	long long ans=0;
	for(int i=n;i>=1;i--){
		ans+=query(c[i]);
		add(c[i]);
	}
	printf("%lld\n",ans);
	return 0;
}

D题：可重集

思路：

hack方法

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INT __int128
#define ULL unsigned long long
int read(){
	int a=0;char c=getchar();
	while(c>'9'||c<'0')c=getchar();
	while('0'<=c&&c<='9'){
		a=a*10+c-48;
		c=getchar();
	}
	return a;
}
int MUL(int a,int x,int Mod){
//	return (INT)a*x%Mod;
	int ans=0,w=a;
	while(x){
		if(x&1)ans=(ans+w)%Mod;
		w=(w+w)%Mod;
		x>>=1;
	}
	return ans;
}
const int G1=1145141;
const int MMod=1000000000000000003ll;
#define MN 2000005
#define Ls (x<<1)
#define Rs (x<<1|1)
#define mid ((l+r)>>1)
#define piii pair<int,int>
#define mp make_pair
#define x first
#define y second
int aupd(int a){return (a<MMod)?a:(a-MMod);}
int supd(int a){return (a>=0)?a:(a+MMod);}
int pw1[MN],s1[MN];
int sum[MN];
int n,q,a[MN];
void build(){
	for(int i=1;i<=n;++i){
		s1[i]=aupd(s1[i]+pw1[a[i]]);
		sum[i]=sum[i]+a[i];
		int to=i+(i&(-i));
		s1[to]=aupd(s1[to]+s1[i]);
		sum[to]=sum[to]+sum[i];
	}
}
void add(int x,int v1,int v2){
	while(x<=n){
		s1[x]=aupd(s1[x]+v1);
		sum[x]+=v2;x+=x&(-x);
	}
}
piii ask(int x){
	piii res=mp(0,0);
	while(x){
		res.x=aupd(res.x+s1[x]);
		res.y+=sum[x];
		x-=x&(-x);
	}
	return res;
}
piii qry(int l,int r){
	piii R=ask(r),L=ask(l-1);
	R.x=supd(R.x-L.x);
	R.y-=L.y;
	return R;
}
signed main(){
	n=read();q=read();
	pw1[0]=1;
	for(int i=1;i<=1000000;++i){
		pw1[i]=MUL(pw1[i-1],G1,MMod);
	}
	for(int i=1;i<=n;++i){
		a[i]=read();
	}
	build();
	for(int i=1;i<=q;++i){
		int op=read();
		if(!op){
			int x=read(),y=read();
			add(x,supd(pw1[y]-pw1[a[x]]),y-a[x]);
			a[x]=y;
		}
		else{
			int l1=read(),r1=read(),l2=read(),r2=read(),len=r1-l1+1;
			piii res1=qry(l1,r1),res2=qry(l2,r2);
			int k=res2.y-res1.y;
			if(abs(k)%len!=0){puts("NO");continue;}
			k/=len;
			if(k>=0){
				res1.x=MUL(res1.x,pw1[k],MMod);
			}
			else {
				k=-k;
				res2.x=MUL(res2.x,pw1[k],MMod);
			}
			if(res1.x==res2.x)puts("YES");
			else puts("NO");
		}
	}
	return 0;
}

E题：序列

思路：

代码：

#include<bits/stdc++.h>
using namespace std;
template<typename T>inline T read(){
	T f=0,x=0;char c=getchar();
	while(!isdigit(c)) f=c=='-',c=getchar();
	while(isdigit(c)) x=x*10+c-48,c=getchar();
	return f?-x:x;
}
namespace run{
	const int N=5009,mod=998244353;
	inline int add(int x,int y){return x+y>=mod?x-mod+y:x+y;}
	inline int sub(int x,int y){return x>=y?x-y:x+mod-y;}
	inline int qpow(int x,int y){
		int ret=1;
		while(y){
			if(y&1) ret=1LL*x*ret%mod;
			x=1LL*x*x%mod,y>>=1;
		}
		return ret;
	}
	int fac[N],ifac[N];
	inline int C(int n,int m){
		if(n<0 || m<0 || n<m) return 0;
		return 1LL*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
	}inline int calc(int n,int d,int m){return sub(C(n,n-d-m),C(n,n-d-m+1));}

	int f[N][N],n,k,inv;
	int main(){
		n=read<int>(),k=read<int>(),inv=qpow(n,mod-2);
		fac[0]=ifac[0]=ifac[1]=1;
		for(int i=1;i<=n;i++) fac[i]=1LL*fac[i-1]*i%mod;
		ifac[n]=qpow(fac[n],mod-2);
		for(int i=n-1;i>=1;i--) ifac[i]=1LL*ifac[i+1]*(i+1)%mod;
		assert(1LL*fac[n-1]*ifac[n-1]%mod==1);

		f[0][0]=1;
		for(int i=1;i<=k;i++){
			int sum=f[i-1][n];
			for(int j=min(n,i);j;j--){
				sum=(1LL*sum*j%mod*inv+f[i-1][j-1])%mod;
				f[i][j]=1LL*inv*(n-j+1)%mod*sum%mod;
			}
		}
		int chk=0;
		for(int i=0;i<=n;i++) chk=add(chk,f[k][i]);
		assert(chk==1);

		for(int i=1;i<=n;i++) f[k][i]=1LL*f[k][i]*qpow(C(n,i),mod-2)%mod;
		int ans=0;
		for(int i=1;i<=n;i++)
			for(int j=2;j<=n && min(i,n-i)>=j/2;j+=2)
				ans=(1LL*f[k][i]*calc(n,i,(j-2*i)/2)%mod*j+ans)%mod;
		printf("%d\n",ans);
		return 0;
	}
}
int main(){
#ifdef my
	freopen("sequence.in","r",stdin);
	freopen("sequence.out","w",stdout);
#endif
	return run::main();
}

F题：一次函数

思路：

代码：

#include <bits/stdc++.h>
using namespace std;

const int Maxi = 1030, Maxn = 20005;
int n, m, ct, bloc, f[Maxn][Maxi], pos[Maxi], fac[Maxi];
pair <int, int> from[Maxn][Maxi];
long long d, p, goal, val[Maxn], arr[Maxn];
pair <int, long long> ans[Maxn];
map <int, int> Ma;
typedef pair <long long, long long> pll;
pll G;
pll operator * (const pll &x, const pll &y)
{
	return make_pair((x.first * y.second + x.second * y.first) % p, x.second * y.second % p);
}
long long gcd(long long x, long long y)
{
	return x == 0 ? y : gcd(y % x, x);
}
long long fast_pow(long long x, long long y)
{
	long long ans = 1, now = x;
	while (y)
	{
		if (y & 1) ans = ans * now % p;
		now = now * now % p;
		y >>= 1;
	}
	return ans;
}
pll fast_pow(pll x, long long y)
{
	pll ans = make_pair(0, 1), now = x;
	while (y)
	{
		if (y & 1) ans = ans * now;
		now = now * now;
		y >>= 1;
	}
	return ans;
}
void dp(void)
{
	int maxi = (1 << ct) - 1;
	memset(f, 0x3f, sizeof(f));
	f[0][maxi] = 0;
	for (int i = 1; i <= n; i++)
	{
		int sta = 0;
		long long tmp_val = val[i] / gcd(val[i], goal);
		for (int j = 1; j <= ct; j++)
			if (tmp_val % fac[j] == 0) sta |= 1 << (j - 1);
		for (int j = 1; j <= maxi; j++)
			if (f[pos[j]][j] + 1 < f[pos[j & sta]][j & sta])
			{
				pos[j & sta] = i;
				f[i][j & sta] = f[pos[j]][j] + 1;
				from[i][j & sta] = make_pair(pos[j], j);
			}
	}
}
int get_unit(void)
{
	int maxi = sqrt(p - 1);
	for (int i = 2; ; i++)
	{
		for (int j = 2; j <= maxi; j++)
			if ((p - 1) % j == 0)
			{
				if (fast_pow(i, j) == 1) goto END;
				if (fast_pow(i, (p - 1) / j) == 1) goto END;
			}
		return i;
		END:;
	}
}
void get_factor(void)
{
	int maxi = sqrt(p - 1), tmp = p - 1;
	for (int i = 2; i <= maxi; i++)
		if (tmp % i == 0)
		{
			fac[++ct] = i;
			while (tmp % i == 0) tmp /= i;
		}
	if (tmp != 1) fac[++ct] = tmp;
	fac[++ct] = p;
}
pll exgcd(long long x, long long y)
{
	if (!x)
		return make_pair(0, 1);
	else
	{
		pll tmp = exgcd(y % x, x);
		return make_pair(tmp.second - tmp.first * (y / x), tmp.first);
	}
}
long long mod(__int128 x)
{
	return (x % (p * (p - 1)) + (p * (p - 1))) % (p * (p - 1));
}
void work(int lt, long long goal_now)
{
	long long g = p * (p - 1), div = gcd(goal_now, p * (p - 1));
	for (int i = lt + 1; i <= m; i++)
		g = gcd(g, arr[i]);
	div = gcd(g, arr[lt]);
	arr[lt] /= div, g /= div, goal_now /= div;
	pll result = exgcd(arr[lt], g);
	ans[lt].second = mod((__int128) result.first * goal_now);
	if (lt == m - 1)
	{
		ans[m].second = mod((__int128) result.second * goal_now);
		return ;
	}
	work(lt + 1, mod(mod((__int128) result.second * goal_now) * (__int128) g));
}
void BSGS_init(void)
{
	bloc = sqrt(n * p);
	long long now = 1;
	d = get_unit();
	for (int i = 0; i < bloc; i++)
	{
		Ma[now] = i;
		now = now * d % p;
	}
}
long long BSGS(pll val_now)
{
	long long inv = fast_pow(fast_pow(d, bloc), p - 2), now_inv = 1;
	for (int j = 0; j < p / bloc + 1; j++)
	{
		if (Ma[now_inv * val_now.second % p])
		{
			long long tmp = Ma[now_inv * val_now.second % p] + j * (long long) bloc;
			pll tmp_val = val_now * fast_pow(make_pair(1, d), p * (p - 1) - tmp);
			return ((p - 1) * (p - tmp_val.first * d % p) + tmp) % (p * (p - 1));
		}
		(now_inv *= inv) %= p;
	}
}
int main()
{
	scanf("%d%lld%lld%lld", &n, &p, &G.first, &G.second);
	BSGS_init();
	get_factor();
	goal = BSGS(G);
	long long g = gcd(p * (p - 1), goal);
	for (int i = 1; i <= n; i++)
	{
		pll x;
		scanf("%lld%lld", &x.first, &x.second);
		val[i] = BSGS(x), g = gcd(g, val[i]);
	}
	for (int i = 1; i <= n; i++) val[i] /= g;
	dp();
	if (f[pos[0]][0] > n)
	{
		puts("-1");
		return 0;
	}
	pair <int, int> now = make_pair(pos[0], 0);
	while (now.first)
	{
		arr[++m] = val[now.first];
		ans[m].first = now.first;
		now = from[now.first][now.second];
	}
	work(1, goal);
	printf("%d\n", m);
	for (int i = 1; i <= m; i++)
		printf("%d %lld\n", ans[i].first, ans[i].second);
	return 0;
}

希望对大家有所帮助。

关于作者

  1. qyh说道：
    2020年7月25日 下午9:34

    A : 签到题，没啥思维难度，怕 math 库掉精度，直接暴力枚举莽了（这题目名是咋回事，，，）。
    B : 简单的 cf 风格组合数学题，个人感觉质量一般。
    C : 套路题，这个转逆序对套树状数组的套路不知到见过多少次了。更加不爽的是这题还卡常，网上搬了快读板子才过，没啥意思。
    D : 数据结构题，我太菜了，并没做出来。试图用树状数组维护方差乱搞结果只拿到 25 分 (upd 貌似正解就是哈希乱搞，如果是这样，那这类似的 idea 也出现过无数次了吧)?
    E : 概率 DP，O (n^2k) 的 DP 思路还是很好想，但是优化到 O (nk) 我并不会。然后这个 DP 超级难调，而且有点卡常，60 变 45。
    F : 没看。

    回复
  2. EricNTH说道：
    2020年7月25日 下午10:31

    555 我只看懂了前两题 阿尔卑微

    回复
  3. EricNTH说道：
    2020年7月25日 下午10:36

    太 难 了

    回复
  4. Alex172说道：
    2020年7月26日 上午8:40

    A题直接输出floor(pow(n,1/m))不就好了吗？

    回复
  5. Zhang, Xuheng说道：
    2020年7月26日 下午2:08

    我141比qyh高10分

    回复
  6. Zhang, Xuheng说道：
    2020年7月27日 上午8:07

    https://www.luogu.com.cn/blog/zxhlg/luo-gu-7-yue-yue-sai-zong-jie
    这次比赛因为我有课，所以只打了大概35分钟。
    T1很水，1分钟就过了。
    T2我的第一反应是爆搜，结果打了个大暴力30分。
    T3没有多少时间了，随便骗了subtask1~3的分数（11分）
    最后：100+30+11+0=141.
    总的来说，这次月赛整体难度不算高，如果我能打4h，应该（jue dui）
    可以超过250分。
    希望下次月赛的时候我不用上课。

    回复
  7. Rolling_Code说道：
    2020年7月28日 上午10:26

    我Div2 288分
    笑死了

    回复
  8. NSObject 23786说道：
    2020年7月30日 上午7:36

    @qyh
    你第一条评论和你的实际得分情况不符啊，，，

    回复
  9. 冯子杰说道：
    2021年3月27日 下午1:33

    收藏《洛谷月赛【LGR-073】题解》文章

    回复
  10. 李丽礼说道：
    2021年4月20日 上午6:16

    收藏《洛谷月赛【LGR-073】题解》文章

    回复
  11. 杨琪瑶说道：
    2021年5月14日 下午9:53

    收藏《洛谷月赛【LGR-073】题解》文章

    回复

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注