【2020省选模拟】题解

T1：

考虑设f1[i]f_1[i]表示前ii个走到第二个位置的步数,f2[i]f_2[i]表示走到第三个位置的步数
然后可以发现
f1[i]=2∗f2[i−1]+1,f2[i]=f1[i−1]+2∗f2[i−1]+2f_1[i]=2*f_2[i-1]+1,f_2[i]=f_1[i-1]+2*f_2[i-1]+2
然后矩乘+BSGS矩乘+BSGS优化即可

没有循环展开跑的贼慢

#include<bits/stdc++.h>
using namespace std;
#define cs const
#define re register
#define pb push_back
#define pii pair<int,int>
#define ll long long
#define fi first
#define se second
#define bg begin
cs int RLEN=1<<20|1;
inline char gc(){
    static char ibuf[RLEN],*ib,*ob;
    (ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
    return (ib==ob)?EOF:*ib++;
}
inline int read(){
    char ch=gc();
    int res=0;bool f=1;
    while(!isdigit(ch))f^=ch=='-',ch=gc();
    while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
    return f?res:-res;
}
inline ll readll(){
    char ch=gc();
    ll res=0;bool f=1;
    while(!isdigit(ch))f^=ch=='-',ch=gc();
    while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
    return f?res:-res;
}
template<class tp>inline void chemx(tp &a,tp b){a<b?a=b:0;}
template<class tp>inline void chemn(tp &a,tp b){a>b?a=b:0;}
cs int mod=998244353;
inline int add(int a,int b){return (a+=b)>=mod?(a-mod):a;}
inline int dec(int a,int b){a-=b;return a+(a>>31&mod);}
inline int mul(int a,int b){static ll r;r=1ll*a*b;return (r>=mod)?(r%mod):r;}
inline void Add(int &a,int b){(a+=b)>=mod?(a-=mod):0;}
inline void Dec(int &a,int b){a-=b,a+=a>>31&mod;}
inline void Mul(int &a,int b){static ll r;r=1ll*a*b;a=(r>=mod)?(r%mod):r;}
inline int ksm(int a,int b,int res=1){for(;b;b>>=1,Mul(a,a))(b&1)&&(Mul(res,a),1);return res;}
inline int Inv(int x){return ksm(x,mod-2);}
inline int fix(int x){return (x<0)?x+mod:x;}
cs int N=1025,C=1023;
struct mat{
	int a[3][3];
	mat(){memset(a,0,sizeof(a));}
	inline void init(){
		a[0][0]=0,a[0][1]=1,a[0][2]=0,a[1][0]=2,a[1][1]=2,a[1][2]=0,a[2][0]=1,a[2][1]=2,a[2][2]=1;
	}
	friend inline mat operator *(cs mat &a,cs mat &b){
		mat c;
		for(int i=0;i<3;i++)
		for(int k=0;k<3;k++)
		for(int j=0;j<3;j++)
		Add(c.a[i][j],mul(a.a[i][k],b.a[k][j]));
		return c;
	}
}bas,pw1[N],pw2[N],pw3[N],pw4[N],I;
int main(){	
	bas.init();I.a[0][0]=1,I.a[1][1]=1,I.a[2][2]=1;
	pw1[0]=I;
	for(int i=1;i<N;i++)pw1[i]=pw1[i-1]*bas;
	bas=pw1[N-1];
	pw2[0]=I;
	for(int i=1;i<N;i++)pw2[i]=pw2[i-1]*bas;
	bas=pw2[N-1];
	pw3[0]=I;
	for(int i=1;i<N;i++)pw3[i]=pw3[i-1]*bas;
	bas=pw3[N-1];
	pw4[0]=I;
	for(int i=1;i<N;i++)pw4[i]=pw4[i-1]*bas;
	int res1=0,res2=0;
	int T=read();
	while(T--){
		ll x=readll();
		int c1=(x&C),c2=(x>>10)&C,c3=(x>>20)&C,c4=(x>>30)&C;
		mat now=pw1[c1]*pw2[c2]*pw3[c3]*pw4[c4];
		res1^=now.a[2][0],res2^=now.a[2][1];
	}
	cout<<res1<<" "<<res2<<'
';
	return 0;
}

T2：

首先显然就是要给几个组分配数字，让每个组内排成环，相邻乘积之和最大
首先由gcd(n,k)gcd(n,k)个环

显然每个组取值相邻的一段最优
每一个组按135798642135798642这样排最优

然后O(n2)O(n^2)做完了

#include<bits/stdc++.h>
using namespace std;
#define cs const
#define re register
#define pb push_back
#define pii pair<int,int>
#define ll long long
#define fi first
#define se second
#define bg begin
cs int RLEN=1<<20|1;
inline char gc(){
    static char ibuf[RLEN],*ib,*ob;
    (ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
    return (ib==ob)?EOF:*ib++;
}
inline int read(){
    char ch=gc();
    int res=0;bool f=1;
    while(!isdigit(ch))f^=ch=='-',ch=gc();
    while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
    return f?res:-res;
}
template<class tp>inline void chemx(tp &a,tp b){a<b?a=b:0;}
template<class tp>inline void chemn(tp &a,tp b){a>b?a=b:0;}
int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}
cs int N=5005;
int n,m,a[N],b[N];
inline ll calc(int *a,int n){
	ll res=0;int cnt=0;
	for(int i=1;i<=n;i+=2)b[++cnt]=a[i];
	for(int i=n-(n&1);i;i-=2)b[++cnt]=a[i];
	for(int i=1;i<n;i++)res+=1ll*b[i]*b[i+1];
	res+=1ll*b[n]*b[1];
	return res;
}
int main(){
	n=read();
	for(int i=1;i<=n;i++)a[i]=read();
	sort(a+1,a+n+1);
	m=read();
	while(m--){
		int k=read(),t=gcd(k,n),len=n/t;
		ll res=0;
		for(int i=1;i<=t;i++)res+=calc(a+len*(i-1),len);
		cout<<res<<'
';
	}return 0;
}

T3：

艹这是我之前想出来打算做noipnoip题的一个idea......idea......

显然任意两人之间贡献独立
考虑对于x,yx,y两人
若对于yy求x>yx>y的概率
那么显然要分成[l[y],r[y]],[r[y],r[x]][l[y],r[y]],[r[y],r[x]]两部分来算
第一部分贡献相当于是一个等差数列，第二部分是直接乘一个len[y]len[y]

第二部分直接线段树维护
第一部分可以用线段树维护每个位置的系数与贡献
比如ll记录[l,l+1][l,l+1]的，系数就是l+0.5l+0.5
然后大概推一下怎么算即可

#include<bits/stdc++.h>
using namespace std;
#define cs const
#define re register
#define pb push_back
#define pii pair<int,int>
#define ll long long
#define fi first
#define se second
#define bg begin
cs int RLEN=1<<20|1;
inline char gc(){
    static char ibuf[RLEN],*ib,*ob;
    (ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
    return (ib==ob)?EOF:*ib++;
}
inline int read(){
    char ch=gc();
    int res=0;bool f=1;
    while(!isdigit(ch))f^=ch=='-',ch=gc();
    while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
    return f?res:-res;
}
template<class tp>inline void chemx(tp &a,tp b){a<b?a=b:0;}
template<class tp>inline void chemn(tp &a,tp b){a>b?a=b:0;}
cs int N=100005,lim=100000;
typedef pair<double,double> pp;
namespace t1{
	cs int N=::N<<2;
	double s1[N],s2[N],coef[N],tag[N];
	#define lc (u<<1)
	#define rc ((u<<1)|1)
	#define mid ((l+r)>>1)
	inline void pushup(int u){
		s1[u]=s1[lc]+s1[rc],s2[u]=s2[lc]+s2[rc];
	}
	void build(int u,int l,int r){
		if(l==r){coef[u]=0.5+l;return;}
		build(lc,l,mid),build(rc,mid+1,r);
		coef[u]=coef[lc]+coef[rc];
	}
	inline void pushnow(int u,int l,double k){
		s1[u]+=k*l,s2[u]+=coef[u]*k,tag[u]+=k;
	}
	inline void pushdown(int u,int l,int r){
		if(tag[u]==0)return;
		pushnow(lc,mid-l+1,tag[u]),pushnow(rc,r-mid,tag[u]);
		tag[u]=0;
	}
	void update(int u,int l,int r,int st,int des,double k){
		if(st<=l&&r<=des)return pushnow(u,r-l+1,k);
		pushdown(u,l,r);
		if(st<=mid)update(lc,l,mid,st,des,k);
		if(mid<des)update(rc,mid+1,r,st,des,k);
		pushup(u);//cout<<u<<" "<<l<<" "<<r<<" "<<st<<" "<<des<<" "<<k<<" "<<s1[u]<<" "<<s2[u]<<'
';
	}
	inline pp operator +(cs pp &a,cs pp &b){return pp(a.fi+b.fi,a.se+b.se);}
	pair<double,double> query(int u,int l,int r,int st,int des){
		if(st>des)return pp(0,0);
		if(st<=l&&r<=des)return pp(s1[u],s2[u]);
		pushdown(u,l,r);
		if(des<=mid)return query(lc,l,mid,st,des);
		if(mid<st)return query(rc,mid+1,r,st,des);
		return query(lc,l,mid,st,des)+query(rc,mid+1,r,st,des);
	}
} 
namespace t2{
	cs int N=::N<<2;
	double s[N],tag[N];
	inline void pushup(int u){
		s[u]=s[lc]+s[rc];
	}
	inline void pushnow(int u,int l,double k){
		s[u]+=k*l,tag[u]+=k;
	}
	inline void pushdown(int u,int l,int r){
		if(tag[u]==0)return;
		pushnow(lc,mid-l+1,tag[u]),pushnow(rc,r-mid,tag[u]);
		tag[u]=0;
	}
	void update(int u,int l,int r,int st,int des,double k){
		if(st<=l&&r<=des)return pushnow(u,r-l+1,k);
		pushdown(u,l,r);
		if(st<=mid)update(lc,l,mid,st,des,k);
		if(mid<des)update(rc,mid+1,r,st,des,k);
		pushup(u);
	}
	double query(int u,int l,int r,int st,int des){
		if(st<=l&&r<=des)return s[u];
		double res=0;pushdown(u,l,r);
		if(st<=mid)res+=query(lc,l,mid,st,des);
		if(mid<des)res+=query(rc,mid+1,r,st,des);
		return res;
	}
	#undef lc
	#undef rc
	#undef mid
}
int n,l[N],r[N];
int main(){
	n=read();
	for(int i=1;i<=n;i++)l[i]=read(),r[i]=read();
	t1::build(1,1,lim);
	for(int i=1;i<=n;i++)t1::update(1,1,lim,l[i],r[i]-1,1.0/(r[i]-l[i])),t2::update(1,1,lim,l[i],r[i]-1,1.0/(r[i]-l[i]));//,cout<<l[i]<<" "<<r[i]-1<<" "<<(1.0/(r[i]-l[i]))<<'
';
	for(int i=1;i<=n;i++){
		pp x=t1::query(1,1,lim,l[i],r[i]-1);
		double c=t2::query(1,1,lim,r[i],lim);
		double res=x.se-x.fi*l[i]+c*(r[i]-l[i]);res/=(r[i]-l[i]),res+=0.5;
		printf("%.8lf
",res);
	}return 0;
}
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/stargazer-cyk/p/12328295.html