Reincarnation

正因为梦易碎，才格外美好。

lfxxx Round 3 NOIP 模拟赛

发表于 分类于 ，
本文字数： 18k 阅读时长 ≈ 16 分钟

被薄纱的一集。义妹生活是真的好看。

A. 宝藏（treasure）

题目简介

初始有 个数 ，以及 次操作的机会，每次可以选择一个 满足 ，并将 替换为 ，每次操作给出 。

最大化 。

数据范围：

考虑一个简单的贪心，每次找到最小的 ，然后将其换为 （显然要满足 ），维护一个优先队列即可。

将 排序，然后将 按照 排序，简单归并一下即可。

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<bits/stdc++.h>
#define re register
typedef long long ll;
typedef unsigned long long ull;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	x*=t?-1:1;
}
template<class T,class ...Arc>
inline void read(T &x,Arc &...arc){ read(x),read(arc...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+48);
}
inline void write(char c){ putchar(c); }
inline void write(bool x){ putchar(x?'1':'0'); }
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...Arc>
inline void write(T x,Arc ...arc){ write(x),write(arc...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=5e5+10;
int N,M,val[MAXN];
struct Item
{
	int p,q;
	bool operator<(const Item &x) const { return p<x.p; }
}It[MAXN];
ll sum;
std::priority_queue<int,std::vector<int>,std::greater<int>>Pq;
int main()
{
	freopen("treasure.in","r",stdin);
	freopen("treasure.out","w",stdout);
	read(N,M);
	for(int i=1;i<=N;++i) read(val[i]),Pq.push(val[i]);
	for(int i=1;i<=M;++i) read(It[i].p,It[i].q);
	std::sort(It+1,It+M+1);
	for(int i=1;i<=M;++i)
	{
		if(Pq.empty()) break;
		if(It[i].p>=It[i].q) continue;
		int x=Pq.top();Pq.pop();
		// write(i,' ',x,'\n');
		if(x>=It[i].p)
		{
			if(x<It[i].q) Pq.push(It[i].q);
			else Pq.push(x);
		}
		else sum+=x,--i;
	}
	while(!Pq.empty()){ sum+=Pq.top();Pq.pop(); }
	write(sum);
	return 0;
}
/*

*/

B. 决斗（duel）

题目简介

给定若干张牌，每张牌中有 个数字，第 个数字满足 ，则一共有 种牌，而每种牌有 个。

设 表示牌 和牌 之间同位相等的个数，即 ，现在系统已经选择了 张牌，你需要再选择 张牌（在剩余的牌堆中等概率随机），求出 的期望。对 取模。

数据范围：

可以发现，分数可以拆到每一对牌的每一个位置上，将每一个位置分开考虑，所有从来没有出现过的数的贡献是一样的，出现过的数不超过 个，将出现过的数单独做，没出现过的数统一做贡献即可。

出题人：

对标 的 模拟赛。

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#include<bits/stdc++.h>
using namespace std;
namespace workIO{
	bool isseen(char _ch){
		if(_ch>32&&_ch<127)return true;
		return false;
	}
	bool isnumber(char _ch){
		if(_ch>='0'&&_ch<='9')return true;
		return false;
	}
	const int maxcharsize=1048576;
	#define rcomi readI32
	#define rcomI readI64
	#define rcomu readU32
	#define rcomU readU64
	#define rcomc readaC
	#define rcomC readsC
	#define rcomw readsCs
	#define rcoml readaCs
	#define rcomd readD
	#define rcomD readLD
	#define wcomi writeI32
	#define wcomI writeI64
	#define wcomu writeU32
	#define wcomU writeU64
	#define wcomc writeC
	#define wcoml writeCs
	#define wcomd writeD
	#define wcomD writeLD
	class Istream{
		protected:
			FILE *stream;
			char top;
			void next(){if(top!=EOF)top=fgetc(stream);}
			void clear(){while(!isseen(top))next();}
		public:
			Istream(){stream=stdin;top=fgetc(stream);}
			Istream(const char *file){stream=fopen(file,"r");top=fgetc(stream);}
			void readI32(int &val){val=0;clear();bool nep;if(top=='-'){nep=1;next();}else nep=0;while(isnumber(top)){val=(val<<3)+(val<<1)+(top^48);next();}if(nep)val=-val;}
			void readI64(long long &val){val=0;clear();bool nep;if(top=='-'){nep=1;next();}else nep=0;while(isnumber(top)){val=(val<<3)+(val<<1)+(top^48);next();}if(nep)val=-val;}
			void readU32(unsigned &val){val=0;clear();while(isnumber(top)){val=(val<<3)+(val<<1)+(top^48);next();}}
			void readU64(unsigned long long &val){val=0;clear();while(isnumber(top)){val=(val<<3)+(val<<1)+(top^48);next();}}
			void readaC(char &val){val=top;next();}
			void readaCs(char *val){int len=0;while(top!='\n'){val[len++]=top;next();}val[len]=0;}
			void readsC(char &val){clear();val=top;next();}
			void readsCs(char *val){clear();int len=0;while(isseen(top)){val[len++]=top;next();}val[len]=0;}
			void readD(double &val){val=0;clear();bool nep;double tmp;if(top=='-')nep=1,next();else nep=0;while(isnumber(top)){val+=val;tmp=val;val+=val;val+=val;val+=tmp;val+=(top^48);next();}if(top=='.'){tmp=1;next();while(isnumber(top)){tmp*=0.1;val+=tmp*(top^48);next();}}if(top=='e'||top=='E'){int mx;next();readI32(mx);if(mx<0)mx=-mx,tmp=0.1;else tmp=10;while(mx){if(mx&1)val*=tmp;tmp*=tmp;mx>>=1;}}if(nep)val=-val;}
			void readLD(long double &val){val=0;clear();bool nep;double tmp;if(top=='-')nep=1,next();else nep=0;while(isnumber(top)){val+=val;tmp=val;val+=val;val+=val;val+=tmp;val+=(top^48);next();}if(top=='.'){tmp=1;next();while(isnumber(top)){tmp*=0.1;val+=tmp*(top^48);next();}}if(top=='e'||top=='E'){int mx;next();readI32(mx);if(mx<0)mx=-mx,tmp=0.1;else tmp=10;while(mx){if(mx&1)val*=tmp;tmp*=tmp;mx>>=1;}}if(nep)val=-val;}
			int eof(){if(top==EOF)return 1;return 0;}
			int peek(){return top;}
			void skip(const char val){while(top!=val)next();}
			void readlots(const char *command, ...){va_list lt;va_start(lt,command);void *sr;char tmp;for(int i=0;command[i]!=0;i++){sr=va_arg(lt,void*);tmp=command[i];if(tmp=='i')rcomi(*(int*)sr);else if(tmp=='I')rcomI(*(long long*)sr);else if(tmp=='u')rcomu(*(unsigned*)sr);else if(tmp=='U')rcomU(*(unsigned long long*)sr);else if(tmp=='c')rcomc(*(char*)sr);else if(tmp=='C')rcomC(*(char*)sr);else if(tmp=='w')rcomw((char*)sr);else if(tmp=='l')rcoml((char*)sr);else if(tmp=='d')rcomd(*(double*)sr);else if(tmp=='D')rcomD(*(long double*)sr);}}
			void readarray(const int l,const int r,const char type,void *val){if(type=='i'){int *sr=(int*)val;for(int i=l;i<=r;i++)rcomi(*(sr+i));}else if(type=='I'){long long *sr=(long long*)val;for(int i=l;i<=r;i++)rcomI(*(sr+i));}else if(type=='u'){unsigned *sr=(unsigned*)val;for(int i=l;i<=r;i++)rcomu(*(sr+i));}else if(type=='U'){unsigned long long *sr=(unsigned long long*)val;for(int i=l;i<=r;i++)rcomU(*(sr+i));}else if(type=='d'){double *sr=(double*)val;for(int i=l;i<=r;i++)rcomd(*(sr+i));}else if(type=='D'){long double *sr=(long double*)val;for(int i=l;i<=r;i++)rcomD(*(sr+i));}}
	};
	class Ostream{
		protected:
			FILE *stream;
			char text[maxcharsize];
			char temp[maxcharsize];
			int len;
			void putstream(){for(int i=0;i<len;i++)fputc(text[i],stream);len=0;}
			void put(const char ch){text[len++]=ch;if(ch=='\n'||len==maxcharsize)putstream();}
		public:
			Ostream(){stream=stdout;len=0;}
			Ostream(const char *file){stream=fopen(file,"w");len=0;}
			void writeI32(const int val){int tmp=val;if(tmp<0){tmp=-tmp;put('-');}if(tmp==0){put('0');return;}int tag=0;while(tmp!=0){temp[tag++]=tmp%10+48;tmp/=10;}while(tag!=0)put(temp[--tag]);}
			void writeI64(const long long val){long long tmp=val;if(tmp<0){tmp=-tmp;put('-');}if(tmp==0){put('0');return;}int tag=0;while(tmp!=0){temp[tag++]=tmp%10+48;tmp/=10;}while(tag!=0)put(temp[--tag]);}
			void writeU32(const unsigned val){unsigned tmp=val;if(tmp==0){put('0');return;}int tag=0;while(tmp!=0){temp[tag++]=tmp%10+48;tmp/=10;}while(tag!=0)put(temp[--tag]);}
			void writeU64(const unsigned long long val){unsigned long long tmp=val;if(tmp==0){put('0');return;}int tag=0;while(tmp!=0){temp[tag++]=tmp%10+48;tmp/=10;}while(tag!=0)put(temp[--tag]);}
			void writeC(const char val){put(val);}
			void writeCs(const char *val){for(int i=0;val[i]!=0;i++)put(val[i]);}
			void writeD(const double val,const int point=-1){if(point==-1)sprintf(temp,"%.6lf",val);else sprintf(temp,"%.*lf",point,val);writeCs(temp);}
			void writeLD(const long double val,const int point=-1){if(point==-1)sprintf(temp,"%.8Lf",val);else sprintf(temp,"%.*Lf",point,val);writeCs(temp);}
			void clear(){putstream();}
			void putln(){put('\n');}
			void putspace(){put(' ');}
			void writelots(const char *command, ...){va_list lt;va_start(lt,command);char tmp;for(int i=0;command[i]!=0;i++){tmp=command[i];if(tmp!='@')put(tmp);else{tmp=command[++i];if(tmp=='i')wcomi(va_arg(lt,int));else if(tmp=='I')wcomI(va_arg(lt,long long));else if(tmp=='u')wcomu(va_arg(lt,unsigned));else if(tmp=='U')wcomU(va_arg(lt,unsigned long long));else if(tmp=='c')wcomc(va_arg(lt,int));else if(tmp=='l')wcoml(va_arg(lt,char*));else if(tmp=='@')put('@');else if(isnumber(tmp)){int sd=tmp^48;while(isnumber(tmp=command[++i]))sd=(sd<<3)+(sd<<1)+(tmp^48);if(tmp=='d')wcomd(va_arg(lt,double),sd);else if(tmp=='D')wcomD(va_arg(lt,long double),sd);}else if(tmp=='d')wcomd(va_arg(lt,double));else if(tmp=='D')wcomD(va_arg(lt,long double));}}}
			void writearray(const int l,const int r,const char type,const void *val,const char *gap=" ",const char *end="\n",const int more=-1){if(type=='i'){int *sr=(int*)val;wcomi(*(sr+l));for(int i=l+1;i<=r;i++){writeCs(gap);wcomi(*(sr+i));}}else if(type=='I'){long long *sr=(long long*)val;wcomI(*(sr+l));for(int i=l+1;i<=r;i++){writeCs(gap);wcomI(*(sr+i));}}else if(type=='u'){unsigned *sr=(unsigned*)val;wcomu(*(sr+l));for(int i=l+1;i<=r;i++){writeCs(gap);wcomu(*(sr+i));}}else if(type=='U'){unsigned long long *sr=(unsigned long long*)val;wcomU(*(sr+l));for(int i=l+1;i<=r;i++){writeCs(gap);wcomU(*(sr+i));}}else if(type=='d'){double *sr=(double*)val;wcomd(*(sr+l),more);for(int i=l+1;i<=r;i++){writeCs(gap);wcomd(*(sr+i),more);}}else if(type=='D'){long double *sr=(long double*)val;wcomD(*(sr+l),more);for(int i=l+1;i<=r;i++){writeCs(gap);wcomD(*(sr+i),more);}}writeCs(end);}
	};
}
workIO::Istream input("duel.in");
workIO::Ostream output("duel.out");
const int mod=1000000007;
struct Ans{
	int val;
	Ans(){val=0;}
	Ans(int x){val=x;}
	operator int(){return val;}
	Ans& operator=(const int &x){val=x;return *this;}
	Ans& operator=(const Ans &x){val=x.val;return *this;}
};
Ans operator+(int x,Ans y){Ans s(x+y.val);if(s.val>=mod)s.val-=mod;return s;}
Ans operator+(Ans x,int y){Ans s(x.val+y);if(s.val>=mod)s.val-=mod;return s;}
Ans operator+(Ans x,Ans y){Ans s(x.val+y.val);if(s.val>=mod)s.val-=mod;return s;}
Ans operator-(int x,Ans y){Ans s(x-y.val);if(s.val<0)s.val+=mod;return s;}
Ans operator-(Ans x,int y){Ans s(x.val-y);if(s.val<0)s.val+=mod;return s;}
Ans operator-(Ans x,Ans y){Ans s(x.val-y.val);if(s.val<0)s.val+=mod;return s;}
Ans operator*(int x,Ans y){return Ans((1ll*x*y.val)%mod);}
Ans operator*(Ans x,int y){return Ans((1ll*x.val*y)%mod);}
Ans operator*(Ans x,Ans y){return Ans((1ll*x.val*y.val)%mod);}
Ans& operator+=(Ans &x,int y){x.val+=y;if(x.val>=mod)x.val-=mod;return x;}
Ans& operator+=(Ans &x,Ans y){x.val+=y.val;if(x.val>=mod)x.val-=mod;return x;}
Ans& operator-=(Ans &x,int y){x.val-=y;if(x.val<0)x.val+=mod;return x;}
Ans& operator-=(Ans &x,Ans y){x.val-=y.val;if(x.val<0)x.val+=mod;return x;}
Ans& operator*=(Ans &x,int y){x.val=(1ll*x.val*y)%mod;return x;}
Ans& operator*=(Ans &x,Ans y){x.val=(1ll*x.val*y.val)%mod;return x;}
Ans Pow(Ans x,int y){
	Ans s(1);
	while(y){
		if(y&1)s*=x;
		x*=x;y>>=1;
	}
	return s;
}

const int maxk=100020;
const int maxm=1000020;
Ans n[maxk],nw[maxk];
vector<int> dv[maxk];
vector<int> sz[maxk];
int main(){
	int k,d,m,x,y;Ans r,nr,mr,ans;
	/*
	2^((PI n_i)*r)
	
	k һ���������ֵ�����
	r ͬһ���Ƶ�����
	d һ����������Ҫ������
	m �Ѿ���������
	n_i (1<=i<=k) ���ϵ� i �����ֵ�ֵ��(1 ~ n_i) 
	*/ 
	input.readlots("iii",&k,&r.val,&d);
	for(int i=0;i<k;i++){
		input.readI32(n[i].val);
		r*=n[i];
		cerr << n[i].val << ' ';
	}
	for(int i=0;i<k;i++){
		nw[i]=r*Pow(n[i],mod-2);
		dv[i].clear();sz[i].clear();
	}
	input.readI32(m);
	nr=Pow(r-m,mod-2);
	mr=nr*Pow(r-m-1,mod-2);
	for(int i=0;i<m;i++)
		for(int j=0;j<k;j++){
			input.readI32(x);
			dv[j].push_back(x);
		}
	for(int i=0;i<k;i++){
		sort(dv[i].begin(),dv[i].end());
		x=-1;
		for(int j:dv[i])
			if(x==j)y++;
			else{if(x!=-1)sz[i].push_back(y);x=j;y=1;}
		if(x!=-1)sz[i].push_back(y);
	}
	for(int i=0;i<k;i++){
		for(int j:sz[i]){
			ans+=Ans(j)*(j-1);
			ans+=Ans(j)*(nw[i]-j)*nr*(d-m)*2;
			ans+=Ans(d-m)*(d-m-1)*(nw[i]-j)*(nw[i]-j-1)*mr;
		}
		ans+=(n[i]-(int)(sz[i].size()))*(d-m)*(d-m-1)*nw[i]*(nw[i]-1)*mr;
	}
	output.writeI32(ans*Pow(2,mod-2));
	output.putln();
	return 0;
}

C. 任务（task）

题目简介

设 函数定义如下：

求

对 取模。

手玩一下，或者感性证明一下，因为 ，所以当且仅当 时 。

所以有 。

首先不考虑 的限制，那么整个式子就是 ，调和级数求和，洛谷上有 的做法。

然后发现这个 的限制非常阴间，所以我们从质因子的方面考虑，主打一个玄幻。

数据分治，分块打表。

如果 较小，我们拥有一个暴力的枚举质因子的做法 ，其中 表示 中质数的个数。

枚举 中的是否存在 ，设因子个数为 ，乘积为 ，根据容斥原理，得到贡献：

可以再度化简为 。

然后我们预处理逆元前缀和，对 的部分分段打表。

总时间复杂度 ，其中 为段数，取 比较合适。

然后当 比较大的时候，设定阈值 ，对于 的质数，使用上述做法得到 ，否则暴力拼凑，实际上个数不会超过 ，大概也是 级别的。

std 中 。

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int List[]={...};
int quickpow(int a,int b){
	int ret=1;
	while(b){
		if(b&1) ret=1ull*ret*a%mod;
		a=1ull*a*a%mod;
		b>>=1;
	}return ret;
}
int prime[1000001],tot;
int inv[10000001],Sinv[10000001];
bool isprime[10000001];
int use;
void shai(int n=1e7){
	fill(isprime+1,isprime+1+n,1);
	isprime[1]=0;
	inv[1]=1;
	for(int i=2;i<=n;i++){
		if(isprime[i]){
			prime[++tot]=i;
			inv[i]=quickpow(i,mod-2);
		}
		for(int j=1;j<=tot&&prime[j]*i<=n;j++){
			isprime[i*prime[j]]=0;
			inv[i*prime[j]]=1ull*inv[i]*inv[prime[j]]%mod;
			if(i%prime[j]==0){
				break;
			}
		}
	}
	Sinv[1]=1;
	for(int i=2;i<=n;i++){
		Sinv[i]=Sinv[i-1]+inv[i];
		if(Sinv[i]>=mod) Sinv[i]-=mod; 
	}
}
int Inv(int x){
	if(x<=1e7) return inv[x];
	return mod-1ull*(mod/x)*Inv(mod%x)%mod;
}
int Sum(int x){
	if(x<=1e7) return Sinv[x];
	int ret=List[x/100000];
	for(int i=(x/100000)*100000+1;i<=x;i++){
		ret+=Inv(i);
		if(ret>=mod) ret-=mod;
	}return ret;
}
int n,m;
int ans=0;
void dfs1(int now,int S,int T,int F,int cnt){
	if(now>F) return ;
	long long tmp=1ull*S*prime[now];
	if(tmp>n) return ;
	dfs1(now+1,S,T,F,cnt);
	S=tmp;
	T=1ull*T*inv[prime[now]]%mod;
	if(cnt&1){
		use+=n/S;
		ans+=1ull*T*Sum(n/S)%mod;
		if(ans>=mod) ans-=mod;
	}
	else{
		use-=n/S;
		ans-=1ull*T*Sum(n/S)%mod;
		if(ans<0) ans+=mod;
	}
	dfs1(now+1,S,T,F,cnt+1);
}
void dfs2(int now,int S,int T,int F,bool can){
	if(prime[now]>m&&!can) return ;
	if(now==F+1) return ;
	long long tmp=1ull*S*prime[now];
	if(tmp>n) return ;
	use++;
	dfs2(now+1,S,T,F,can);
	S=tmp;
	T=1ull*T*inv[prime[now]]%mod;
	ans+=T;
	if(ans>=mod) ans-=mod;
	dfs2(now,S,T,F,can|(prime[now]<=m));
}
int T=58;
signed main(){
	freopen("task.in", "r", stdin);
	freopen("task.out", "w", stdout);
	cin>>n>>m;
	shai();
	if(prime[T]>=m){
		int ed=0;
		for(int i=1;i<=tot;i++){
			if(prime[i]<=m) ed=i;
			else break;
		}
		dfs1(1,1,1,ed,1);
		cout<<ans<<'\n';
		return 0;
	}
	dfs1(1,1,1,T,1);
	dfs2(T+1,1,1,tot,0);
	cout<<ans;
}
/*
1000000000 2000
10 5
943618294 24
999999999 3157523
*/

打表部分 ……

D. 德扑（poker）

题目简介

大模拟。

德州扑克的所有规则，计算每一回合每一位选手获胜概率以及最终下注变化。

大模拟还需要题解？？？

相关文章