洛谷月赛【LGR-073】题解

本文作者：qyh  本文分类：编程学习笔记  浏览：588
阅读时间：8059字, 约9-13.5分钟

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

注意：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题：可重集

思路：

代码：

#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;
}

希望对大家有所帮助。

关于作者qyh

• 还没有填写个人简介
• Email: qinyihao071206@gmail.com
• 注册于: 2020-04-07 01:29:40